Early/tardy scheduling with sequence dependent setups on uniform parallel machines

被引：84

作者：

Balakrishnan, N ^{[1
]}

Kanet, JJ ^{[1
]}

Sridharan, V ^{[1
]}

机构：

[1] Clemson Univ, Dept Management, Clemson, SC 29634 USA

来源：

COMPUTERS & OPERATIONS RESEARCH | 1999年 / 26卷 / 02期

关键词：

scheduling; parallel machines; earliness-tardiness problem;

D O I：

10.1016/S0305-0548(98)00051-3

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We consider the problem of scheduling N jobs on M parallel machines that operate at different speeds (known as uniform parallel machines), to minimize the sum of earliness and tardiness costs. Jobs are assumed to arrive in a dynamic albeit deterministic manner, and have nonidentical due dates. Violations of due dates result in earliness or tardiness penalties that may be different for different jobs. Setup times are job-sequence dependent and may be different on different machines based on the characteristics of the machines. For this problem, we present a mixed integer formulation that has substantially fewer zero-one variables than typical formulations for scheduling problems of this type. We present our computational experience in using this model to solve small sized problems, and discuss solution approaches for solving larger problems. (C) 1998 Elsevier Science Ltd. All rights reserved.

引用

页码：127 / 141

页数：15

共 30 条

[1] Scheduling jobs with different, job-dependent earliness and tardiness penalties using the SLK method [J].

Adamopoulos, GI ;

Pappis, CP .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 88 (02) :336-344

[2] MINIMIZING THE WEIGHTED SUM OF LATE AND EARLY COMPLETION PENALTIES IN A SINGLE-MACHINE [J].

AHMED, MU ;

SUNDARARAGHAVAN, PS .

IIE TRANSACTIONS, 1990, 22 (03) :288-290

[3]

[Anonymous], LINEAR INTEGER PROGR

[4] MINIMIZING MEAN SQUARED DEVIATION OF COMPLETION TIMES ABOUT A COMMON DUE DATE [J].

BAGCHI, U ;

SULLIVAN, RS ;

CHANG, YL .

MANAGEMENT SCIENCE, 1987, 33 (07) :894-906

[5] SEQUENCING WITH EARLINESS AND TARDINESS PENALTIES - A REVIEW [J].

BAKER, KR ;

SCUDDER, GD .

OPERATIONS RESEARCH, 1990, 38 (01) :22-36

[6]

Baker KR., 1974, Introduction to Sequencing and Scheduling

[7]

Blazewicz J., 1993, SCHEDULING COMPUTER

[8] MINMAX EARLINESS TARDINESS SCHEDULING IN IDENTICAL PARALLEL MACHINE SYSTEM USING GENETIC ALGORITHMS [J].

CHENG, RW ;

GEN, MS ;

TOZAWA, T .

COMPUTERS & INDUSTRIAL ENGINEERING, 1995, 29 :513-517

[9]

CHENG TCE, 1994, J OPER RES SOC, V45, P685, DOI 10.1057/jors.1994.106

[10] Parallel-machine scheduling with controllable processing times [J].

Cheng, TCE ;

Chen, ZL ;

Li, CL .

IIE TRANSACTIONS, 1996, 28 (02) :177-180

← 1 2 3 →