Minimizing makespan on a single batching machine with release times and non-identical job sizes

被引：66

作者：

Li, SG ^{[1
]}

Li, GJ

Wang, XL

Liu, QM

机构：

[1] Yantai Univ, Dept Math & Informat Sci, Yantai 264005, Peoples R China

[2] Shandong Univ, Sch Math & Syst Sci, Jinan 250100, Peoples R China

[3] Chinese Acad Sci, Inst Software, Beijing 100080, Peoples R China

[4] Yantai Normal Univ, Sch Comp Sci & Technol, Yantai 264025, Peoples R China

来源：

OPERATIONS RESEARCH LETTERS | 2005年 / 33卷 / 02期

关键词：

approximation algorithms; scheduling; batch processing; makespan; release times;

D O I：

10.1016/j.orl.2004.04.009

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the problem of scheduling jobs with release times and non-identical job sizes on a single batching machine; our objective is to minimize makespan. We present an approximation algorithm with worst-case ratio 2 + epsilon, where epsilon > 0 can be made arbitrarily small. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：157 / 164

页数：8

共 12 条

[1]

AFRATI F, 1999, P 40 ANN IEEE S FDN, P32

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[3]

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

[4]

2-R

[5]

Co man Jr EG, 1996, APPROXIMATION ALGORI, P46

[6]

DENG X, IN PRESS J COMBIN OP

[7]

Deng XT, 2000, LECT NOTES COMPUT SC, V1741, P153

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

LEE, CY ;

UZSOY, R ;

MARTINVEGA, LA .

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

[9]

LEE CY, 1996, MINIMIZING MAKESPAN

[10]

LENSTRA JK, 1995, COMPUTING NEAR OPTIM

← 1 2 →