One- and multi-stage scheduling problems with parallel processors
- Publication Type:
- Thesis
- Issue Date:
- 2006
Closed Access
Filename | Description | Size | |||
---|---|---|---|---|---|
01Front.pdf | contents and abstract | 479.45 kB | |||
02Whole.pdf | thesis | 4.81 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
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: