Zurück zu den Preprints des Jahres 1997


1997-38

On Polynomial Solvability of two Multiprocessor Scheduling Problems

by Girlich, E., Tarnowski, G..


Series: 1997-38, Preprints

MSC:
90C10 Integer programming
90C25 Convex programming

Abstract:
We discuss a new approach for solving multiprocessor scheduling prob-
lems by using and improving results for guillotine pallet loading problem. We
introduce a new class of schedules by analogy with the guillotine restriction for cutting
stock problem and show that many well-known algorithms from classical scheduling
theory construct schedules only from this class. We also consider two multiprocessor
scheduling problems and prove that they can be solved in polynomial time.

Keywords:
greedy algorithm, guillotine cutting stock, multiprocessor scheduling,packing, pallet loading.