A worm optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times

Jean-Paul Arnaout ()
Additional contact information
Jean-Paul Arnaout: Gulf University for Science and Technology

Annals of Operations Research, 2020, vol. 285, issue 1, No 12, 273-293

Abstract: Abstract This paper addresses the unrelated parallel machine scheduling problem with setup times, with an objective of minimizing the makespan. The machines are unrelated in the sense that the processing speed depends on the job being executed and not the machine. Each job will have different processing times for each of the available machines, is available at the beginning of the scheduling horizon, and can be processed on any of the machines but needs to be processed by one machine only. Sequence-dependent and machine-dependent setup times are also considered. A Worm Optimization (WO) algorithm is introduced and is applied to this NP-hard problem. The novel WO is based on the behaviors of the worm, which is a nematode with only 302 neurons. Nevertheless, these neurons allow worms to achieve several intricate behaviors including finding food, interchanging between solitary and social foraging styles, alternating between dwelling and roaming, and entering a type of stasis/declining stage. WO’s performance is evaluated by comparing its solutions to solutions of six other known metaheuristics for the problem under study, and the extensive computational results indicated that the proposed WO performs best.

Keywords: Worm optimization; Unrelated parallel machines; Setup time (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-019-03138-w 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:annopr:v:285:y:2020:i:1:d:10.1007_s10479-019-03138-w

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

DOI: 10.1007/s10479-019-03138-w

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().