Scheduling UET tasks on two parallel machines with the criteria of makespan and total completion time
- Publisher:
- Springer
- Publication Type:
- Chapter
- Citation:
- Multidisciplinary Scheduling: Theory and applications, 2005, 1, pp. 83 - 109
- Issue Date:
- 2005-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
 | 2005002911OK.pdf | 2.23 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
Two extensions of the classical scheduling model with two parallel identical machines and a partially ordered set of unit execution time tasks are considered. It is well known that the Coffman-Graham algorithm constructs for this model a so-called ideal schedule: that is, a schedule which is optimal for both makespan and total completion time criteria simultaneously. The question of the existence of such a schedule for the extension of this model, where each task has a release time, has remained open over seneral decades. The paper gives a positive answer to this question and presents the corresponding polynormal-time algorithm.Another straightforward generalisation of the considered classcial model is obtained by the introduction of multiprocessor tasks. It is shown that, despite the fact tha a slightly modified Coffman-Graham algorithm solves the makespan problem with multiprocessor tasks for arbirtary precedence constraints, generally an ideal schedule does not exist and the problem with the criterion of total completion time turns out to be NP-hard ithe strong sense even for in-trees.
Please use this identifier to cite or link to this item: