One- and multi-stage scheduling problems with parallel processors

Publication Type:
Thesis
Issue Date:
2006
Filename Description Size
01Front.pdfcontents and abstract479.45 kB
Adobe PDF
02Whole.pdfthesis4.81 MB
Adobe PDF
Full metadata record
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: