Better Bounds for Online Scheduling
Author:
- Susanne AlbersSASusanne Albers
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 29 (2) , 459-473
Abstract
We study a classical problem in online scheduling. A sequence of jobs must be scheduled on m identical parallel machines. As each job arrives, its processing time is known. The goal is to minimize the makespan. Bartal et al. [ J. Comput. System Sci., 51 (1995), pp. 359--366] gave a deterministic online algorithm that is 1.986-competitive. Karger, Phillips, and Torng [ J. Algorithms, 20 (1996), pp. 400--430] generalized the algorithm and proved an upper bound of 1.945. The best lower bound currently known on the competitive ratio that can be achieved by deterministic online algorithms is equal to 1.837. In this paper we present an improved deterministic online scheduling algorithm that is 1.923-competitive; for all $m\geq 2$. The algorithm is based on a new scheduling strategy, i.e., it is not a generalization of the approach by Bartal et al. Also, the algorithm has a simple structure. Furthermore, we develop a better lower bound. We prove that, for general m, no deterministic online scheduling algorithm can be better than 1.852-competitive.
Keywords
This publication has 8 references indexed in Scilit:
- On-line routing of virtual circuits with applications to load balancing and machine schedulingJournal of the ACM, 1997
- A Better Algorithm for an Ancient Scheduling ProblemJournal of Algorithms, 1996
- New Algorithms for an Ancient Scheduling ProblemJournal of Computer and System Sciences, 1995
- New lower and upper bounds for on-line schedulingOperations Research Letters, 1994
- A better lower bound for on-line schedulingInformation Processing Letters, 1994
- An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List SchedulingSIAM Journal on Computing, 1993
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985
- Bounds for Certain Multiprocessing AnomaliesBell System Technical Journal, 1966