On-line scheduling of unit time jobs with rejection: minimizing the total completion time

被引：64

作者：

Epstein, L

Noga, J

Woeginger, GJ

机构：

[1] Univ Twente, Dept Math, NL-7500 AE Enschede, Netherlands

[2] Interdisciplinary Ctr, Sch Comp & Med Sci, IL-46150 Herzliyya, Israel

[3] Calif State Univ Northridge, Dept Comp Sci, Northridge, CA 91330 USA

[4] Graz Tech Univ, Math Inst, A-1080 Graz, Austria

来源：

OPERATIONS RESEARCH LETTERS | 2002年 / 30卷 / 06期

关键词：

scheduling; on-line algorithm; competitive analysis; worst-case bounds;

D O I：

10.1016/S0167-6377(02)00160-8

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider on-line scheduling of unit time jobs on a single machine with job-dependent penalties. The jobs arrive on-line (one by one) and can be either accepted and scheduled, or be rejected at the cost of a penalty. The objective is to minimize the total completion time of the accepted jobs plus the sum of the penalties of the rejected jobs. We give an on-line algorithm for this problem with competitive ratio 1/2(2 + root3) approximate to 1.86602. Moreover, we prove that there does not exist an on-line algorithm with competitive ratio better than 1.63784. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：415 / 420

页数：6

共 6 条

[1] Multiprocessor scheduling with rejection [J].

Bartal, Y ;

Leonardi, S ;

Marchetti-Spaccamela, A ;

Sgall, J ;

Stougie, L .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (01) :64-78

[2]

ENGELS DW, 1998, LECT NOTES COMPUT SC, V1461, P490

[3]

HOOGEVEEN H, 2000, LECT NOTES COMPUTER, V1879, P268

[4]

Lawler E.L, 1993, HDB OPERATIONS RES M, V4, P445, DOI 10.1016/S0927-0507(05)80189-6

[5] Preemptive multiprocessor scheduling with rejection [J].

Seiden, SS .

THEORETICAL COMPUTER SCIENCE, 2001, 262 (1-2) :437-458

[6]

Sgall J, 1998, LECT NOTES COMPUT SC, V1442, P196, DOI 10.1007/BFb0029570

← 1 →