Complexity results for single-machine problems with positive finish-start time-lags
Autor(en): | Brucker, P Knust, S |
Stichwörter: | complexity results; Computer Science; Computer Science, Theory & Methods; flow-shop problem; single machine; SUBJECT; time-lags | Erscheinungsdatum: | 1999 | Herausgeber: | SPRINGER-VERLAG WIEN | Journal: | COMPUTING | Volumen: | 63 | Ausgabe: | 4 | Startseite: | 299 | Seitenende: | 316 | Zusammenfassung: | In a single-machine problem with time-lags a set of jobs has to be processed on a single machine in such a way that certain timing restrictions between the finishing and starting times of the jobs are satisfied and a given objective function is minimized. We consider the case of positive finish-start time-lags l(ij) which mean that between the finishing time of job i and the starting time of job j the minimal distance l(ij) has to be respected. New complexity results are derived for single-machine problems with constant positive time-lags l(ij) = l which also lead to new results for Bow-shop problems with unit processing times and job precedences. |
ISSN: | 0010485X | DOI: | 10.1007/s006070050036 |
Zur Langanzeige
Seitenaufrufe
5
Letzte Woche
1
1
Letzter Monat
0
0
geprüft am 18.05.2024