Scheduling jobs with equal processing times and time windows on identical parallel machines

Autor(en): Brucker, Peter
Kravchenko, Svetlana A.
Stichwörter: Engineering; Engineering, Manufacturing; linear programming; Operations Research & Management Science; parallel machines; scheduling
Erscheinungsdatum: 2008
Herausgeber: SPRINGER
Journal: JOURNAL OF SCHEDULING
Volumen: 11
Ausgabe: 4
Startseite: 229
Seitenende: 237
Zusammenfassung: 
We present a linear programming approach to the problem of scheduling equal processing time jobs with release dates and deadlines on identical parallel machines. The known algorithm with complexity O(n(3) log log n) of B. Simons schedules all the jobs while minimizing both the maximum completion time and the mean flow time. Our approach permits also to minimize the weighted sum of completion times and total tardiness in polynomial time for the problems without deadlines. The complexity status of these problems was open.
ISSN: 10946136
DOI: 10.1007/s10951-008-0063-y

Show full item record

Page view(s)

2
Last Week
0
Last month
0
checked on Mar 2, 2024

Google ScholarTM

Check

Altmetric