Iterated greedy insertion approaches for the flexible job shop scheduling problem with transportation times constraint

被引:2
作者
Bekkar A. [1 ]
Belalem G. [1 ]
Beldjilali B. [1 ]
机构
[1] Department of Computer Science, Faculty of Exact and Applied Sciences, University of Oranm, 1 Ahmed Ben Bella, Oran
关键词
flexible job shop; greedy heuristics; optimisation; production; scheduling;
D O I
10.1504/IJMR.2019.096746
中图分类号
学科分类号
摘要
This paper proposes two greedy heuristics based on an iterated insertion technique to solve the flexible job shop scheduling problem with transportation time's constraint. The approaches treat the two sub-problems of: The assignment of machines to operations and the sequencing of the operations on the assigned machines. The idea is to start with a greedy construction method, then, apply an iterative destroy and recreate algorithm, to minimise the maximal completion time of machines (makespan). The heuristics were tested on a benchmark that considers the transportation times between the machines and based on a real flexible job shop 'AIP-PRIMECA cell of Valenciennes University'. The results of the proposed heuristics are compared with the results of a mixed integer linear program (MILP) and the potential fields (PF) approach. The results obtained are very promising. © 2019 Inderscience Enterprises Ltd.
引用
收藏
页码:43 / 66
页数:23
相关论文
共 54 条
[1]  
Afsar H.M., Lacomme P., Ren L., Prodhon C., Vigo D., Resolution of a job shop problem with transportation constraints: A master/slave approach, IFAC-PapersOnLine, 49, 12, pp. 898-903, (2016)
[2]  
Azab A., Naderi B., Greedy heuristics for distributed job shop problems, Procedia CIRP, 20, pp. 7-12, (2014)
[3]  
Bekkar A., Guemri O., Bekrar A., Aissani N., Beldjilali B., Trentesaux D., An iterative greedy insertion technique for flexible job shop scheduling problem, IFAC-PapersOnLine, 49, 12, pp. 1956-1961, (2016)
[4]  
Benbouzid-Sitayeb F., Guebli S.A., Bessadi Y., Varnier C., Zerhouni N., Joint scheduling of jobs and preventive maintenance operations in the flowshop sequencing problem: A resolution with sequential and integrated strategies, Int. J. Manuf. Res., 6, 1, pp. 30-48, (2011)
[5]  
Brandimarte P., Routing and scheduling in a flexible job shop by tabu search, Annals of Operations Research, 41, 3, pp. 157-183, (1993)
[6]  
Brucker P., Schlie R., Job shop scheduling with multi-purpose machines, Computing, 45, 4, pp. 369-375, (1990)
[7]  
Chan F.T.S., Wong T.C., Chan L.Y., Flexible job shop scheduling problem under resource constraints, International Journal of Production Research, 44, 11, pp. 2071-2089, (2006)
[8]  
Chaudhry I.A., Khan A.A., A research survey: Review of flexible job shop scheduling techniques, International Transactions in Operational Research, 23, 3, pp. 551-591, (2016)
[9]  
Chen T., Wang Y.-C., A post-classifying fuzzy-neural and data-fusion rule for job scheduling in a wafer fab - A simulation study, Int. J. Manuf. Res., 8, 2, pp. 150-170, (2013)
[10]  
(2017)