Exact solution of the single-machine scheduling problem with periodic maintenances and sequence-dependent setup times

Vitor Nesello, Anand Subramanian, Maria Battarra, Gilbert Laporte

Research output: Contribution to journalArticle

Abstract

The single-machine scheduling problem with periodic maintenances and sequence-dependent setup times aims at scheduling jobs on a single machine in which periodic maintenances and setups are required. The objective is the minimization of the makespan. We propose an exact algorithm based on the iterative solution of three alternative arc-time-indexed models. Extensive computational experiments are carried out on 420 benchmark instances with up to 50 jobs, and on 405 newly proposed instances involving up to 150 jobs. We compare the results found by all formulations with those obtained by the best available mathematical formulation. All instances from the existing dataset are solved to optimality for the first time.
LanguageEnglish
Pages498-507
Number of pages10
JournalEuropean Journal of Operational Research
Volume266
Issue number2
Early online date17 Oct 2017
DOIs
StatusPublished - 16 Apr 2018

Fingerprint

Sequence-dependent Setup Times
Single Machine Scheduling
Scheduling Problem
Maintenance
Exact Solution
Scheduling
Formulation
Job Scheduling
Single Machine
Iterative Solution
Exact Algorithms
Computational Experiments
Optimality
Arc of a curve
Benchmark
Alternatives
Experiments
Exact solution
Single machine scheduling
Sequence-dependent setup times

Cite this

Exact solution of the single-machine scheduling problem with periodic maintenances and sequence-dependent setup times. / Nesello, Vitor; Subramanian, Anand; Battarra, Maria; Laporte, Gilbert.

In: European Journal of Operational Research, Vol. 266, No. 2, 16.04.2018, p. 498-507.

Research output: Contribution to journalArticle

@article{f92546db1ece41b79ca56ae1c00b4ff3,
title = "Exact solution of the single-machine scheduling problem with periodic maintenances and sequence-dependent setup times",
abstract = "The single-machine scheduling problem with periodic maintenances and sequence-dependent setup times aims at scheduling jobs on a single machine in which periodic maintenances and setups are required. The objective is the minimization of the makespan. We propose an exact algorithm based on the iterative solution of three alternative arc-time-indexed models. Extensive computational experiments are carried out on 420 benchmark instances with up to 50 jobs, and on 405 newly proposed instances involving up to 150 jobs. We compare the results found by all formulations with those obtained by the best available mathematical formulation. All instances from the existing dataset are solved to optimality for the first time.",
author = "Vitor Nesello and Anand Subramanian and Maria Battarra and Gilbert Laporte",
year = "2018",
month = "4",
day = "16",
doi = "10.1016/j.ejor.2017.10.020",
language = "English",
volume = "266",
pages = "498--507",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "2",

}

TY - JOUR

T1 - Exact solution of the single-machine scheduling problem with periodic maintenances and sequence-dependent setup times

AU - Nesello,Vitor

AU - Subramanian,Anand

AU - Battarra,Maria

AU - Laporte,Gilbert

PY - 2018/4/16

Y1 - 2018/4/16

N2 - The single-machine scheduling problem with periodic maintenances and sequence-dependent setup times aims at scheduling jobs on a single machine in which periodic maintenances and setups are required. The objective is the minimization of the makespan. We propose an exact algorithm based on the iterative solution of three alternative arc-time-indexed models. Extensive computational experiments are carried out on 420 benchmark instances with up to 50 jobs, and on 405 newly proposed instances involving up to 150 jobs. We compare the results found by all formulations with those obtained by the best available mathematical formulation. All instances from the existing dataset are solved to optimality for the first time.

AB - The single-machine scheduling problem with periodic maintenances and sequence-dependent setup times aims at scheduling jobs on a single machine in which periodic maintenances and setups are required. The objective is the minimization of the makespan. We propose an exact algorithm based on the iterative solution of three alternative arc-time-indexed models. Extensive computational experiments are carried out on 420 benchmark instances with up to 50 jobs, and on 405 newly proposed instances involving up to 150 jobs. We compare the results found by all formulations with those obtained by the best available mathematical formulation. All instances from the existing dataset are solved to optimality for the first time.

UR - https://doi.org/10.1016/j.ejor.2017.10.020

U2 - 10.1016/j.ejor.2017.10.020

DO - 10.1016/j.ejor.2017.10.020

M3 - Article

VL - 266

SP - 498

EP - 507

JO - European Journal of Operational Research

T2 - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -