Extended Local Clustering Organization with Rule-Based Neighborhood Search for Job-shop Scheduling Problem

被引：0

作者：

Tamura, Yasumasa ^{[1
]}

Iizuka, Hiroyuki ^{[1
]}

Yamamoto, Masahito ^{[1
]}

机构：

[1] Hokkaido Univ, Grad Sch Informat Sci & Technol, Sapporo, Hokkaido 060, Japan

来源：

PROCEEDINGS OF THE 18TH ASIA PACIFIC SYMPOSIUM ON INTELLIGENT AND EVOLUTIONARY SYSTEMS, VOL 2 | 2015年

关键词：

job-shop scheduling problem; local clustering organization; dispatching rules; kicking techniques;

D O I：

10.1007/978-3-319-13356-0_37

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Job-shop scheduling problem(JSP) is one of the hardest combinatorial optimization problems. Local clustering organization (LCO) is proposed by Furukawa et al. to solve such a combinatorial optimization problems as the metaheuristic algorithm. Its effectiveness for the JSP is verified by the comparison with genetic algorithm. However, since LCO is based on the greedy search, the solution is often trapped in local minima. To improve the problem, this study proposes a novel neighborhood search method using priority rules. This paper also shows the extended LCO integrated with the search method.

引用

页码：465 / 477

页数：13

共 16 条

[1] THE SHIFTING BOTTLENECK PROCEDURE FOR JOB SHOP SCHEDULING
ADAMS, J
BALAS, E
ZAWACK, D
[J]. MANAGEMENT SCIENCE, 1988, 34 (03) : 391 - 401
[2] [Anonymous], 1976, Computer and job-shop scheduling theory
[3] [Anonymous], 1984, Technical report
[4] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[5] BIERWIRTH C, 1995, OR SPEKTRUM, V17, P87, DOI 10.1007/BF01719250
[6] Conway R.W., 2003, Theory of scheduling
[7] French S., 1982, Sequencing and Scheduling
[8] Furukawa M, 2006, J JAPAN SOC PRECISIO, V72, P867
[9] Local Clustering Organization (LCO) Solving a Large-Scale TSP
Furukawa, Masashi
Watanabe, Michiko
Matsumura, Yusuke
[J]. JOURNAL OF ROBOTICS AND MECHATRONICS, 2005, 17 (05) : 560 - 567
[10] Garey M. R., 1976, Mathematics of Operations Research, V1, P117, DOI 10.1287/moor.1.2.117

← 1 2 →