Continuous task scheduling on unrelated multiprocessing systems.
Item
-
Title
-
Continuous task scheduling on unrelated multiprocessing systems.
-
Identifier
-
AAI9405605
-
identifier
-
9405605
-
Creator
-
Yeh, Henry Tang-Yu.
-
Contributor
-
Advisers: David Dannenbring | Georghios Sphicas | William Chien
-
Date
-
1993
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Business Administration, Management | Computer Science
-
Abstract
-
A class of problems which concerns the nonpreemptive scheduling of independent tasks on a set of processors with different capabilities are investigated. Each processor can process one task at a time, and a task can only be processed on one processor at a time. Basically, we are given a set of tasks to be assigned to a set of processors, where each processor can only execute a subset of tasks. We assume that no processors can work indefinitely without any rest. That is, each processor, after working continuously for a certain period of time, must take a rest for a specified interval of time. A maximum working time and a minimum resting time are specified for each processor. Our problem is: Can we construct a feasible schedule which assigns the tasks to the processors in such a way that at any time unit there exist at least (or at most) some processors working. Furthermore, if such a schedule exists, we want all the tasks to be finished in the shortest time. Processors are unrelated in the sense that the time required for the execution of a task on a processor is a function of both the task and the processor. This problem is referred to as continuous task scheduling on unrelated multiprocessing systems. The continuous task scheduling problem may be applied to banks, toll booths, fast food stores, manufacturers, hospitals, schools, computer local area networks, etc.;We formulate this problem as an exact integer programming model, which can then be solved using standard integer programming codes. Then, we find an alternative--a sequential solution method to relax and decompose the exact model. Finally, due to the limitation of the integer programming package, we develop an heuristic algorithm, with two versions of a reassignment subroutine, to solve the problem. The effectiveness of the heuristic approach or algorithm has been demonstrated: Its accuracy is 99.5% of the exact models and about 10{dollar}\sp4{dollar} faster than that of GAMS. The maximum problem size that can be run by GAMS is approximately 5 processors and 50 tasks, while problems with at least 10 processors and 100 tasks can be easily run by the heuristic approach. The contributions of this thesis are: We defined the continuous task scheduling problem, proved it to be NP-complete, formulated it as an integer programming model and provided a constraint-relaxed and decomposed method, and developed a heuristic algorithm to solve the problem. The primary limitation of this research is that the accuracy of our heuristic algorithm is 99.5% of the exact model.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
