In deterministic scheduling theory, scheduling problems have been formulated with common assumptions that: (i) timing constraints are absolute and independent; (ii) performance measures are regular; and (iii) a job can execute on at most one processor at any time. In this dissertation, we investigate the complexity of scheduling problems with constraints that do not conform to these assumptions Firstly, we consider a relative timing constraint called temporal distance constraint. We study the problem of scheduling a set of unit-execution-time jobs on one processor subject to both deadline and temporal distance constraints. We show that the problem is NP-hard in the strong sense even when temporal distance constraints take the structure of arbitrary chains and arbitrary values. When the values of temporal distance constraints are the same constant, we extend Han and Lin's work to accommodate problem instances subject to temporal distance constraints of directed trees in which the root has at most two immediate children. We present an $O(n)$ algorithm for the distinct deadline case and an $O(n\sp2)$ algorithm for the non-distinct deadline case Secondly, we consider a non-regular performance measure that imposes penalties for jobs completed early or late. We study the problem of finding a nonpreemptive schedule with minimum maximal weighted earliness and tardiness about a common due date d on one processor. For jobs with arbitrary execution times and arbitrary weights, we prove that this problem in NP-hard in the ordinary sense for any given relation between d and the total execution time. For jobs with equal execution time, we present an $O(n\sp2$) algorithm to find an optimal nonpreemptive schedule Thirdly, we propose a new scheduling model, called the Generalized Task System, to provide the flexibility of both sequential and simultaneous parallel execution of subtasks of a single job on multiple processors. Based on this new model, we study the problem of scheduling a set of independent jobs on two identical processors with the objective of minimizing the total waiting time. For both preemptive and nonpreemptive cases, we show that the problem is NP-hard in the ordinary sense when jobs are allowed to have two parallelizable subtasks / acase@tulane.edu
| Identifer | oai:union.ndltd.org:TULANE/oai:http://digitallibrary.tulane.edu/:tulane_24582 |
| Date | January 1992 |
| Contributors | Ng, Chung Wa (Author), Benard, Mark (Thesis advisor) |
| Publisher | Tulane University |
| Source Sets | Tulane University |
| Language | English |
| Detected Language | English |
| Rights | Access requires a license to the Dissertations and Theses (ProQuest) database., Copyright is in accordance with U.S. Copyright law |
Page generated in 0.2066 seconds