Skip to Main content Skip to Navigation
Book sections

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

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.
Document type :
Book sections
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02490453
Contributor : Daniel Gavrysiak <>
Submitted on : Tuesday, February 25, 2020 - 11:16:05 AM
Last modification on : Wednesday, February 26, 2020 - 2:02:53 AM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

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⟩

Share

Metrics

Record views

45