97-38
On Polynomial Solvability of two Multiprocessor Scheduling Problems
Preprint series: 97-38, Preprints
- MSC:
- 90C10 Integer programming
- 90C25 Convex programming
Abstract: We discuss a new approach for solving multiprocessor scheduling problems 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.
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.