Skip to Main content Skip to Navigation
Journal articles

A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times

Djamel Nait Tahar 1 Farouk Yalaoui 1 Chengbin Chu 1 Lionel Amodeo 1
1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
ICD - Institut Charles Delaunay
Abstract : In this study, we consider the problem of scheduling a set of independent jobs with sequence-dependent setup times and job splitting, on a set of identical parallel machines such that maximum completion time (makespan) is minimized. For this NP-hard problem, we suggest a heuristic algorithm improving an existing one, using a linear programming modeling with setup times and job splitting considerations. The performance of our new method is tested on over 6000 instances with different size by comparing it with a lower bound.
Keywords : Scheduling Parallel machine Splitting Setup times Linear programming
Document type :
Journal articles
Complete list of metadatas
https://hal-utt.archives-ouvertes.fr/hal-02477208
Contributor : Daniel Gavrysiak <>
Submitted on : Thursday, February 13, 2020 - 11:32:15 AM
Last modification on : Wednesday, May 20, 2020 - 3:48:08 PM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Djamel Nait Tahar, Farouk Yalaoui, Chengbin Chu, Lionel Amodeo. A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times. International Journal of Production Economics, Elsevier, 2006, 99 (1-2), pp.63-73. ⟨10.1016/j.ijpe.2004.12.007⟩. ⟨hal-02477208⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

44