Batch scheduling to minimize the weighted number of tardy jobs

被引：9
作者：
Erel, Erdal [1 ]
Ghosh, Jay B.
机构：
[1] Bilkent Univ, Fac Business Adm, TR-06800 Ankara, Turkey
[2] Apratech, LLC, Los Angeles, CA USA
来源：
COMPUTERS & INDUSTRIAL ENGINEERING | 2007年 / 53卷 / 03期
关键词：
scheduling; batch setup times; dynamic programming; approximation;
D O I：
10.1016/j.cie.2007.03.006
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
In this paper, we address a single-machine scheduling problem with due dates and batch setup times to minimize the weighted number of tardy jobs. We give a pseudo-polynomial dynamic program and a fully-polynomial approximation scheme for the case where the due dates are uniform within. a family. (C) 2007 Elsevier Ltd. All rights reserved.
引用
收藏
页码：394 / 400
页数：7
相关论文
共 9 条
[1]  
BRUNO J, 1978, SIAM J COMPUT, V7, P393, DOI 10.1137/0207031
[2]   FAST APPROXIMATION ALGORITHM FOR JOB SEQUENCING WITH DEADLINES [J].
GENS, GV ;
LEVNER, EV .
DISCRETE APPLIED MATHEMATICS, 1981, 3 (04) :313-318
[3]   SCHEDULING WITH BATCHING - MINIMIZING THE WEIGHTED NUMBER OF TARDY JOBS [J].
HOCHBAUM, DS ;
LANDY, D .
OPERATIONS RESEARCH LETTERS, 1994, 16 (02) :79-86
[4]  
Karp R. M., 1972, COMPLEXITY COMPUTER, P85, DOI DOI 10.1007/978-1-4684-2001-2_9
[5]   FUNCTIONAL EQUATION AND ITS APPLICATION TO RESOURCE ALLOCATION AND SEQUENCING PROBLEMS [J].
LAWLER, EL ;
MOORE, JM .
MANAGEMENT SCIENCE SERIES A-THEORY, 1969, 16 (01) :77-84
[6]   ON THE COMPLEXITY OF SCHEDULING WITH BATCH SETUP TIMES [J].
MONMA, CL ;
POTTS, CN .
OPERATIONS RESEARCH, 1989, 37 (05) :798-804
[7]  
Rote G., 1998, Acta Cybernetica, V13, P423
[8]   ALGORITHMS FOR SCHEDULING INDEPENDENT TASKS [J].
SAHNI, SK .
JOURNAL OF THE ACM, 1976, 23 (01) :116-127
[9]   SCHEDULING GROUPS OF JOBS ON A SINGLE-MACHINE [J].
WEBSTER, S ;
BAKER, KR .
OPERATIONS RESEARCH, 1995, 43 (04) :692-703
1