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

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.
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02283325
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Tuesday, September 10, 2019 - 4:42:54 PM
Last modification on : Wednesday, October 9, 2019 - 2:40:04 PM

Identifiers

Collections

P2MN | UTT

Citation

Ganggang Niu, Shudong Sun, Pascal Lafon, Yingfeng Zhang, Junqiang Wang. Two decompositions for the bicriteria job-shop scheduling problem with discretely controllable processing times. International Journal of Production Research, Taylor & Francis, 2012, 50 (24), pp.7415-7427. ⟨10.1080/00207543.2011.651169⟩. ⟨hal-02283325⟩

Share

Metrics

Record views

3