Constraint Programming in Single Machine Scheduling for Minimizing Makespan with Multiple Constraints

Abstract

This study focuses on developing a scheduling model for sequencing a set of jobs with different release times in a single machine to meet non-similar due dates as well as to reduce total sequence-dependent setup time. A constraint programming (CP) model is proposed to solve the scheduling problem by minimizing makespan under multiple constraints, namely release times, sequence-dependent setup time, and due dates. The proposed constraint programming model is tested and compared with the baseline method derived from as-is scheduling of alloy wheels manufactures. The computational experiments show the proposed constraint programming model outperforms the baseline method in the average improvement in makespan and total setup time. For small-size problems, the proposed scheduling model were optimally solved in a short time, achieving the best average improvement in makespan of 4.8826% and the best average improvement in total setup time of 45.7924%. Despite increasing problem sizes, the proposed scheduling model's computational time deteriorates but continues to provide the best solutions, achieving the best average improvement in makespan of 7.4891% and the best average improvement in total setup time of 55.4033%.