Fast approximation algorithms for job scheduling with processing set restrictions

被引:22
作者
Huo, Yumei [2 ]
Leung, Joseph Y-T [1 ]
机构
[1] New Jersey Inst Technol, Dept Comp Sci, Newark, NJ 07102 USA
[2] CUNY, Dept Comp Sci, Staten Isl, NY 10314 USA
关键词
Tree-hierarchical processing set; Inclusive processing set; Nested processing set; Makespan minimization; Polynomial-time approximation algorithm; NP-hard; Nonpreemptive scheduling;
D O I
10.1016/j.tcs.2010.08.008
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider the problem of scheduling n independent jobs on m parallel machines, where the machines differ in their functionality but not in their processing speeds. Each job has a restricted set of machines to which it can be assigned, called its processing set. Preemption is not allowed. Our goal is to minimize the makespan of the schedule. We study two variants of this problem: (1) the case of tree-hierarchical processing set and (2) the case of nested processing set. We first give a fast algorithm for the case of tree-hierarchical processing set with a worst-case bound of 4/3, which is better than the best known algorithm whose worst-case bound is 2. We then give a more complicated algorithm for the case of nested processing set with a worst-case bound of 5/3, which is better than the best known algorithm whose worst-case bound is 7/4. In both cases, we will give examples achieving the worst-case bounds. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码:3947 / 3955
页数:9
相关论文
共 16 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[2]   On-line load balancing in a hierarchical server topology [J].
Bar-Noy, A ;
Freund, A ;
Naor, JS .
SIAM JOURNAL ON COMPUTING, 2001, 31 (02) :527-549
[3]  
Chen B., 1998, Handbook of Combinatorial Optimization, P1493, DOI [DOI 10.1007/978-1-4613-0303-9_25, 10.1007/978-1-4613-0303-925, DOI 10.1007/978-1-4613-0303-925]
[4]  
EPSTEIN L, INT J PRODU IN PRESS
[5]   Scheduling unit length jobs with parallel nested machine processing set restrictions [J].
Glass, CA ;
Mills, HR .
COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (03) :620-638
[6]   Parallel machine scheduling with job assignment restrictions [J].
Glass, Celia A. ;
Kellerer, Hans .
NAVAL RESEARCH LOGISTICS, 2007, 54 (03) :250-257
[7]   USING DUAL APPROXIMATION ALGORITHMS FOR SCHEDULING PROBLEMS - THEORETICAL AND PRACTICAL RESULTS [J].
HOCHBAUM, DS ;
SHMOYS, DB .
JOURNAL OF THE ACM, 1987, 34 (01) :144-162
[8]   Parallel machine scheduling with nested processing set restrictions [J].
Huo, Yumei ;
Leung, Joseph Y-T .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 204 (02) :229-236
[9]   Parallel machine scheduling under a grade of service provision [J].
Hwang, HC ;
Chang, SY ;
Lee, K .
COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (12) :2055-2061
[10]  
Kafura D. G., 1977, SIAM Journal on Computing, V6, P167, DOI 10.1137/0206014