Solving Single Machine Sequencing to Minimize Maximum Lateness Problem Using Mixed Integer Programming

Despite existing various integer programming for sequencing problems, there is not enough information about practical values of the models. This paper considers the problem of minimizing maximum lateness with release dates and presents four different mixed integer programming (MIP) models to solve this problem. These models have been formulated for the classical single machine problem, namely sequenceposition (SP), disjunctive (DJ), linear ordering (LO) and hybrid (HY). The main focus of this research is on studying the structural properties of minimizing maximum lateness in a single machine using MIP formulations. This comparison helps us know the characteristics and priority of different models in minimizing maximum lateness. Regarding to these characteristics and priorities, while solving the lateness problem in the procedure of solving a real-world problem, we apply the lateness model which yields in solution in shortest period of time and try not to use formulations which never lead to solution for large-scale problems. Beside single machine, these characteristics are applicable to more complicated machine environment. We generate a set of test problems in an attempt to solve the formulations, using CPLEX software. According to the computational results, a detailed comparison between proposed MIP formulations is reported and discussed in order to determine the best formulation which is computationally efficient and structurally parsimonious to solve the considering problem. Among the four presented formulations, sequence-position (SP) has the most efficient computational time to find the optimal solution.