2-MACHINE SHOP SCHEDULING PROBLEMS WITH BATCH PROCESSING

被引：31

作者：

KLEINAU, U

机构：

[1] Technische Universität Magdeburg, Fakultät für Mathematik Institut für Mathematische Optimierung, O- 3010 Magdeburg

来源：

MATHEMATICAL AND COMPUTER MODELLING | 1993年 / 17卷 / 06期

关键词：

D O I：

10.1016/0895-7177(93)90196-6

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We consider shop scheduling problems with group-technology. Groups of jobs are given to schedule them in a flow shop or open shop environment to minimize makespan. Setups have to be performed whenever two jobs of different groups are processed consecutively on the same machine. We show both problems to be NP-hard even in the two-machine case and give several algorithms for solving special cases of the open shop problem.

引用

页码：55 / 66

页数：12

共 6 条

[1]

ALBERS S, 1990, 131 U OSN PREPR

[2] SCHEDULING GROUPS OF JOBS IN THE 2-MACHINE FLOW-SHOP [J].

BAKER, KR .

MATHEMATICAL AND COMPUTER MODELLING, 1990, 13 (03) :29-36

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

DOBSON, G ;

KARMARKAR, US ;

RUMMEL, JL .

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

[4]

GONZALEZ T, 1976, J ACM, V23, P665, DOI 10.1145/321978.321985

[5] ON THE COMPLEXITY OF SCHEDULING WITH BATCH SETUP TIMES [J].

MONMA, CL ;

POTTS, CN .

OPERATIONS RESEARCH, 1989, 37 (05) :798-804

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

NADDEF, D ;

SANTOS, C .

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

← 1 →