返回Google圖書搜尋

Better Bounds for Online Scheduling

出版	MPI Informatik, Bibliothek & Dokumentation, 1997
URL	http://books.google.com.hk/books?id=gU6MYgEACAAJ&hl=&source=gbs_api

註釋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, Fiat, Karloff and Vohra [3] gave a deterministic online algorithm that is 1.986-competitive. Karger, Philips and Torng [11] 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 it [sic] equal to 1.837. In this paper we present an improved deterministic online scheduling algorithm that is 1.923-competitive, for all m[> or =]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."