Articles via Databases
Articles via Journals
Online Catalog
E-books
Research & Information Literacy
Interlibrary loan
Theses & Dissertations
Collections
Policies
Services
About / Contact Us
Administration
Littman Architecture Library
This site will be removed in January 2019, please change your bookmarks.
This page will redirect to https://digitalcommons.njit.edu/dissertations/698 in 5 seconds

The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title: Some topics on deterministic scheduling problems
Author: Huo, Yumei
View Online: njit-etd2005-071
(xii, 136 pages ~ 7.5 MB pdf)
Department: Department of Computer Science
Degree: Doctor of Philosophy
Program: Computer Science
Document Type: Dissertation
Advisory Committee: Leung, Joseph Y-T. (Committee chair)
Czumaj, Artur (Committee member)
Gerbessiotis, Alexandros V. (Committee member)
Nakayama, Marvin K. (Committee member)
Pinedo, Michael (Committee member)
Date: 2005-05
Keywords: Scheduling
Online algorithm
Approximation algorithm
Dual criteria
NP-hard
Availability: Unrestricted
Abstract:

Sequencing and scheduling problems are motivated by allocation of limited resources over time. The goal is to find an optimal allocation where optimality is defined by some problem specific objectives.

This dissertation considers the scheduling of a set of ri tasks, with precedence constraints, on m >= 1 identical and parallel processors so as to minimize the makespan. Specifically, it considers the situation where tasks, along with their precedence constraints, are released at different times, and the scheduler has to make scheduling decisions without knowledge of future releases. Both preemptive and nonpreemptive schedules are considered. This dissertation shows that optimal online algorithms exist for some cases, while for others it is impossible to have one. The results give a sharp boundary delineating the possible and the impossible cases.

Then an O(n log n)-time implementation is given for the algorithm which solves P|pj = 1, rj, outtree| ΣCj and P|pmtn, pj=1,rj,outtree|ΣCj.

A fundamental problem in scheduling theory is that of scheduling a set of n unit-execution-time (UET) tasks, with precedence constraints, on m > 1 parallel and identical processors so as to minimize the mean flow time. For arbitrary precedence constraints, this dissertation gives a 2-approximation algorithm. For intrees, a 1.5-approximation algorithm is given.

Six dual criteria problems are also considered in this dissertation. Two open problems are first solved. Both problems are single machine scheduling problems with the number of tardy jobs as the primary criterion and with the total completion time and the total tardiness as the secondary criterion, respectively. Both problems are shown to be NP-hard. Then it focuses on bi-criteria scheduling problems involving the number of tardy jobs, the maximum weighted tardiness and the maximum tardiness. NP-hardness proofs are given for the scheduling problems when the number of tardy jobs is the primary criterion and the maximum weighted tardiness is the secondary criterion, or vice versa. It then considers complexity relationships between the various problems, gives polynomial-time algorithms for some special cases, and proposes fast heuristics for the general case.


If you have any questions please contact the ETD Team, libetd@njit.edu.

 
ETD Information
Digital Commons @ NJIT
Theses and DIssertations
ETD Policies & Procedures
ETD FAQ's
ETD home

Request a Scan
NDLTD

NJIT's ETD project was given an ACRL/NJ Technology Innovation Honorable Mention Award in spring 2003