ANALYSIS OF APPROXIMATION ALGORITHMS FOR SINGLE-MACHINE SCHEDULING WITH DELIVERY TIMES AND SEQUENCE INDEPENDENT BATCH SETUP TIMES

被引：28

作者：

ZDRZALKA, S

机构：

[1] Technical University of Wrocław, Institute of Engineering Cybernetics, 50-370 Wrocław

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1995年 / 80卷 / 02期

关键词：

SEQUENCING; BATCH SETUP TIMES; WORST-CASE ANALYSIS;

D O I：

10.1016/0377-2217(93)E0160-Y

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The paper deals with the single-machine scheduling problem in which each job has a processing time and a delivery time, a set of jobs is divided into batches and a setup time is incurred whenever there is a switch from a job in one batch to a job in another batch. The objective is to find a sequence of jobs which minimizes the time by which all jobs are delivered. Two approximation algorithms with the worst-case performance ratio of 3/2 are given for the case with sequence independent batch setup times. Results of computational experiments are also provided.

引用

页码：371 / 380

页数：10

共 6 条

[1]

BRUNO J, 1979, SIAM J COMPUT, V7, P393

[2]

CHEN B, 1991, IN PRESS SIAM J COMP

[3]

LAWLER EL, 1989, HDB OPERATIONS RES M, V4

[4] ON THE COMPLEXITY OF SCHEDULING WITH BATCH SETUP TIMES [J].