Citation
Scheduling UET Tasks on Two Parallel Machines with the Criteria of Makespan and Total Completion Time. In Selected papers from the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), pages 83-109, Springer, 2005.
Selected
Abstract
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 several decades. The paper gives a positive answer to this question and presents the corresponding polynomial-time algorithm. Another straightforward generalization of the considered classical model is obtained by the introduction of multiprocessor tasks. It is shown that, despite the fact that a slightly modified Coffman-Graham algorithm solves the makespan problem with multiprocessor tasks for arbitrary 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 in the strong sense even for in-trees.
There is no pdf available for this paper. You might like to try to obtain the original source (see the doi, for example)
doi
The doi for this publication is 10.1007/0-387-27744-7_5 You can link directly to the original paper, via the doi, from here
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INBOOK{2005-083-109-SI, chapter = {Selected papers from the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA)},
pages = {83--109},
title = {Scheduling UET Tasks on Two Parallel Machines with the Criteria of Makespan and Total Completion Time},
publisher = {Springer},
year = {2005},
editor = {G. Kendall and E. Burke and S. Petrovic and M. Gendreau},
author = {Y. Zinder and V. Ha Do},
note = {Selected},
abstract = {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 several decades. The paper gives a positive answer to this question and presents the corresponding polynomial-time algorithm. Another straightforward generalization of the considered classical model is obtained by the introduction of multiprocessor tasks. It is shown that, despite the fact that a slightly modified Coffman-Graham algorithm solves the makespan problem with multiprocessor tasks for arbitrary 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 in the strong sense even for in-trees.},
doi = {10.1007/0-387-27744-7_5},
owner = {gxk},
timestamp = {2012.05.29} }