An Efficient Heuristic to Minimize the Total Tardiness in the Parallel Machines Scheduling Problem - Archive ouverte HAL Access content directly
Book Sections Year : 2016

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

(1) , (2) , (2) , (1)
1
2

Abstract

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.
Not file

Dates and versions

hal-02490453 , version 1 (25-02-2020)

Identifiers

Cite

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⟩

Collections

CNRS UTT LOSI
22 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More