A mixed integer formulation and an efficient metaheuristic for the unrelated parallel machine scheduling problem: Total tardiness minimization

Abstract

In this paper, the unrelated parallel machine scheduling problem with the objective of minimizing the total tardiness is addressed. For such a problem, a mixed-integer linear programming (MILP) formulation, that considers assignment and positional variables, is presented. In addition, an iterated local search (ILS) algorithm that produces high-quality solutions in reasonable times is proposed for large size instances. The ILS robustness was determined by comparing its performance with the results provided by the MILP. The instances used in this paper were constructed under a new approach which results in tighter due dates than the previous generation method for this problem. The proposed MILP formulation was able to solve instances of up to 150 jobs and 20 machines. Regarding the ILS, it yielded high-quality solutions in a reasonable time, solving instances of a size up to 400 jobs and 20 machines. Experimental results confirm that both approaches are efficient and promising.

Keywords

• Total tardiness
• Unrelated parallel machines
• Scheduling
• Mixed integer programming
• Iterated local search algorithm