WORST-CASE ERROR-BOUNDS FOR PARALLEL MACHINE SCHEDULING PROBLEMS WITH BOUNDED SEQUENCE-DEPENDENT SETUP TIMES

被引：29

作者：

OVACIK, IM

UZSOY, R

机构：

[1] School of Industrial Engineering, Purdue University, West Lafayette, IN 47907-1287

来源：

OPERATIONS RESEARCH LETTERS | 1993年 / 14卷 / 05期

基金：

美国国家科学基金会;

关键词：

SCHEDULING; PARALLEL MACHINES; SEQUENCE-DEPENDENT SETUP TIMES; HEURISTICS;

D O I：

10.1016/0167-6377(93)90089-Y

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider minimizing makespan (Cmax) and maximum lateness (Lmax) on parallel identical machines with sequence-dependent setup times. We show that the optimal schedule need not be a list schedule. Motivated by a practical scheduling problem, we study the class of problems where setup times are bounded by processing times and develop tight worst case error bounds for list scheduling algorithms to minimize Cmax and Lmax.

引用

页码：251 / 256

页数：6

共 11 条

[1]

Baker K. R., 1974, INTRO SEQUENCING SCH

[2]

Bitran G. R., 1990, Journal of Manufacturing and Operations Management, V3, P24

[3] SCHEDULING JOBS WITH RELEASE DATES AND TAILS ON IDENTICAL MACHINES TO MINIMIZE THE MAKESPAN [J].