An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem |
| |
| Institution: | 1. State Key Laboratory of Synthetical Automation for Process Industries (Northeastern University), Shenyang 110819, PR China;2. College of Computer Science, Liaocheng University, Liaocheng 252059, PR China;3. Grupo de Sistemas de Optimización Aplicada, Instituto Tecnológico de Informática, Ciudad Politécnica de la Innovación, Edifico 8G, Acc. B. Universitat Politècnica de València, Camino de Vera s/n, 46021 València, Spain;1. Department of Automation, Tsinghua University, Beijing 100084, PR China;2. College of Business Administration, University of Alabama in Huntsville, Huntsville, AL 35899, USA;3. School of Economics and Management, Nanchang University, Nanchang 330031, PR China;4. School of Design, Communication and Information Technology, The University of Newcastle, Callaghan, NSW 2308, Australia;1. Department of Industrial Engineering, Faculty of Engineering, University of Kharazmi, Karaj, Iran;2. Grupo de Sistemas de Optimización Aplicada, Instituto Tecnológico de Informática, Ciudad Politécnica de la Innovación, Universitat Politècnica de València, Edifico 8G, Acc. B, Camino de Vera s/n, 46021 València, Spain;1. College of Information Science and Engineering, Guangxi University for Nationalities, Nanning 530006, China;2. Guangxi Key Laboratory of Hybrid Computation and IC Design Analysis, Nanning 530006, China;3. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100081, China;1. Institut Supérieur de Gestion de Tunis, Université de Tunis, 41, Avenue de la Liberté, Cité Bouchoucha, Bardo,Tunis, Tunisie;2. Ecole Supérieure de Commerce de Tunis, Université de la Manouba, Tunis, Tunisie |
| |
| Abstract: | In the no-idle flowshop, machines cannot be idle after finishing one job and before starting the next one. Therefore, start times of jobs must be delayed to guarantee this constraint. In practice machines show this behavior as it might be technically unfeasible or uneconomical to stop a machine in between jobs. This has important ramifications in the modern industry including fiber glass processing, foundries, production of integrated circuits and the steel making industry, among others. However, to assume that all machines in the shop have this no-idle constraint is not realistic. To the best of our knowledge, this is the first paper to study the mixed no-idle extension where only some machines have the no-idle constraint. We present a mixed integer programming model for this new problem and the equations to calculate the makespan. We also propose a set of formulas to accelerate the calculation of insertions that is used both in heuristics as well as in the local search procedures. An effective iterated greedy (IG) algorithm is proposed. We use an NEH-based heuristic to construct a high quality initial solution. A local search using the proposed accelerations is employed to emphasize intensification and exploration in the IG. A new destruction and construction procedure is also shown. To evaluate the proposed algorithm, we present several adaptations of other well-known and recent metaheuristics for the problem and conduct a comprehensive set of computational and statistical experiments with a total of 1750 instances. The results show that the proposed IG algorithm outperforms existing methods in the no-idle and in the mixed no-idle scenarios by a significant margin. |
| |
| Keywords: | Flowshop No-idle Heuristics Iterated greedy Local search |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
