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

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

Domains: Computer Science [cs]; Operations Research [cs.RO]

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, 2006, 99 (1-2), pp.63-73. ⟨10.1016/j.ijpe.2004.12.007⟩. ⟨hal-02477208⟩