A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times

Gonzalo Mejía and Francisco Yuraszeck

European Journal of Operational Research, 2020, vol. 285, issue 2, 484-496

Abstract: In this paper, we study Open Shop Scheduling Problems (OSSPs) that involve (1) travel times between machines and/or (2) sequence-dependent setup times. First, we propose a new decoding scheme on the well-known permutation list representation and study its properties. Second, we describe an effective Variable Neighborhood Search (VNS) algorithm which incorporates the proposed decoding scheme and that uses a self-tuning routine to set its most important parameter. Last, we tested the performance of the algorithm on several sets of instances: the first two sets consisted of classical instances of OSSPs extended with randomly generated both travel times and anticipatory sequence-dependent setup times. The third set of problems were instances of OSSPs with travel times previously presented in the literature. The last set of problems consisted of classical OSSP of the literature and was used mainly to corroborate our results. The solutions of the proposed VNS were compared with the solutions of constraint programming (CP) algorithms, previous solutions and with the optimal solutions where available. The results revealed three important things: First, the decoding strategy was the factor that had the greatest influence on the performance of the VNS algorithm. Second, the proposed self-tuning VNS algorithm was robust and very easy to adapt to a variety of OSSPs. Third, the algorithm exhibited consistent and very competitive performance in terms of computer time and solution quality in all sets of instances.

Keywords: Scheduling; Open shop; Variable neighborhood search; Sequence-dependent setup times; Travel times (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://www.sciencedirect.com/science/article/pii/S0377221720301284
Full text for ScienceDirect subscribers only

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:eee:ejores:v:285:y:2020:i:2:p:484-496

DOI: 10.1016/j.ejor.2020.02.010

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().