Better bounds for online scheduling

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 pro cessing 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 onlin e algorithm that is 1.986-competitive. Karger, Phillips, and Torng [J. Algo rithms, 20 (1996), pp. 400-430] generalized the algorithm and proved an upp er 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 greater than or equal to 2. The algorithm is based on a new scheduling strategy, i.e., it is not a gene ralization of the approach by Bartal et al. Also, the algorithm has a simpl e structure. Furthermore, we develop a better lower bound. We prove that, f or general m, no deterministic online scheduling algorithm can be better th an 1.852-competitive.