Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/19424
Title: A note on reverse scheduling with maximum lateness objective
Authors: Li, SS
Brucker, P
Ng, CT 
Cheng, TCE 
Shakhlevich, NV
Yuan, JJ
Keywords: Maximum lateness
Reverse scheduling
Issue Date: 2013
Publisher: Springer
Source: Journal of scheduling, 2013, v. 16, no. 4, p. 417-422 How to cite?
Journal: Journal of scheduling 
Abstract: The inverse and reverse counterparts of the single-machine scheduling problem 1
Lmax are 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 ℓH max. 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 ℓH max, the complexity results are derived based on the properties of the corresponding forward problems, while the case of the norm ℓ2 is treated separately. As a by-product, we resolve an open question on the complexity of problem 1
∑α jTj 2.
URI: http://hdl.handle.net/10397/19424
ISSN: 1094-6136
EISSN: 1099-1425
DOI: 10.1007/s10951-013-0314-4
Appears in Collections:Conference Paper

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

2
Last Week
0
Last month
0
Citations as of Oct 19, 2017

WEB OF SCIENCETM
Citations

3
Last Week
0
Last month
1
Citations as of Oct 15, 2017

Page view(s)

70
Last Week
5
Last month
Checked on Oct 15, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.