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

Gonzalo Mejía, Francisco Yuraszeck

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)484-496
Number of pages13
JournalEuropean Journal of Operational Research
Volume285
Issue number2
DOIs
Publication statusPublished - 1 Sep 2020

Keywords

  • Open shop
  • Scheduling
  • Sequence-dependent setup times
  • Travel times
  • Variable neighborhood search

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times'. Together they form a unique fingerprint.

Cite this