Minimizing Number of Tardy Jobs on a Batch Processing Machine with Incompatible Job Families

被引：6

作者：

Liu, Lili ^{[1
]}

Zhang, Feng ^{[1
]}

机构：

[1] Second Polytech Univ, Sch Sci, Pudong Shanghai 201209, Peoples R China

来源：

2008 ISECS INTERNATIONAL COLLOQUIUM ON COMPUTING, COMMUNICATION, CONTROL, AND MANAGEMENT, VOL 3, PROCEEDINGS | 2008年

关键词：

D O I：

10.1109/CCCM.2008.107

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper we prove that the problem of scheduling jobs with incompatible job families on a single batch processing machine to minimize number of tardy jobs is strongly (unary) NP-hard. We then develop a dynamic programming algorithm for minimizing weighted number of tardy jobs on a single batch processing machine with incompatible job families.

引用

页码：277 / 280

页数：4

共 7 条

[1]

Brucker P., 1998, Journal of Scheduling, V1, P31, DOI 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO

[2]

2-R

[3] EFFICIENT SCHEDULING ALGORITHMS FOR A SINGLE BATCH PROCESSING MACHINE [J].

IKURA, Y ;

GIMPLE, M .

OPERATIONS RESEARCH LETTERS, 1986, 5 (02) :61-65

[4] Minimizing number of tardy jobs on a batch processing machine with incompatible job families [J].

Jolai, F .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2005, 162 (01) :184-190

[5] Minimizing total tardiness on a batch processing machine with incompatible job families [J].

Mehta, SV ;

Uzsoy, R .

IIE TRANSACTIONS, 1998, 30 (02) :165-178

[6] Minimizing total weighted tardiness on a single batch process machine with incompatible job families [J].

Perez, IC ;

Fowler, JW ;

Carlyle, WM .

COMPUTERS & OPERATIONS RESEARCH, 2005, 32 (02) :327-341

[7] SCHEDULING BATCH PROCESSING MACHINES WITH INCOMPATIBLE JOB FAMILIES [J].

UZSOY, R .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1995, 33 (10) :2685-2708

← 1 →