Classification and comparison of integer programming formulations for the single-machine sequencing problem

Abstract

It is natural to formulate sequencing problems as integer programming models. However, there are a number of possible formulations the practical value of which can be significantly different. In this paper, we first propose a novel classification of integer programming formulations for single-machine sequencing. Next, we present associated mixed-integer linear programming models for total tardiness minimization. Finally, we conduct an extensive computational study on randomly generated instances. For the unweighted case, the position-indexed formulation with linearly many constraints outperforms others, whereas for the weighted case, it is best to use the sparse reformulation of the time-indexed formulation. Integer programming turns out to be a viable option for many practical problem sizes.