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 publicationJournal articleAcademic researchpeer-review

128 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 languageEnglish
Pages (from-to)352-361
Number of pages10
JournalComputers and Industrial Engineering
Volume59
Issue number2
DOIs
Publication statusPublished - 1 Sep 2010

Keywords

  • Complexity
  • Cyclic scheduling problems
  • Reducibility
  • Robotic scheduling

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this