A note on reverse scheduling with maximum lateness objective |
| |
Authors: | S S Li P Brucker C T Ng T C E Cheng N V Shakhlevich J J Yuan |
| |
Affiliation: | 1. College of Science, Zhongyuan University of Technology, Zhengzhou, 450007, People’s Republic of China 2. University of Osnabrueck, Faculty of Mathematics/Informatics, 49069, Osnabrueck, Germany 3. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong 4. School of Computing, University of Leeds, Leeds, LS2 9JT, UK 5. Department of Mathematics, Zhengzhou University, Zhengzhou, 450001, People’s Republic of China
|
| |
Abstract: | The inverse and reverse counterparts of the single-machine scheduling problem $1||L_{\max }$ 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: $\ell _{1},\ell _{2},\ell _{\infty },\ell _{H}^{\Sigma } $ , and $\ell _{H}^{\max }$ . It appears that the $O(n^{2})$ -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 $\ell _{1},\ell _{\infty },\ell _{H}^{\Sigma }$ , and $ \ell _{H}^{\max }$ , the complexity results are derived based on the properties of the corresponding forward problems, while the case of the norm $\ell _{2}$ is treated separately. As a by-product, we resolve an open question on the complexity of problem $1||\sum \alpha _{j}T_{j}^{2}$ . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|