Zurück zu den Preprints des Jahres 1997


On Polynomial Solvability of two Multiprocessor Scheduling Problems

by Girlich, E., Tarnowski, G..

Series: 1997-38, Preprints

90C10 Integer programming
90C25 Convex programming

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.

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