Scheduling UET-UCT tasks: Branch-and-bound search in the priority space
- Publication Type:
- Journal Article
- Optimization and Engineering, 2010, 11 (4), pp. 627 - 646
- Issue Date:
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. © 2009 Springer Science+Business Media, LLC.
Please use this identifier to cite or link to this item: