Two decompositions for the bicriteria job-shop scheduling problem with discretely controllable processing times - Archive ouverte HAL Access content directly
Journal Articles International Journal of Production Research Year : 2012

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

(1, 2) , (1) , (2) , (1) , (1)
1
2

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.
Not file

Dates and versions

hal-02283325 , version 1 (10-09-2019)

Identifiers

Cite

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, 2012, 50 (24), pp.7415-7427. ⟨10.1080/00207543.2011.651169⟩. ⟨hal-02283325⟩

Collections

CNRS UTT
12 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More