Scheduling UET tasks on two parallel machines with the criteria of makespan and total completion time

DSpace/Manakin Repository

Search OPUS


Advanced Search

Browse

My Account

Show simple item record

dc.contributor.author Zinder, Y
dc.contributor.author Do, V
dc.contributor.editor Kendall, G
dc.contributor.editor Burke, E
dc.contributor.editor Petrocic, S
dc.contributor.editor Gendreau, M
dc.date.accessioned 2010-06-16T04:55:08Z
dc.date.issued 2005-01
dc.identifier.citation Multidisciplinary Scheduling: Theory and applications, 2005, 1, pp. 83 - 109
dc.identifier.isbn 0-387-25266-5
dc.identifier.other B1 en_US
dc.identifier.uri http://hdl.handle.net/10453/11621
dc.description.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 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.
dc.publisher Springer
dc.title Scheduling UET tasks on two parallel machines with the criteria of makespan and total completion time
dc.type Chapter
dc.parent Multidisciplinary Scheduling: Theory and applications
dc.journal.number en_US
dc.publocation USA en_US
dc.publocation Melbourne, Australia
dc.publocation USA
dc.publocation USA
dc.identifier.startpage 83 en_US
dc.identifier.endpage 109 en_US
dc.cauo.name SCI.Mathematical Sciences en_US
dc.conference Verified OK en_US
dc.conference Australia and New Zealand Business Academy Conference
dc.for 010303 Optimisation
dc.personcode 930901
dc.personcode 004207
dc.percentage 100 en_US
dc.classification.name Optimisation en_US
dc.classification.type FOR-08 en_US
dc.edition 1 en_US
dc.edition 1
dc.edition 1
dc.custom en_US
dc.date.activity en_US
dc.date.activity 2005-11-10
dc.location.activity en_US
dc.location.activity Melbourne, Australia
dc.description.keywords schduing, parallel machines, precedence constraints, multiprocessor tasks
dc.description.keywords schduing, parallel machines, precedence constraints, multiprocessor tasks
pubs.embargo.period Not known
pubs.organisational-group /University of Technology Sydney
pubs.organisational-group /University of Technology Sydney/Faculty of Science
utslib.copyright.status Closed Access
utslib.copyright.date 2015-04-15 12:17:09.805752+10
utslib.copyright.date 2015-04-15 12:17:09.805752+10
pubs.consider-herdc true
pubs.consider-herdc true
utslib.collection.history Closed (ID: 3)


Files in this item

This item appears in the following Collection(s)

Show simple item record