Existence Theorems for Scheduling to Meet Two Objectives

Dartmouth Technical Report PCS-TR99-347

	April M. Rasala

Date: June 1999

URL (compressed postscript): <http://www.cs.dartmouth.edu/reports/TR99-347.ps.Z> (280KB)

URL (PDF): <http://www.cs.dartmouth.edu/reports/TR99-347.pdf> (376KB)

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.