SCHEDULING WITH BATCHING - MINIMIZING THE WEIGHTED NUMBER OF TARDY JOBS

被引：43

作者：

HOCHBAUM, DS ^{[1
]}

LANDY, D ^{[1
]}

机构：

[1] UNIV CALIF BERKELEY,SCH BUSINESS ADM,BERKELEY,CA 94720

来源：

OPERATIONS RESEARCH LETTERS | 1994年 / 16卷 / 02期

关键词：

SEMICONDUCTOR MANUFACTURING; PSEUDO-POLYNOMIAL ALGORITHMS; BATCH SCHEDULING;

D O I：

10.1016/0167-6377(94)90063-9

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The weighted tardiness with batching (WTB) problem can be briefly described as follows: given n jobs, each with a processing time, a weight, and a due date, and given a batch setup time, find a sequence of batches that minimizes the weighted number of tardy jobs. We show that the decision version of WTB is NP-complete, but that it can be solved in pseudo-polynomial time by a dynamic programming algorithm. We also analyze various restricted versions of the problem generated by requiring that one or more of the job parameters (weight, processing time, or due date) is the same for all jobs. For each such version of the problem, we prove NP-completeness or provide a polynomial algorithm.

引用

页码：79 / 86

页数：8

共 10 条

[1] THE COMPLEXITY OF ONE-MACHINE BATCHING PROBLEMS [J].

ALBERS, S ;

BRUCKER, P .

DISCRETE APPLIED MATHEMATICS, 1993, 47 (02) :87-107

[2]

BRUCKER PJ, 1991, 1991 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION, VOLS 1-3, P1778, DOI 10.1109/ROBOT.1991.131880

[3]

BRUNO J, 1978, SIAM J COMPUT, V7, P393, DOI 10.1137/0207031

[4]

Coffman E. G. Jr., 1990, Annals of Operations Research, V26, P135, DOI 10.1007/BF02248589

[5] OPTIMAL SCHEDULING OF PRODUCTS WITH 2 SUBASSEMBLIES ON A SINGLE-MACHINE [J].

COFFMAN, EG ;

NOZARI, A ;

YANNAKAKIS, M .

OPERATIONS RESEARCH, 1989, 37 (03) :426-436

[6] BATCHING TO MINIMIZE FLOW TIMES ON ONE MACHINE [J].

DOBSON, G ;

KARMARKAR, US ;

RUMMEL, JL .

MANAGEMENT SCIENCE, 1987, 33 (06) :784-799

[7]

Karp R.M., 1972, COMPLEXITY COMPUTER, P85

[8] 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

[9] ONE-PASS BATCHING ALGORITHMS FOR THE ONE-MACHINE PROBLEM [J].

NADDEF, D ;

SANTOS, C .

DISCRETE APPLIED MATHEMATICS, 1988, 21 (02) :133-145

[10] A POLYNOMIAL ALGORITHM FOR A ONE MACHINE BATCHING PROBLEM [J].

SHALLCROSS, DF .

OPERATIONS RESEARCH LETTERS, 1992, 11 (04) :213-218

← 1 →