Modeling and heuristics for scheduling of distributed job shops |
| |
| Affiliation: | 1. Product Lifecycle Management Research Lab, Department of Industrial and Manufacturing Systems Engineering, Faculty of Engineering, University of Windsor, Windsor, Canada;2. Department of Industrial Engineering, Faculty of Engineering, University of Kharazmi, Karaj, Iran;1. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China;2. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China;3. Department of Computing, The Hong Kong Polytechnic University, Hong Kong;1. Gradiant Research Centre, Vigo, Spain;2. AtlantTIC Research Center for Information and Communication Technologies, Department of Telematics Engineering, University of Vigo, Spain;1. Programa de Pós-Graduação em Ciências da Computação, Instituto Federal de Educação, Ciência e Tecnologia do Ceará, Maracanau, CE, Brazil;2. Programa de Pós-Graduação em Engenharia de Teleinformática, Universidade Federal do Ceará, Fortaleza, CE, Brazil;3. Programa de Pós-Graduação em Informática Aplicada, Universidade de Fortaleza, Fortaleza, Ceará, Brazil |
| |
| Abstract: | This paper deals with the problem of distributed job shop scheduling in which the classical single-facility job shop is extended to the multi-facility one. The mathematical formulation of the problem is comprehensively discussed. Two different mixed integer linear programming models in form of sequence and position based variables are proposed. Using commercial software of CPLEX, the small sized problems are optimally solved. To solve large sized problems, besides adapting three well-known heuristics, three greedy heuristics are developed. The basic idea behind the developed heuristics is to iteratively insert operations (one at each iteration) into a sequence to build up a complete permutation of operations. The permutation scheme, although having several advantages, suffers from redundancy which is having many different permutations representing the same schedule. The issue is analyzed to recognize the redundant permutation. That improves efficiency of heuristics. Comprehensive experiments are conducted to evaluate the performance of the two models and the six heuristics. The results show sequence based model and greedy heuristics equipped with redundancy exclusion are effective for the problem. |
| |
| Keywords: | Distributed job shop scheduling Mathematical modeling Greedy heuristics |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
