Skip to Main content Skip to Navigation
Journal articles

An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times

Abstract : In this paper, we consider a simplified real-life identical parallel machine scheduling problem with sequence-dependent setup times and job splitting to minimize makespan. We propose a heuristic to solve this problem. Our method is composed of two parts. The problem is first reduced into a single machine scheduling problem with sequence-dependent setup times. This reduced problem can be transformed into a Traveling Salesman Problem (TSP), which can be efficiently solved using Little's method. In the second part, a feasible initial solution to the original problem is obtained by exploiting the results of the first part. This initial solution is then improved in a step by step manner, taking into account the setup times and job splitting. We develop a lower bound and evaluate the performances of our heuristic on a large number of randomly generated instances. The solution given by our heuristic is less than 4.88% from the lower bound.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02490429
Contributor : Daniel Gavrysiak <>
Submitted on : Tuesday, February 25, 2020 - 11:07:21 AM
Last modification on : Wednesday, May 20, 2020 - 3:48:08 PM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Farouk Yalaoui, Chengbin Chu. An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times. IIE Transactions, Taylor & Francis, 2003, 35 (2), pp.183-190. ⟨10.1080/07408170304382⟩. ⟨hal-02490429⟩

Share

Metrics

Record views

52