Parallel machine scheduling with job assignment restrictions

Parallel machine scheduling with job assignment restrictions

0.00 Avg rating0 Votes
Article ID: iaor20082440
Country: United States
Volume: 54
Issue: 3
Start Page Number: 250
End Page Number: 257
Publication Date: Apr 2007
Journal: Naval Research Logistics
Authors: ,
Abstract:

In the classical multiprocessor scheduling problem independent jobs must be assigned to parallel, identical machines with the objective of minimizing the makespan. This article explores the effect of assignment restrictions on the jobs for multiprocessor scheduling problems. This means that each job can only be processed on a specific subset of the machines. Particular attention is given to the case of processing times restricted to one of two values, 1 and λ, differing by at most 2. A matching based polynomial time ϵ-approximation algorithm is developed that has a performance ratio tending to 2−1/1+λ. This algorithm is shown to have the best possible performance, tending to 3/2, for processing times 1 and 2. For the special case of nested processing sets, i.e., when the sets of machines upon which individual jobs may be assigned are non-overlapping, the behavior of list scheduling algorithms is explored. Finally, for assignment restrictions determined by just one characteristic of the machines, such as disc storage or memory constraint in the case of high performance computing, we contribute an algorithm that provides a 3/2 worst case bound and runs in time linear in the number of jobs.

Reviews

Required fields are marked *. Your email address will not be published.