Order acceptance and scheduling on non-identical parallel machines with dependent setup times: new mixed integer programming formulations
摘要
This research investigates the Order Acceptance and Scheduling (OAS) problem in make-to-order systems, where the objective is to maximize net revenue by optimizing job acceptance and scheduling decisions. Notably, this work focuses on determining the optimal number of jobs to accept for processing and the optimal allocation and sequencing of the accepted jobs on non-identical parallel machines. Unlike most prior works, this research considers machine- and sequence-dependent setup times (MSDST) in OAS, which directly affect processing times and machine availability, thereby requiring additional modelling considerations. We propose three mixed-integer linear programming (MILP) formulations to address the OAS problem with MSDST on non-identical parallel machines, differing primarily in their decision variable structures. The models are evaluated through extensive computational experiments, and their performance is compared against a benchmark model. The results demonstrate the impact of formulation strategies on computational efficiency and provide a foundation for advancing scheduling methods in make-to-order manufacturing environments.