97-38

On Polynomial Solvability of two Multiprocessor Scheduling Problems

by Girlich, E.; Tarnowski, G.

 

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.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster