A note on reverse scheduling with maximum lateness objective
Autor(en): | Li, S. S. Brucker, P. Ng, C. T. Cheng, T. C. E. Shakhlevich, N. V. Yuan, J. J. |
Stichwörter: | ALGORITHM; Engineering; Engineering, Manufacturing; Maximum lateness; ONE MACHINE; Operations Research & Management Science; Reverse scheduling; TARDINESS | Erscheinungsdatum: | 2013 | Herausgeber: | SPRINGER | Enthalten in: | JOURNAL OF SCHEDULING | Band: | 16 | Ausgabe: | 4, SI | Startseite: | 417 | Seitenende: | 422 | Zusammenfassung: | The inverse and reverse counterparts of the single-machine scheduling problem 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: , and . It appears that the -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 , and , the complexity results are derived based on the properties of the corresponding forward problems, while the case of the norm is treated separately. As a by-product, we resolve an open question on the complexity of problem . |
ISSN: | 10946136 | DOI: | 10.1007/s10951-013-0314-4 |
Zur Langanzeige
Seitenaufrufe
1
Letzte Woche
0
0
Letzter Monat
0
0
geprüft am 07.06.2024