BATCH DELIVERY SCHEDULING ON A SINGLE-MACHINE

被引：14

作者：

CHENG, TCE ^{[1
]}

GORDON, VS ^{[1
]}

机构：

[1] BYELORUSSIAN ACAD SCI, INST ENGN CYBERNET, MINSK, BELARUS

来源：

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY | 1994年 / 45卷 / 10期

关键词：

SCHEDULING; SEQUENCING; BATCHING;

D O I：

10.1038/sj/jors/0451012

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The problem of partitioning a set of independent and simultaneously available jobs into batches and sequencing them for processing on a single machine is presented. Jobs in the same batch are to be delivered together, upon completion of the last job in the batch. Jobs finished before this time have to wait until delivery. There are a delivery cost depending on the number of batches formed and an earliness cost for jobs finished before delivery. The dynamic programming approach to minimizing the total cost is considered, yielding two pseudopolynomial algorithms when the number of batches has a fixed upper bound. A polynomial algorithm for a special case of the problem is also presented.

引用

页码：1211 / 1215

页数：5

共 12 条

[1]

ALBERS S, 1994, IN PRESS DISCRETE AP

[2]

BELLMAN R, 1963, APPLIED DYNAMIC PROG

[3]

CHENG TCE, 1993, ASIA PAC J OPER RES, V10, P145

[4] SURVEY OF SCHEDULING RESEARCH INVOLVING DUE DATE DETERMINATION DECISIONS [J].

CHENG, TCE ;

GUPTA, MC .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1989, 38 (02) :156-166

[5]

COFFMAN EG, 1988, BATCH SIZING SEQUENC

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

DOBSON, G ;

KARMARKAR, US ;

RUMMEL, JL .

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

[7] BATCHING TO MINIMIZE FLOW TIMES ON PARALLEL HETEROGENEOUS MACHINES [J].

DOBSON, G ;

KARMARKAR, US ;

RUMMEL, JL .

MANAGEMENT SCIENCE, 1989, 35 (05) :607-613

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

Rothkopf M. H., 1966, MANAGE SCI, V12, P437, DOI [DOI 10.1287/MNSC.12.5.437, 10.1287/mnsc.12.5.437]

← 1 2 →