SHOP SCHEDULING PROBLEMS WITH MULTIPROCESSOR TASKS ON DEDICATED PROCESSORS

Autor(en): BRUCKER, P
KRAMER, A
Stichwörter: Operations Research & Management Science
Erscheinungsdatum: 1995
Herausgeber: BALTZER SCI PUBL BV
Journal: ANNALS OF OPERATIONS RESEARCH
Volumen: 57
Startseite: 13
Seitenende: 27
Zusammenfassung: 
The computational complexity of shop scheduling problems with multiprocessor tasks on dedicated processors is investigated. The objective is makespan minimization. Preemption of tasks is not allowed. For open and flow-shop problems with three stages, complete classifications into polynomial solvable and NP-hard problems are given. These classifications depend on the compatibility structures of the problems. Furthermore, results for open-shop problems with unit processing times are derived. Finally, it is shown that most of the special cases of the job-shop problem which are polynomially solvable remain polynomially solvable in the multiprocessor task situation.
ISSN: 02545330
DOI: 10.1007/BF02099688

Show full item record

Page view(s)

4
Last Week
0
Last month
3
checked on Mar 4, 2024

Google ScholarTM

Check

Altmetric