A hybrid bin-packing heuristic to multiprocessor scheduling

Adriana Alvim (alviminf.puc-rio.br)
Celso Ribeiro (celsoinf.puc-rio.br)

Abstract: The multiprocessor scheduling problem consists in scheduling a set of tasks with known processing times into a set of identical processors so as to minimize their makespan, i.e., the maximum processing time over all processors. We propose a new heuristic for solving the multiprocessor scheduling problem, based on a hybrid heuristic to the bin packing problem. Computational results illustrating the effectiveness of this approach are reported and compared with those obtained by other heuristics.

Keywords: Multiprocessor scheduling, bin packing, tabu search, hybrid metaheuristics

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Combinatorial Optimization (Meta Heuristics )

Citation: Research report, Catholic University of Rio de Janeiro, Department of Computer Science, February 2004.

Download: [Postscript]

Entry Submitted: 04/05/2004
Entry Accepted: 04/05/2004
Entry Last Modified: 04/05/2004

Modify/Update this entry