A decomposition approach to job-shop scheduling problem with discretely controllable processing times

Ganggang Niu 1, 2 Shudong Sun 3 Pascal Lafon 2 Hongan Yang 3
1 Institute of System Integration and Engineering Management
2 LASMIS - Laboratoire des Systèmes Mécaniques et d'Ingénierie Simultanée
ICD - Institut Charles Delaunay
3 NPU - Northwestern Polytechnical University [Xi'an]
Abstract : Job-shop scheduling problem with discretely controllable processing times (JSP-DCPT) is modeled based on the disjunctive graph, and the formulation of JSP-DCPT is presented. A three-step decomposition approach is proposed so that JSP-DCPT can be handled by solving a job-shop scheduling problem (JSP) and a series of discrete time-cost tradeoff problems. To simplify the decomposition approach, the time-cost phase plane is introduced to describe tradeoffs of the discrete time-cost tradeoff problem, and an extreme mode-based set dominant theory is elaborated so that an upper bound is determined to cut discrete time-cost tradeoff problems generated by using the proposed decomposition approach. An extreme mode-based set dominant decomposition algorithm (EMSDDA) is then proposed. Experimental simulations for instance JSPDCPT_FT10, which is designed based on a JSP benchmark FT10, demonstrate the effectiveness of the proposed theory and the decomposition approach.
Document type :
Journal articles
Complete list of metadatas
https://hal-utt.archives-ouvertes.fr/hal-02275891
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Monday, September 2, 2019 - 9:39:36 AM
Last modification on : Wednesday, October 9, 2019 - 2:40:04 PM

Links full text

istex

Identifiers

Collections

P2MN | UTT

Citation

Ganggang Niu, Shudong Sun, Pascal Lafon, Hongan Yang. A decomposition approach to job-shop scheduling problem with discretely controllable processing times. Science in China Series E: Technological Sciences, Springer Verlag, 2011, 54 (5), pp.1240-1248. ⟨10.1007/s11431-010-4249-0⟩. ⟨hal-02275891⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

5

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD