BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR99-347
ENTRY:: June 10, 1999
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Existence Theorems for Scheduling to Meet Two Objectives
TYPE:: Technical Report (paper)
REVISION:: 3
AUTHOR:: Rasala, April M.
DATE:: June 1999
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: Compressed Postscript at http://www.cs.dartmouth.edu/reports/TR99-347.ps.Z
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR99-347.pdf
ABSTRACT:: We will look at the existence of schedules which are simultaneously
near-optimal for two criteria.  First, we will present some techniques for
proving existence theorems, in a very general setting, for bicriterion
scheduling problems.  We will then use these techniques to prove existence
theorems for a large class of 
problems.  We will consider the relationship between objective functions based
on completion time, flow time, lateness and the number of on-time jobs.  We
will also present negative results first for the problem of simultaneously
minimizing the maximum flow time and average weighted flow time and second for
minimizing the maximum flow time and simultaneously maximizing the number of
on-time jobs.  In some cases we will also present lower bounds and algorithms
that approach our bicriterion existence theorems.  Finally we will improve upon
our general existence results in one  more specific environment.  
NOTE:: 
Undergraduate Honors Thesis. Advisor: Cliff Stein.
END:: ncstrl.dartmouthcs//TR99-347