A BRANCH-AND-BOUND ALGORITHM FOR THE JOB-SHOP SCHEDULING PROBLEM

被引：258

作者：

BRUCKER, P

JURISCH, B

SIEVERS, B

机构：

[1] FB 6 Mathematik, Universität Osnabrück

来源：

DISCRETE APPLIED MATHEMATICS | 1994年 / 49卷 / 1-3期

关键词：

JOB-SHOP SCHEDULING; BRANCH AND BOUND METHOD;

D O I：

10.1016/0166-218X(94)90204-6

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A fast branch and bound algorithm for the job-shop scheduling problem has been developed. Among other hard problems it solves the 10 x 10 benchmark problem which has been open for more than 20 years. We will give a complete description of this algorithm and will present computational results.

引用

收藏

页码：107 / 127

页数：21

相关论文

共 17 条

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

ADAMS, J ;

BALAS, E ;

ZAWACK, D .

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

[2]

Applegate D., 1991, ORSA Journal on Computing, V3, P149, DOI 10.1287/ijoc.3.2.149

[3]

BOUMA RW, 1982, THESIS U ROTERDAM

[4] JOB-SHOP (C-CODES) [J].

BRUCKER, P ;

JURISCH, B ;

SIEVERS, B .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1992, 57 (01) :132-133

[5] A NEW LOWER BOUND FOR THE JOB-SHOP SCHEDULING PROBLEM [J].

BRUCKER, P ;

JURISCH, B .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1993, 64 (02) :156-167

[6] THE ONE-MACHINE SEQUENCING PROBLEM [J].

CARLIER, J .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1982, 11 (01) :42-47

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

CARLIER, J ;

PINSON, E .

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

[8]

Carlier J., 1990, Annals of Operations Research, V26, P269

[9] A BLOCK APPROACH FOR SINGLE-MACHINE SCHEDULING WITH RELEASE DATES AND DUE DATES [J].

GRABOWSKI, J ;

NOWICKI, E ;

ZDRZALKA, S .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1986, 26 (02) :278-285

[10]

GRABOWSKI J, 1988, PRZEGLAD STATYSTYCZN, V45, P67