APPROXIMATION ALGORITHMS FOR SINGLE-MACHINE SEQUENCING WITH DELIVERY TIMES AND UNIT BATCH SET-UP TIMES

被引：19

作者：

ZDRZALKA, S

机构：

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

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1991年 / 51卷 / 02期

关键词：

SEQUENCING; BATCH SET-UP TIMES; APPROXIMATION ALGORITHM; WORST-CASE ANALYSIS;

D O I：

10.1016/0377-2217(91)90250-Y

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The single machine sequencing problem is considered in which a set of n jobs is divided into batches, each job has a processing time and a delivery time, and there is a unit set-up time associated with switching from jobs in one batch to those in another. The objective is to find a sequence of jobs which minimizes the time by which all jobs are delivered. Three efficient approximation algorithms are described and analyzed. They guarantee worst-case performance bounds of n - 1, 2 and 5/3.

引用

页码：199 / 209

页数：11