Scheduling UET-UCT tasks: bransch-and-bound search in the priority space

Publisher:
Springer
Publication Type:
Journal Article
Citation:
Optimization and Engineering, 2010, 11 (4), pp. 627 - 646
Issue Date:
2010-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2010004994OK.pdf413.87 kB
Adobe PDF
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.
Please use this identifier to cite or link to this item: