ANALYSIS OF MIXED INTEGER PROGRAMMING FORMULATIONS FOR SINGLE MACHINE SCHEDULING PROBLEMS WITH SEQUENCE DEPENDENT SETUP TIMES AND RELEASE DATES

ABSTRACT The scheduling of jobs over a single machine with sequence dependent setups is a classical problem setting that appears in many practical applications in production planning and logistics. In this work, we analyze six mixed-integer formulation paradigms for this classical context considering release dates and two objective functions: the total weighted completion time and the total weighted tardiness. For each paradigm, we present and discuss a MIP formulation, introducing in some cases new constraints to improve performance. A dominance hierarchy in terms of strength of their linear relaxations bounds is developed. We report extensive computational experiments on a variety of instances to capture several aspects of practical situations, allowing a comparison regarding size, linear relaxation and overall performance. Based on the results, discussions and recommendations are made for the considered problems.