A note on reverse scheduling with maximum lateness objective

S. S. Li, P. Brucker, Chi To Ng, Edwin Tai Chiu Cheng, N. V. Shakhlevich, J. J. Yuan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)

Abstract

The inverse and reverse counterparts of the single-machine scheduling problem 1||Lmaxare studied in [2], in which the complexity classification is provided for various combinations of adjustable parameters (due dates and processing times) and for five different types of norm: ℓ1,ℓ2,ℓ∞,ℓHσ, and ℓHmax. It appears that the O(n2) -time algorithm for the reverse problem with adjustable due dates contains a flaw. In this note, we present the structural properties of the reverse model, establishing a link with the forward scheduling problem with due dates and deadlines. For the four norms ℓ1, ℓ∞,ℓHσand ℓHmax, the complexity results are derived based on the properties of the corresponding forward problems, while the case of the norm ℓ2is treated separately. As a by-product, we resolve an open question on the complexity of problem 1||∑α jTj2.
Original languageEnglish
Pages (from-to)417-422
Number of pages6
JournalJournal of Scheduling
Volume16
Issue number4
DOIs
Publication statusPublished - 1 Aug 2013

Keywords

  • Maximum lateness
  • Reverse scheduling

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence
  • Engineering(all)
  • Management Science and Operations Research

Cite this