Windows scheduling of arbitrary-length jobs on multiple machines |
| |
Authors: | Amotz Bar-Noy Richard E Ladner Tami Tamir Tammy VanDeGrift |
| |
Affiliation: | (1) Computer & Information Science Department, Brooklyn College, 2900 Bedford Ave., Brooklyn, NY 11210, USA;(2) Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WA 98195, USA;(3) School of Computer Science, The Interdisciplinary Center, Herzliya, Israel;(4) Electrical Engineering & Computer Science, University of Portland, 5000 N. Willamette Blvd., Portland, OR 97203, USA |
| |
Abstract: | The generalized windows scheduling problem for n jobs on multiple machines is defined as follows: Given is a sequence, I=〈(w
1,ℓ
1),(w
2,ℓ
2),…,(w
n
,ℓ
n
)〉 of n pairs of positive integers that are associated with the jobs 1,2,…,n, respectively. The processing length of job i is ℓ
i
slots where a slot is the processing time of one unit of length. The goal is to repeatedly and non-preemptively schedule
all the jobs on the fewest possible machines such that the gap (window) between two consecutive beginnings of executions of
job i is at most w
i
slots. This problem arises in push broadcast systems in which data are transmitted on multiple channels. The problem is NP-hard
even for unit-length jobs and a (1+ε)-approximation algorithm is known for this case by approximating the natural lower bound W(I)=?i=1n(1/wi)W(I)=\sum_{i=1}^{n}(1/w_{i}). The techniques used for approximating unit-length jobs cannot be extended for arbitrary-length jobs mainly because the optimal
number of machines might be arbitrarily larger than the generalized lower bound W(I)=?i=1n(li/wi)W(I)=\sum_{i=1}^{n}(\ell_{i}/w_{i}). The main result of this paper is an 8-approximation algorithm for the WS problem with arbitrary lengths using new methods,
different from those used for the unit-length case. The paper also presents another algorithm that uses 2(1+ε)W(I)+logw
max machines and a greedy algorithm that is based on a new tree representation of schedules. The greedy algorithm is optimal
for some special cases, and computational experiments show that it performs very well in practice. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|