An Efficient Heuristic to Minimize the Total Tardiness in the Parallel Machines Scheduling Problem

Andres Felipe Bernate Lara (1) , Farouk Yalaoui (2) , Frédéric Dugardin (2) , Françoise Entzmann (1)

1 OSIRIS, Soufflet Group, Nogent sur Seine
2 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

This chapter deals with the parallel machines scheduling problem to minimize the total tardiness , when jobs have different release dates . Preemption and splitting are not allowed and machines are considered identical. Since one machine scheduling problem is NP-Hard then parallel machines scheduling problem is NP-Hard too. In this paper we develop a mathematical model which describes the parallel machine scheduling problem and provides optimal solutions of small size instances. Moreover, heuristic methods are provided to solve all instances. Finally, we propose a Tabu Inspired Heuristic (TIH) to get good solutions. Computational tests are driven performing over 1,000 different instances based on literature to identify the most effective structure for the proposed heuristic algorithm to minimize total tardiness. The obtained results are discussed and analyzed.

Keywords: Completion Time; Parallel Machine; Priority Rule; Tabu List; Total Tardiness

Domains: Operations Research [cs.RO]

Andres Felipe Bernate Lara, Farouk Yalaoui, Frédéric Dugardin, Françoise Entzmann. An Efficient Heuristic to Minimize the Total Tardiness in the Parallel Machines Scheduling Problem. Metaheuristics for Production Systems, 60, pp.241-262, 2016, Operations Research/Computer Science Interfaces Series, 978-3-319-23350-5. ⟨10.1007/978-3-319-23350-5_11⟩. ⟨hal-02490453⟩