- -

Benders decomposition for the mixed no-idle permutation flowshop scheduling problem

RiuNet: Repositorio Institucional de la Universidad Politécnica de Valencia

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

Benders decomposition for the mixed no-idle permutation flowshop scheduling problem

Mostrar el registro sencillo del ítem

Ficheros en el ítem

Thumbnail
Nombre: BektasHamzadayiRuiz ...
Tamaño: 284.6Kb
Formato: PDF
Descripción: Versión editorial
Abrir
dc.contributor.author Bektas, Tolga es_ES
dc.contributor.author Hamzadayi, Alper es_ES
dc.contributor.author Ruiz García, Rubén es_ES
dc.date.accessioned 2021-07-29T03:31:03Z
dc.date.available 2021-07-29T03:31:03Z
dc.date.issued 2020-08 es_ES
dc.identifier.issn 1094-6136 es_ES
dc.identifier.uri http://hdl.handle.net/10251/170778
dc.description.abstract [EN] The mixed no-idle flowshop scheduling problem arises in modern industries including integrated circuits, ceramic frit and steel production, among others, and where some machines are not allowed to remain idle between jobs. This paper describes an exact algorithm that uses Benders decomposition with a simple yet effective enhancement mechanism that entails the generation of additional cuts by using a referenced local search to help speed up convergence. Using only a single additional optimality cut at each iteration, and combined with combinatorial cuts, the algorithm can optimally solve instances with up to 500 jobs and 15 machines that are otherwise not within the reach of off-the-shelf optimization software, and can easily surpass ad-hoc existing metaheuristics. To the best of the authors' knowledge, the algorithm described here is the only exact method for solving the mixed no-idle permutation flowshop scheduling problem. es_ES
dc.description.sponsorship This research project was partially supported by the Scientific and Technological Research Council of Turkey (TuBITAK) under Grant 1059B191600107. While writing this paper, Dr Hamzaday was a visiting researcher at the Southampton Business School at the University of Southampton. Ruben Ruiz is supported by the Spanish Ministry of Science, Innovation and Universities, under the Project 'OPTEP-Port Terminal Operations Optimization' (No. RTI2018-094940-B-I00) financed with FEDER funds. Thanks are due to two anonymous reviewers for their careful reading of the paper and helpful suggestions. es_ES
dc.language Inglés es_ES
dc.publisher Springer-Verlag es_ES
dc.relation.ispartof Journal of Scheduling es_ES
dc.rights Reconocimiento (by) es_ES
dc.subject Flowshop scheduling es_ES
dc.subject Mixed no-idle es_ES
dc.subject Benders decomposition es_ES
dc.subject Referenced local search es_ES
dc.subject.classification ESTADISTICA E INVESTIGACION OPERATIVA es_ES
dc.title Benders decomposition for the mixed no-idle permutation flowshop scheduling problem es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1007/s10951-020-00637-8 es_ES
dc.relation.projectID info:eu-repo/grantAgreement/TUBITAK//1059B191600107/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/RTI2018-094940-B-I00/ES/OPTIMIZACION DE OPERACIONES EN TERMINALES PORTUARIAS/ es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Estadística e Investigación Operativa Aplicadas y Calidad - Departament d'Estadística i Investigació Operativa Aplicades i Qualitat es_ES
dc.description.bibliographicCitation Bektas, T.; Hamzadayi, A.; Ruiz García, R. (2020). Benders decomposition for the mixed no-idle permutation flowshop scheduling problem. Journal of Scheduling. 23(4):513-523. https://doi.org/10.1007/s10951-020-00637-8 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1007/s10951-020-00637-8 es_ES
dc.description.upvformatpinicio 513 es_ES
dc.description.upvformatpfin 523 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 23 es_ES
dc.description.issue 4 es_ES
dc.relation.pasarela S\424885 es_ES
dc.contributor.funder Agencia Estatal de Investigación es_ES
dc.contributor.funder European Regional Development Fund es_ES
dc.contributor.funder Scientific and Technological Research Council of Turkey es_ES
dc.description.references Adiri, I., & Pohoryles, D. (1982). Flowshop no-idle or no-wait scheduling to minimize the sum of completion times. Naval Research Logistics, 29(3), 495–504. es_ES
dc.description.references Baker, K. R. (1974). Introduction to sequencing and scheduling. New York: Wiley. es_ES
dc.description.references Baptiste, P., & Hguny, L. K. (1997). A branch and bound algorithm for the $$F$$/no-idle/$$C_{max}$$. In Proceedings of the international conference on industrial engineering and production management, IEPM’97, Lyon, France (Vol. 1, pp. 429–438). es_ES
dc.description.references Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238–252. es_ES
dc.description.references Cordeau, J. F., Pasin, F., & Solomon, M. (2006). An integrated model for logistics network design. Annals of Operations Research, 144(1), 59–82. es_ES
dc.description.references Costa, A. M., Cordeau, J. F., Gendron, B., & Laporte, G. (2012). Accelerating benders decomposition with heuristic master problem solutions. Pesquisa Operacional, 32(1), 3–20. es_ES
dc.description.references Deng, G., & Gu, X. (2012). A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion. Computers & Operations Research, 39(9), 2152–2160. es_ES
dc.description.references Goncharov, Y., & Sevastyanov, S. (2009). The flow shop problem with no-idle constraints: A review and approximation. European Journal of Operational Research, 196(2), 450–456. es_ES
dc.description.references Kalczynski, P. J., & Kamburowski, J. (2005). A heuristic for minimizing the makespan in no-idle permutation flow shops. Computers & Industrial Engineering, 49(1), 146–154. es_ES
dc.description.references Magnanti, T. L., & Wong, R. T. (1981). Accelerating benders decomposition: Algorithmic enhancement and model selection criteria. Operations Research, 29(3), 464–484. es_ES
dc.description.references Pan, Q. K., & Ruiz, R. (2014). An effective iterated greedy algorithm for the mixed no-idle flowshop scheduling problem. Omega, 44(1), 41–50. es_ES
dc.description.references Pan, Q. K., Tasgetiren, M. F., & Liang, Y. C. (2008). A discrete differential evolution algorithm for the permutation flowshop scheduling problem. Computers & Industrial Engineering, 55(4), 795–816. es_ES
dc.description.references Pan, Q. K., & Wang, L. (2008a). No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm. International Journal of Advanced Manufacturing Technology, 39(7–8), 796–807. es_ES
dc.description.references Pan, Q. K., & Wang, L. (2008b). A novel differential evolution algorithm for no-idle permutation flow-shop scheduling problems. European Journal of Industrial Engineering, 2(3), 279–297. es_ES
dc.description.references Papadakos, N. (2008). Practical enhancements to the Magnanti–Wong method. Operations Research Letters, 36(4), 444–449. es_ES
dc.description.references Röck, H. (1984). The three-machine no-wait flow shop is NP-complete. Journal of the Association for Computing Machinery, 31(2), 336–345. es_ES
dc.description.references Ruiz, R., & Maroto, C. (2005). A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165(2), 479–494. es_ES
dc.description.references Ruiz, R., Vallada, E., & Fernández-Martínez, C. (2009). Scheduling in flowshops with no-idle machines. In U. Chakraborty (Ed.), Computational intelligence in flow shop and job shop scheduling, chap 2 (pp. 21–51). New York: Springer. es_ES
dc.description.references Saadani, N. E. H., Guinet, A., & Moalla, M. (2003). Three stage no-idle flow-shops. Computers & Industrial Engineering, 44(3), 425–434. es_ES
dc.description.references Saharidis, G., & Ierapetritou, M. (2013). Speed-up Benders decomposition using maximum density cut (MDC) generation. Annals of Operations Research, 210, 101–123. es_ES
dc.description.references Shao, W., Pi, D., & Shao, Z. (2017). Memetic algorithm with node and edge histogram for no-idle flow shop scheduling problem to minimize the makespan criterion. Applied Soft Computing, 54, 164–182. es_ES
dc.description.references Tasgetiren, M. F., Buyukdagli, O., Pan, Q. K., & Suganthan, P. N. (2013). A general variable neighborhood search algorithm for the no-idle permutation flowshop scheduling problem. In B. K. Panigrahi, P. N. Suganthan, S. Das, & S. S. Dash (Eds.), Swarm, evolutionary, and memetic computing (pp. 24–34). Cham: Springer. es_ES
dc.description.references Vachajitpan, P. (1982). Job sequencing with continuous machine operation. Computers & Industrial Engineering, 6(3), 255–259. es_ES


Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem