One- and multi-stage scheduling problems with parallel processors

Do, Van Ha

One- and multi-stage scheduling problems with parallel processors

Do, Van Ha

Permalink

Publication Type:: Thesis
Issue Date:: 2006

Closed Access

	Filename	Description	Size
	01Front.pdf	contents and abstract	479.45 kB	Adobe PDF	View/Open
	02Whole.pdf	thesis	4.81 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Do, Van Ha
dc.date.accessioned	2016-12-05T23:54:37Z
dc.date.available	2016-12-05T23:54:37Z
dc.date.issued	2006
dc.identifier.uri	http://hdl.handle.net/10453/66029
dc.description	University of Technology, Sydney. Dept. of Mathematical Sciences.	en_AU
dc.description	NO FULL TEXT AVAILABLE. Access is restricted indefinitely. The hardcopy may be available for consultation at the UTS Library.
dc.description.abstract	NO FULL TEXT AVAILABLE. Access is restricted indefinitely. ----- The thesis studies several deterministic scheduling problems with partially ordered sets of tasks. The first of these problems is the maximum lateness problem with parallel identical machines and partially ordered unit execution time (UET) tasks. Based on the observation that the majority of algorithms developed for this problem are in fact different implementations of the same idea, the thesis generalizes this approach by introducing the notion of a priority algorithm. For each priority algorithm, the thesis introduces the notion of domain which characterizes the instances amenable to this algorithm. The main results of this part of the thesis are the proof of the existence of a priority algorithm with the domain containing domains of all other priority algorithms and the description of this largest possible domain. The next scheduling problem considered in the thesis involves UET multiprocessor tasks. Multiprocessor tasks relax the restriction of the previous model that any task requires only one machine. The thesis presents complexity results for the problem of scheduling partially ordered UET multiprocessor tasks on two identical machines with the criterion of total completion time. The thesis establishes the NP-hardness in the strong sense for the case when the precedence constraints are restricted to a collection of out-trees and for the case when the precedence constraints are restricted to a collection of in-trees. These results strengthen the previously known fact that the considered problem is NP-hard when the precedence constraints are in the form of a series-parallel graph. These complexity results are complemented by a proof of NP-hardness in the strong sense of the two-stage hybrid flow shop problem with UET multiprocessor tasks, the criterion of makespan, and the precedence constraints in the form of chains. The last scheduling model considered in the thesis is quite general and relaxes the restriction of previous models that each task requires only one unit of processing time. In this model, the duration of each multiprocessor task can be any positive integer, bounded above by a constant which remains the same for all instances of the problem. The considered model also involves release times and dedicated machines. The main result of this part of the thesis is the conditions under which the problem can be solved in polynomial time. It is proven that these conditions are applicable to various criteria having certain properties. This result is used in establishing the existence of polynomial-time algorithms for several particular cases. The results presented in this thesis constituted three papers in leading international journals, two published and one submitted for publication, and a chapter in a book published by Springer. These results were presented at three international conferences. The results on computational complexity are listed in the website http://www.mathematik.uni-osnabrueck.de/research/OR/class which is one of the most authoritative references in the field of scheduling complexity.	en_AU
dc.format	Thesis (PhD)
dc.language.iso	en_AU	en_AU
dc.rights	info:eu-repo/semantics/closedAccess
dc.rights	The author owns the copyright in this thesis including all reproduction and reuse rights for the work. The work may not be altered without the permission of the copyright owner. Attribution is essential when quoting or paraphrasing from this thesis.
dc.title	One- and multi-stage scheduling problems with parallel processors	en_AU
dc.type	Thesis	en_AU
utslib.copyright.status	closed_access

Abstract:

NO FULL TEXT AVAILABLE. Access is restricted indefinitely. ----- The thesis studies several deterministic scheduling problems with partially ordered sets of tasks. The first of these problems is the maximum lateness problem with parallel identical machines and partially ordered unit execution time (UET) tasks. Based on the observation that the majority of algorithms developed for this problem are in fact different implementations of the same idea, the thesis generalizes this approach by introducing the notion of a priority algorithm. For each priority algorithm, the thesis introduces the notion of domain which characterizes the instances amenable to this algorithm. The main results of this part of the thesis are the proof of the existence of a priority algorithm with the domain containing domains of all other priority algorithms and the description of this largest possible domain. The next scheduling problem considered in the thesis involves UET multiprocessor tasks. Multiprocessor tasks relax the restriction of the previous model that any task requires only one machine. The thesis presents complexity results for the problem of scheduling partially ordered UET multiprocessor tasks on two identical machines with the criterion of total completion time. The thesis establishes the NP-hardness in the strong sense for the case when the precedence constraints are restricted to a collection of out-trees and for the case when the precedence constraints are restricted to a collection of in-trees. These results strengthen the previously known fact that the considered problem is NP-hard when the precedence constraints are in the form of a series-parallel graph. These complexity results are complemented by a proof of NP-hardness in the strong sense of the two-stage hybrid flow shop problem with UET multiprocessor tasks, the criterion of makespan, and the precedence constraints in the form of chains. The last scheduling model considered in the thesis is quite general and relaxes the restriction of previous models that each task requires only one unit of processing time. In this model, the duration of each multiprocessor task can be any positive integer, bounded above by a constant which remains the same for all instances of the problem. The considered model also involves release times and dedicated machines. The main result of this part of the thesis is the conditions under which the problem can be solved in polynomial time. It is proven that these conditions are applicable to various criteria having certain properties. This result is used in establishing the existence of polynomial-time algorithms for several particular cases. The results presented in this thesis constituted three papers in leading international journals, two published and one submitted for publication, and a chapter in a book published by Springer. These results were presented at three international conferences. The results on computational complexity are listed in the website http://www.mathematik.uni-osnabrueck.de/research/OR/class which is one of the most authoritative references in the field of scheduling complexity.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/66029