A simple metaheuristic approach to the simultaneous scheduling of machines and automated guided vehicles

被引:99
作者
Deroussi, L.
Gourgand, M.
Tchernev, N.
机构
关键词
job-shop problem; metaheuristics; neighbouring systems; flexible manufacturing systems; automated guided vehicles;
D O I
10.1080/00207540600818286
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
In this paper we address the problem of simultaneous scheduling of machines and vehicles in flexible manufacturing systems. The studied problem is a job shop where the jobs have to be transported between the machines by automatic guided vehicles. In addition to the processing of jobs, we consider the transportation aspect as an integral part of the optimization process. To deal with this problem, we propose a new solution representation based on vehicles rather than machines. Each solution can thus be evaluated using a discrete event approach. An efficient neighbouring system is then described and implemented into three different metaheuristics: iterated local search, simulated annealing and their hybridisation. Computational results are presented for a benchmark of 40 literature instances. New upper bounds are found for 11 of them, showing the effectiveness of the presented approach.
引用
收藏
页码:2143 / 2164
页数:22
相关论文
共 32 条
[1]  
Abdelmaguid TF, 2004, INT J PROD RES, V42, P267, DOI [10.1080/0020754032000123579, 10.1080/0020754031000123579]
[2]  
[Anonymous], 1987, SIMULATED ANNEALING
[3]   A time window approach to simultaneous scheduling of machines and material handling system in an FMS [J].
Bilge, U ;
Ulusoy, G .
OPERATIONS RESEARCH, 1995, 43 (06) :1058-1070
[4]  
Blazewicz J., 1991, International Journal of Flexible Manufacturing Systems, V4, P5, DOI 10.1007/BF01325094
[5]   Metaheuristics in combinatorial optimization: Overview and conceptual comparison [J].
Blum, C ;
Roli, A .
ACM COMPUTING SURVEYS, 2003, 35 (03) :268-308
[6]  
BRUCKER P, 1998, SCHEDULING ALGORITHM
[7]  
DEROUSSI L, 2002, THESIS U CLERMONT FE
[8]  
DESAI R, COMBINING SIMULATED
[9]   CHARACTERIZATION OF AUTOMATIC GUIDED VEHICLE DISPATCHING RULES [J].
EGBELU, PJ ;
TANCHOCO, JMA .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 1984, 22 (03) :359-374
[10]   Design and operational issues in AGV-served manufacturing systems [J].
Ganesharajah, T ;
Hall, NG ;
Sriskandarajah, C .
ANNALS OF OPERATIONS RESEARCH, 1998, 76 (0) :109-154