Online Scheduling with Known Arrival Time
<--
Return to the list
Date: 10-26-2006
Start Time:
4:00pm
End Time: 5:30pm
Speaker: Chris Potts, School of Mathematics, University of Southampton
Location: SindeBand East, 414 Schapiro CEPSR Morningside Campus
Abstract
We consider
an online scheduling environment
where decisions are made without
knowledge of the data of jobs that
may arrive later. However,
additional jobs can only arrive at
known future times. This environment
interpolates between the classical
offline and online scheduling
environments, and approaches the
classical online environment when
there are many equally spaced
potential job arrival times. The
objective is to minimize the sum of
weighted completion times, a widely
used measure of work-in-process
inventory cost and customer service.
For a non-preemptive single
machine environment, we show that a
lower bound on the competitive ratio
of any online algorithm is the
solution of a mathematical program.
This lower bound is between
(1+sqrt{5})/2 and 2, with the exact
value depending on the potential job
arrival times. We also provide a
"best possible" online scheduling
algorithm, and show that its
competitive ratio matches this lower
bound. A key element in establishing
this result is a system of equations
and inequalities that characterizes
the schedule delivered by our online
algorithm for an arbitrary problem
instance. Then we use this system to construct a
feasible solution to the
mathematical program that
establishes the lower bound. This
proof technique has potential
application to other online
scheduling problems. We analyze two
practically motivated special cases
where the potential job arrival
times have a special structure.
