Scheduling one batch processor subject to job release dates

被引：61

作者：

Liu, ZH ^{[1
]}

Yu, WC ^{[1
]}

机构：

[1] E China Univ Sci & Technol, Inst Appl Math, Shanghai 200237, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2000年 / 105卷 / 1-3期

关键词：

scheduling; batch processor; NP-hardness; heuristic;

D O I：

10.1016/S0166-218X(00)00181-5

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, we consider the problem of scheduling jobs with release dates on a single-batch processor in order to minimize the makespan. This problem is proved to be NP-hard even for the case with two distinct release dates. Then a pseudopolynomial algorithm is presented for the case with a fixed number of release dates. Finally, a greedy heuristic for the general problem is shown to have the best-performance bound 2. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：129 / 136

页数：8

共 8 条

[1]

Brucker P., 1998, Journal of Scheduling, V1, P31, DOI 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO

[2]

2-R

[3] EFFICIENT SCHEDULING ALGORITHMS FOR A SINGLE BATCH PROCESSING MACHINE [J].

IKURA, Y ;

GIMPLE, M .

OPERATIONS RESEARCH LETTERS, 1986, 5 (02) :61-65

[4]

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

[5] EFFICIENT ALGORITHMS FOR SCHEDULING SEMICONDUCTOR BURN-IN OPERATIONS [J].

LEE, CY ;

UZSOY, R ;

MARTINVEGA, LA .

OPERATIONS RESEARCH, 1992, 40 (04) :764-775

[6]

LEE CY, 1996, MINIMIZING MAKESPAN

[7]

LIU Z, 1997, THESIS E CHINA U SCI

[8] SCHEDULING GROUPS OF JOBS ON A SINGLE-MACHINE [J].

WEBSTER, S ;

BAKER, KR .

OPERATIONS RESEARCH, 1995, 43 (04) :692-703

← 1 →