Complexity of cyclic scheduling problems: A state-of-the-art survey

Eugene Levner; Vladimir Kats; David Alcaide López De Pablo; Edwin Tai Chiu Cheng

doi:10.1016/j.cie.2010.03.013

Complexity of cyclic scheduling problems: A state-of-the-art survey

Eugene Levner, Vladimir Kats, David Alcaide López De Pablo, Edwin Tai Chiu Cheng

Research output: Journal article publication › Journal article › Academic research › peer-review

158 Citations (Scopus)

Abstract

In this survey we review the current complexity status of basic cyclic scheduling models. We start with the formulations of three fundamental cyclic scheduling problems, namely the cyclic jobshop, cyclic flowshop, and cyclic project scheduling problems. We present state-of-the-art results on the computational complexity of the problems, paying special attention to recent results on the unsolvability (NP-hardness) of various cyclic problems arising from the scheduling of robotic cells.

Original language	English
Pages (from-to)	352-361
Number of pages	10
Journal	Computers and Industrial Engineering
Volume	59
Issue number	2
DOIs	https://doi.org/10.1016/j.cie.2010.03.013
Publication status	Published - 1 Sept 2010

Keywords

Complexity
Cyclic scheduling problems
Reducibility
Robotic scheduling

ASJC Scopus subject areas

General Computer Science
General Engineering

More information

10.1016/j.cie.2010.03.013

Cite this

@article{84ddc0ddb1a14201a21d83f943d22eaa,

title = "Complexity of cyclic scheduling problems: A state-of-the-art survey",

abstract = "In this survey we review the current complexity status of basic cyclic scheduling models. We start with the formulations of three fundamental cyclic scheduling problems, namely the cyclic jobshop, cyclic flowshop, and cyclic project scheduling problems. We present state-of-the-art results on the computational complexity of the problems, paying special attention to recent results on the unsolvability (NP-hardness) of various cyclic problems arising from the scheduling of robotic cells.",

keywords = "Complexity, Cyclic scheduling problems, Reducibility, Robotic scheduling",

author = "Eugene Levner and Vladimir Kats and {Alcaide L{\'o}pez De Pablo}, David and Cheng, {Edwin Tai Chiu}",

year = "2010",

month = sep,

day = "1",

doi = "10.1016/j.cie.2010.03.013",

language = "English",

volume = "59",

pages = "352--361",

journal = "Computers and Industrial Engineering",

issn = "0360-8352",

publisher = "Elsevier Ltd",

number = "2",

}

TY - JOUR

T1 - Complexity of cyclic scheduling problems: A state-of-the-art survey

AU - Levner, Eugene

AU - Kats, Vladimir

AU - Alcaide López De Pablo, David

AU - Cheng, Edwin Tai Chiu

PY - 2010/9/1

Y1 - 2010/9/1

N2 - In this survey we review the current complexity status of basic cyclic scheduling models. We start with the formulations of three fundamental cyclic scheduling problems, namely the cyclic jobshop, cyclic flowshop, and cyclic project scheduling problems. We present state-of-the-art results on the computational complexity of the problems, paying special attention to recent results on the unsolvability (NP-hardness) of various cyclic problems arising from the scheduling of robotic cells.

AB - In this survey we review the current complexity status of basic cyclic scheduling models. We start with the formulations of three fundamental cyclic scheduling problems, namely the cyclic jobshop, cyclic flowshop, and cyclic project scheduling problems. We present state-of-the-art results on the computational complexity of the problems, paying special attention to recent results on the unsolvability (NP-hardness) of various cyclic problems arising from the scheduling of robotic cells.

KW - Complexity

KW - Cyclic scheduling problems

KW - Reducibility

KW - Robotic scheduling

UR - http://www.scopus.com/inward/record.url?scp=77955700913&partnerID=8YFLogxK

U2 - 10.1016/j.cie.2010.03.013

DO - 10.1016/j.cie.2010.03.013

M3 - Journal article

SN - 0360-8352

VL - 59

SP - 352

EP - 361

JO - Computers and Industrial Engineering

JF - Computers and Industrial Engineering

IS - 2

ER -

Complexity of cyclic scheduling problems: A state-of-the-art survey

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this