TITLE

Heuristics Based on Partial Enumeration for the Unrelated Parallel Processor Scheduling Problem

AUTHOR(S)
Mokotoff, E.; Jimeno, J. L.
PUB. DATE
November 2002
SOURCE
Annals of Operations Research;Nov2002, Vol. 117 Issue 1-4, p133
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
The classical deterministic scheduling problem of minimizing the makespan on unrelated parallel processors is known to be NP-hard in the strong sense. Given the mixed integer linear model with binary decision variables, this paper presents heuristic algorithms based on partial enumeration. Basically, they consist in the construction of mixed integer subproblems, considering the integrality of some subset of variables, formulated using the information obtained from the solution of the linear relaxed problem. Computational experiments are reported for a collection of test problems, showing that some of the proposed algorithms achieve better solutions than other relevant approximation algorithms published up to now.
ACCESSION #
9964425

 

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics