Scheduling uniform machines on-line requires nondecreasing speed ratios |
| |
Authors: | Arjen P. A. Vestjens |
| |
Affiliation: | (1) Department of Mathematics and Computing Science, Eindhoven University of Technology, Den Dolech 2, P.O. Box 513, 5600 MB Eindhoven, The Netherlands;(2) Present address: CQM, P.O. Box 414, 5600 AK Eindhoven, The Netherlands |
| |
Abstract: | We consider the following on-line scheduling problem. We have to schedulen independent jobs, wheren is unknown, onm uniform parallel machines so as to minimize the makespan; preemption is allowed. Each job becomes available at its release date, and this release date is not known beforehand; its processing requirement becomes known at its arrival. We show that if only a finite number of preemptions is allowed, there exists an algorithm that solves the problem if and only ifsi–1/si si/si+1 for alli = 2,,m – 1, wheresi denotes theith largest machine speed. We also show that if this condition is satisfied, then O(mn) preemptions are necessary, and we provide an example to show that this bound is tight. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V. |
| |
Keywords: | On-line algorithms Preemptive scheduling Uniform machines |
本文献已被 SpringerLink 等数据库收录! |
|