On-line scheduling with extendable working time on a small number of machines |
| |
Authors: | Deshi Ye |
| |
Affiliation: | a Department of Mathematics, Zhejiang University, Hangzhou 310027, People's Republic of China b Institut für Informatik und Praktische Mathematik, Universität Kiel, Olshausenstrasse 40, 24098 Kiel, Germany |
| |
Abstract: | Speranza and Tuza Ann. Oper. Res. 86 (1999) 494-506] studied the on-line problem of scheduling jobs on m identical machines with extendable working time. In this problem, each machine is assumed to have an identical regular working time, which can be extended if necessary. The working time of a machine is the larger one between its regular working time and the total processing time of jobs assigned to it. The objective is to minimize the total working time of machines. They presented an on-line algorithm Hx, with a competitive ratio at most 1.228 for any number of machines by choosing an appropriate parameter x. In this paper we consider a small number of machines. The best choices of x are given for m=2,3,4 and the tight bounds, 7/6, 11/9 and 19/16, respectively, are proved. Among them, the algorithm for m=2 is best possible. We then derive a new algorithm for m=3 with a competitive ratio 7/6. |
| |
Keywords: | Analysis of algorithms On-line scheduling Competitive ratio |
本文献已被 ScienceDirect 等数据库收录! |
|