Authors
Ganggang Niu, Shudong Sun, Pascal Lafon, Yingfeng Zhang, Junqiang Wang,
Title
Two decompositions for the bicriteria job-shop scheduling problem with discretely controllable processing times
In
International Journal of Production Research
Volume
50
Issue
24
Pages
7415–7427
Year
2012
Publisher's URL
http://dx.doi.org/10.1080/00207543.2011.651169
Indexed by
Abstract
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.
Affiliations
Offprint