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

作者：Tahar DN; Yalaoui F; Chu CB; Amodeo L

来源：International Journal of Production Economics, 2006, 99(1-2): 63-73.

DOI：10.1016/j.ijpe.2004.12.007

• scheduling
• parallel machine
• splitting
• setup times
• linear programming

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.

• 出版日期2006-2