On minimizing total tardiness in a serial batching problem

被引：6

作者：

Baptiste, P ^{[1
]}

Jouglet, A ^{[1
]}

机构：

[1] Univ Technol Compiegne, CNRS, UMR 6599, HeuDiaSyC,Ctr Rech Royallieu, F-60205 Compiegne, France

来源：

RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH | 2001年 / 35卷 / 01期

关键词：

scheduling; batching; dynamic programming; total tardiness;

D O I：

10.1051/ro:2001105

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We study the problem of scheduling jobs on a serial batching machine to minimize total tardiness. Jobs of the same batch start and are completed simultaneously and the length of a batch equals the sum of the processing times of its jobs. When a new batch starts, a constant setup time s occurs. This problem 1\s-batch\SigmaT(i) is known to be NP-Hard in the ordinary sense. In this paper we show that it is solvable in pseudopolynomial time by dynamic programming.

引用

页码：107 / 115

页数：9

共 14 条

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

ALBERS, S ;

BRUCKER, P .

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

[2]

BAPTISTE P, 1999, BATCHING IDENTICAL J

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

Brucker P., 1995, SCHEDULING ALGORITHM

[6]

BRUCKER P, 1996, MATH METHOD OPER RES, V43, P1

[7]

Brucker P., Complexity results for scheduling problems

[8]

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

[9] MINIMIZING TOTAL TARDINESS ON ONE MACHINE IS NP-HARD [J].

DU, JZ ;

LEUNG, JYT .

MATHEMATICS OF OPERATIONS RESEARCH, 1990, 15 (03) :483-495

[10]

DUPONT L, IN PRESS TSI, V10

← 1 2 →