A heuristic algorithm for identical parallel machine scheduling: splitting jobs, sequence-dependent setup times, and limited setup operators

Jun-Ho Lee and Hyun-Jung Kim ()
Additional contact information
Jun-Ho Lee: Chungnam National University
Hyun-Jung Kim: Korea Advanced Institute of Science and Technology

Flexible Services and Manufacturing Journal, 2021, vol. 33, issue 4, No 4, 992-1026

Abstract: Abstract We examine a parallel machine scheduling problem with a job splitting property, sequence-dependent setup times, and limited setup operators, for minimizing makespan. Jobs are split into arbitrary (job) sections that can be processed on different machines simultaneously. When a job starts to be processed on a machine, a setup that requires an operator is performed, and the setup time is sequence-dependent. The number of setup operators is limited, and hence not all of the machines can be set up at the same time. For this problem, we propose a mathematical programming model and analyze a lower bound. We then develop a simple but efficient heuristic algorithm so that it can be used in practice, and analytically derive a worst-case bound of the algorithm. We finally evaluate the performance of the proposed algorithm numerically with various scenarios.

Keywords: Parallel machine scheduling; Job splitting; Setup operators; Sequence-dependent setup times; Heuristic algorithm (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10696-020-09400-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:flsman:v:33:y:2021:i:4:d:10.1007_s10696-020-09400-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10696

DOI: 10.1007/s10696-020-09400-9

Access Statistics for this article

Flexible Services and Manufacturing Journal is currently edited by Hans Günther

More articles in Flexible Services and Manufacturing Journal from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().