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

来源：

International Journal of Manufacturing Research | 2019年 / 14卷 / 01期

关键词：

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 条

[31]

Lopez M.L.N., Diaz H.L., Sanmiguel P.J.J., Gonzalez J.V.R., Transfer batch size impact on a job shop environment performance, Int. J. Manuf. Res., 12, 3, (2017)

[32]

Mastrolilli M., Gambardella L.M., Effective neighbourhood functions for the flexible job shop problem, Journal of Scheduling, 3, 1, pp. 3-20, (2000)

[33]

Mati Y., Rezg N., Xie X., An integrated greedy heuristic for a flexible job shop scheduling problem, 2001 IEEE International Conference on Systems, Man, and Cybernetics, pp. 2534-2539, (2001)

[34]

Mati Y., Rezg N., Xie X., Greedy heuristic and genetic algorithms for the multi-resource shop scheduling with resource flexibility, Proc. 8th International Workshop on Project Management and Scheduling (PMS2002), (2002)

[35]

Pach C., Berger T., Bonte T., Trentesaux D., ORCA-FMS: A dynamic architecture for the optimized and reactive control of flexible manufacturing scheduling, Computers in Industry, 65, 4, pp. 706-720, (2014)

[36]

Pezzella F., Morganti G., Ciaschetti G., A genetic algorithm for the flexible job shop scheduling problem, Computers and Operations Research, 35, 10, pp. 3202-3212, (2008)

[37]

Pinedo M.L., Scheduling, (2012)

[38]

Pranzo M., Pacciarelli D., An iterated greedy metaheuristic for the blocking job shop scheduling problem, Journal of Heuristics, 22, 4, pp. 587-611, (2015)

[39]

Rossi A., Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships, International Journal of Production Economics, 153, pp. 253-267, (2014)

[40]

Ruiz R., Stutzle T., An iterated greedy algorithm for the flowshop problem with sequence dependent setup times, The 6th Metaheuristics International Conference, pp. 817-826, (2005)

← 1 2 3 4 5 6 →