Scheduling UET‐UCT tasks: branch‐and‐bound search in the priority space

Scheduling UET‐UCT tasks: branch‐and‐bound search in the priority space

0.00 Avg rating0 Votes
Article ID: iaor20108993
Volume: 11
Issue: 4
Start Page Number: 627
End Page Number: 646
Publication Date: Dec 2010
Journal: Optimization and Engineering
Authors: , , ,
Keywords: makespan, parallel machines
Abstract:

The paper is concerned with the problem of scheduling partially ordered unit execution time tasks on parallel processors with unit communication delays and release times. Two criteria are considered, the maximum lateness and its particular case, the makespan. This problem plays an important role in scheduling theory and was originally inspired by the applications to multi‐processor computer systems. It is well known that for both criteria the problem is NP‐hard in the strong sense. The paper presents an implementation of the branch‐and‐bound method which does not partition the feasible region explicitly. The theoretical results are complemented by computational experiments.

Reviews

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