This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Hall, N. G. Articles by Potts, C. N. Search for Related Content

Online Scheduling with Known Arrival Times

Department of Management Sciences and 3D Laboratory, The Ohio State University, Columbus, Ohio 43210
Department of Integrated Systems Engineering and 3D Laboratory, The Ohio State University, Columbus, Ohio 43210
School of Mathematics, University of Southampton, Southampton SO17 1BJ, United Kingdom
hall_33{at}fisher.osu.edu, http://fisher.osu.edu/hall_33
posner.1{at}osu.edu, www.iwse.osu.edu/ISEFaculty/Posner/Posner.htm
C.N.Potts{at}soton.ac.uk, www.soton.ac.uk/maths/people/profiles/or/cnp1.html

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 nonpreemptive 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. We analyze two practically motivated special cases where the potential job arrival times have a special structure. When there are many equally spaced potential job arrival times, the competitive ratio of our online algorithm approaches the best possible competitive ratio of 2 for the classical online problem.

Key Words: machine scheduling; online algorithm; total weighted completion time; competitive analysis
History: Received: October 12, 2006; revision received: April 28, 2008;