Two decompositions for the bicriteria job-shop scheduling problem with discretely controllable processing times

Ganggang Niu, Shudong Sun, Pascal Lafon, Yingfeng Zhang, Junqiang Wang

科研成果: 期刊稿件文章同行评审

22 引用 (Scopus)

摘要

The job-shop scheduling problem with discretely controllable processing times (JSP-DCPT) is a combination of two kinds of sub-problems: the job-shop scheduling problem and the discrete time-cost tradeoff problem. Neither good approximation algorithms nor efficient exact algorithms exist for the bicriteria JSP-DCPT that is to simultaneously minimise the duration and the cost of performing schedules to the problem. An assignment-first decomposition (AFD) and a sequencing-first decomposition (SFD) are proposed for solving the problem. The main difference between the two decompositions lies in the logical sequence for solving the two kinds of sub-problems. The comparison is carried out by evaluating the size of the searching space with respect to each of the two decompositions, and a general conclusion is deduced that for the JSP-DCPT with at least two machines, at least two jobs, and at least two modes for each operation, the efficiency of the searching-based approaches incorporating SFD is superior to that incorporating AFD. Computational studies on JSP-DCPT instances constructed based on a set of well-known JSP benchmarks illustrate the overall superiority of SFD to AFD regarding multiple measure metrics.

源语言英语
页(从-至)7415-7427
页数13
期刊International Journal of Production Research
50
24
DOI
出版状态已出版 - 15 12月 2012

指纹

探究 'Two decompositions for the bicriteria job-shop scheduling problem with discretely controllable processing times' 的科研主题。它们共同构成独一无二的指纹。

引用此