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

Show full item record

Page view(s)

3
Last Week
0
Last month
0
checked on Feb 22, 2024

Google ScholarTM

Check

Altmetric