THE SHIFTING BOTTLENECK PROCEDURE FOR JOB SHOP SCHEDULING

被引：964

作者：

ADAMS, J

BALAS, E

ZAWACK, D

机构：

[1] CARNEGIE MELLON UNIV,GRAD SCH IND ADM,PITTSBURGH,PA 15213

[2] AMER AIRLINES,NEW YORK,NY

来源：

MANAGEMENT SCIENCE | 1988年 / 34卷 / 03期

关键词：

DATA PROCESSING - Critical Path Analysis - MACHINE SHOPS - Scheduling - MATHEMATICAL TECHNIQUES - Graph Theory - PRODUCTION CONTROL - Scheduling;

D O I：

10.1287/mnsc.34.3.391

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We describe an approximation method for solving the minimum makespan problem of job shop scheduling. It sequences the machines one by one, successively, taking each time the machine identified as a bottleneck among the machines not yet sequenced. Every time after a new machine is sequenced, all previously established sequences are locally reoptimized. Both the bottleneck identification and the local reoptimization procedures are based on repeatedly solving certain one-machine scheduling problems. Besides this straight version of the Shifting Bottleneck Procedure, we have also implemented a version that applies the procedure to the nodes of a partial search tree.

引用

页码：391 / 401

页数：11

共 13 条

[1]

Baker K., 1974, INTRO SEQUENCING SCH

[2] MACHINE SEQUENCING VIA DISJUNCTIVE GRAPHS - AN IMPLICIT ENUMERATION ALGORITHM [J].