Scheduling UET tasks on parallel machines: strength of priority algorithms
- Publisher:
- Western Australian Centre of Excellence in Industrial Optimisation, Curtin University of Technology
- Publication Type:
- Conference Proceeding
- Citation:
- Proceedings of the 18th National Conference of the Australian Society for OPerations Research and the 11th Australian Optimisation Day, 2005, pp. 186 - 191
- Issue Date:
- 2005-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
 | 2005002913.pdf | 390.74 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
The paper is concerned with the problem of shceduling a partially ordered set of unit execution time tasks on parallel identical machines in ordered to minimise the criterion of maximum lateness which plays one of the central roles in scheduling theory. It is well known that the considered scheduling problem is NP-hard in the strong sense, and therefore various polynormial-time algorithms, developed for this problem are usually schracterised by their worst-case performance. For a broad class of scheduling algorithms, the paper introduces a notion of a strength, characterising their worst-case performance and within this formal framework gives a positive answer to the question of the existence of a strongest algorithm i.e. agorithm with the best worst-case performance.
Please use this identifier to cite or link to this item: