A NEW LOWER BOUND FOR THE JOB-SHOP SCHEDULING PROBLEM

被引：21

作者：

BRUCKER, P

JURISCH, B

机构：

[1] Universität Osnabrück, Osnabrück

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1993年 / 64卷 / 02期

关键词：

JOB-SHOP SCHEDULING; LOWER BOUND; SHORTEST PATH PROBLEM WITH OBSTACLES;

D O I：

10.1016/0377-2217(93)90174-L

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

A new lower bound for the job-shop scheduling problem is developed. This lower bound is based on a two-job relaxation which can be solved efficiently by using geometeric methods. Computational experiments show that the new lower bound improves the classical lower bound if the ratio between the number of machines and the number of jobs is large.

引用

收藏

页码：156 / 167

页数：12

相关论文

共 15 条

[1] THE SHIFTING BOTTLENECK PROCEDURE FOR JOB SHOP SCHEDULING [J].

ADAMS, J ;

BALAS, E ;

ZAWACK, D .

MANAGEMENT SCIENCE, 1988, 34 (03) :391-401

[2] A GRAPHICAL APPROACH TO PRODUCTION SCHEDULING PROBLEMS [J].

AKERS, SB .

OPERATIONS RESEARCH, 1956, 4 (02) :244-245

[3] JOB-SHOP SCHEDULING WITH MULTIPURPOSE MACHINES [J].

BRUCKER, P ;

SCHLIE, R .

COMPUTING, 1990, 45 (04) :369-375

[4] MINIMIZING MAXIMUM LATENESS IN A 2-MACHINE UNIT-TIME JOB SHOP [J].

BRUCKER, P .

COMPUTING, 1981, 27 (04) :367-370

[5] AN EFFICIENT ALGORITHM FOR THE JOB-SHOP PROBLEM WITH 2 JOBS [J].

BRUCKER, P .

COMPUTING, 1988, 40 (04) :353-359

[6] AN ALGORITHM FOR SOLVING THE JOB-SHOP PROBLEM [J].

CARLIER, J ;

PINSON, E .

MANAGEMENT SCIENCE, 1989, 35 (02) :164-176

[7]

Fisher H., 1963, IND SCHEDULING, P225

[8] A GEOMETRIC MODEL AND A GRAPHICAL ALGORITHM FOR A SEQUENCING PROBLEM [J].

HARDGRAVE, WW ;

NEMHAUSER, GL .

OPERATIONS RESEARCH, 1963, 11 (06) :889-900

[9] AN EFFICIENT OPTIMAL ALGORITHM FOR THE 2-MACHINES UNIT-TIME JOBSHOP SCHEDULE-LENGTH PROBLEM [J].

HEFETZ, N ;

ADIRI, I .

MATHEMATICS OF OPERATIONS RESEARCH, 1982, 7 (03) :354-360

[10]

Jackson J.R., 1956, NAV RES LOGIST Q, V3, P201, DOI [10.1002/nav.3800030307, DOI 10.1002/NAV.3800030307]