Comparison of different variable and value order strategies for the optimum solution of a single machine scheduling problem with sequence-dependent setups

The job sequencing problem for a single machine with sequence-dependent setups is solved using the constraint programming (CP) and mixed-integer programming (MIP) approaches. For the CP search, ten different variable and value ordering heuristics are tested using both the CP model and/or the combined model of the MIP and CP formulations. Some of these heuristics exploit problem specific data like setup cost and due date. Others rely on hybrid strategies that use the linear programming (LP) solver within the CP search or direct the search using the initial feasible solution obtained from the MIP model. A comparative analysis of the search heuristics and the CP and MIP solvers has been given with respect to the solution times. The research results indicate that the CP solver finds the optimum solution in a very short time compared to the MIP solver as the number of jobs to be scheduled increases