Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 2
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

An effective iterated greedy algorithm for the mixed no-idle flowshop scheduling problem

  • Pan, Quan-Ke
  • Ruiz García, Rubén
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., Quan-Ke Pan is partially supported by the National Science Foundation of China 61174187, Program for New Century Excellent Talents in University (NCET-13-0106), Science Foundation of Liaoning Province in China (2013020016), Basic scientific research foundation of Northeast University under Grant N110208001, Starting foundation of Northeast University under Grant 29321006, and Shandong Province Key Laboratory of Intelligent Information Processing and Network Security (Liaocheng University). Ruben Ruiz is partially supported by the Spanish Ministry of Economy and Competitiveness, under the project "RESULT - Realistic Extended Scheduling Using Light Techniques" with reference DPI2012-36243-C02-01 co-financed by the European Union and FEDER funds and by the Universitat Politecnica de Valencia, for the project MRPIV with reference PAID/2012/202.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Artículo científico (JournalArticle)

Iterated search methods for earliness and tardiness minimization in hybrid flowshops with due windows

  • Pan, Quan-Ke
  • Ruiz García, Rubén
  • Alfaro-Fernandez, Pedro
[EN] In practice due dates usually behave more like intervals rather than specific points in time. This paper studies hybrid flowshops where jobs, if completed inside a due window, are considered on time. The objective is therefore the minimization of the weighted earliness and tardiness from the due window. This objective has seldom been studied and there are almost no previous works for hybrid flowshops. We present methods based on the simple concepts of iterated greedy and iterated local search. We introduce some novel operators and characteristics, like an optimal idle time insertion procedure and a two stage local search where, in the second stage, a limited local search on a exact representation is carried out. We also present a comprehensive computational campaign, including the reimplementation and comparison of 9 competing procedures. A thorough evaluation of all methods with more than 3000 instances shows that our presented approaches yield superior results which are also demonstrated to be statistically significant. Experiments also show the contribution of the new operators in the presented methods. (C) 2016 Elsevier Ltd. All rights reserved., The authors would like to thank Professors Lofti Hidri and Mohamed Haouari for sharing with us the source codes and explanations of the lower bounds. Quan-Ke Pan is supported by the National Natural Science Foundation of China (Grant No. 51575212), Program for New Century Excellent Talents in University (Grant No. NCET-13-0106), Science Foundation of Hubei Province in China (Grant No. 2015CFB560), Specialized Research Fund for the Doctoral Program of Higher Education (Grant No. 20130042110035), Key Laboratory Basic Research Foundation of Education Department of Liaoning Province (LZ2014014), Open Research Fund Program of the State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, China. Ruben Ruiz and Pedro Alfaro-Fernandez are supported by the Spanish Ministry of Economy and Competitiveness, under the project "SCHEYARD Optimization of Scheduling Problems in Container Yards" (No. DPI2015-65895-R) financed by FEDER funds.