Optimización de la tardanza total en máquinas paralelas: caso de estudio en la industria del café
Total tardiness optimization on parallel machines: case study in the coffee industry
Barra lateral del artículo
PDF
FLIP
Términos de la licencia (VER)
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.
Declaración del copyright
Los autores ceden en exclusiva a la Universidad EIA, con facultad de cesión a terceros, todos los derechos de explotación que deriven de los trabajos que sean aceptados para su publicación en la Revista EIA, así como en cualquier producto derivados de la misma y, en particular, los de reproducción, distribución, comunicación pública (incluida la puesta a disposición interactiva) y transformación (incluidas la adaptación, la modificación y, en su caso, la traducción), para todas las modalidades de explotación (a título enunciativo y no limitativo: en formato papel, electrónico, on-line, soporte informático o audiovisual, así como en cualquier otro formato, incluso con finalidad promocional o publicitaria y/o para la realización de productos derivados), para un ámbito territorial mundial y para toda la duración legal de los derechos prevista en el vigente texto difundido de la Ley de Propiedad Intelectual. Esta cesión la realizarán los autores sin derecho a ningún tipo de remuneración o indemnización.
La autorización conferida a la Revista EIA estará vigente a partir de la fecha en que se incluye en el volumen y número respectivo en el Sistema Open Journal Systems de la Revista EIA, así como en las diferentes bases e índices de datos en que se encuentra indexada la publicación.
Todos los contenidos de la Revista EIA, están publicados bajo la Licencia Creative Commons Atribución-NoComercial-NoDerivativa 4.0 Internacional
Licencia
Esta obra está bajo una Licencia Creative Commons Atribución-NoComercial-NoDerivativa 4.0 Internacional
Contenido principal del artículo
Resumen
La programación de producción es una de las tareas con mayor importancia en sistemas de manufactura ya que permite la asignación de trabajos con cierto número de recursos disponibles. En la industria de manufactura y de servicios, poder cumplir con los compromisos acordados con los diferentes clientes y con los plazos de producción puede generar mayores niveles de satisfacción y ventajas competitivas en el mercado. Por otra parte, una de las principales industrias a nivel mundial es la cafetera. El café es la segunda materia prima más negociada del mundo. Por lo tanto, en esta investigación se aborda la optimización de la tardanza total en la programación de trabajos en máquinas paralelas para un caso de estudio en una tostadora de café. Este es un problema NP-hard donde cada trabajo requiere del proceso de tostión y, además, cuenta con una fecha de entrega asociada. El tiempo de procesamiento de cada trabajo depende de la máquina que se designe y no todas las máquinas puede ejecutar todos los trabajos. Se presenta el modelo matemático para describir el problema mediante programación lineal entera mixta y se implementa en Python. Adicionalmente, se propone un modelo mate heurístico basado en la heurística ATC que permite reducir el tiempo de cómputo y obtener soluciones cercanas al óptimo. Este modelo fue evaluado con mil instancias de datos reales del proceso de tostión. Para la solución del problema se utilizó el optimizador Gurobi. El método exacto muestra altos tiempos de cómputo por lo que se propuso realizar primero la secuenciación de trabajos para luego asignarlos a las maquinas por medio de un modelo matemático simplificado. Al utilizar el modelo mate heurístico propuesto se logra reducir en promedio un 53.98% el tiempo de ejecución y con respecto a la tardanza de la solución, este modelo logra una mediana del 0.0% con respecto al óptimo.
Descargas
Detalles del artículo
Referencias (VER)
Azizoǧlu, M.; & Kirca, Ö. (1998). Tardiness minimization on parallel machines. International Journal of Production Economics, 55(2), 163-168. https://doi.org/10.1016/s0925-5273(98)00034-6.
Bektur, G.; & Saraç, T. (2019). A mathematical model and heuristic algorithms for an unrelated parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and a common server. Computers & Operations Research, 103, 46-63. https://doi.org/10.1016/j.cor.2018.10.010
Berthier, A.; Yalaoui, A.; Chehade, H.; Yalaoui, F.; Yalaoui, F.; & Bouillot, C. (2022). Unrelated parallel machines scheduling with dependent setup times in textile industry. Computers & Industrial Engineering, 174, 108736. https://doi.org/10.1016/j.cie.2022.108736
Costa, A. S.; Alves, R. C.; Vinha, A. F.; Barreira, S. V. P.; Nunes, M. A.; Cunha, L. M.; & Oliveira, M. B. P. (2014). Optimization of antioxidants extraction from coffee silverskin, a roasting by-product, having in view a sustainable process. Industrial Crops and Products, 53, 350-357. https://doi.org/10.1016/j.indcrop.2014.01.006
Diana, R. O. M.; De Souza, S. R.; & Filho, M. F. F. (2018). A variable neighborhood descent as ILS local search to the minimization of the total weighted tardiness on unrelated parallel machines and sequence dependent setup times. Electronic Notes in Discrete Mathematics, 66, 191-198. https://doi.org/10.1016/j.endm.2018.03.025
Fang, W.; Zhu, H.; & Mei, Y. (2022). Hybrid meta-heuristics for the unrelated parallel machine scheduling problem with setup times. Knowledge-Based Systems 241:108193. https://doi.org/10.1016/j.knosys.2022.108193.
Heydar, M.; Mardaneh, E.; & Loxton, R. (2022). Approximate dynamic programming for an energy-efficient parallel machine scheduling problem. European Journal of Operational Research 302(1):363–80. https://doi.org/10.1016/j.ejor.2021.12.041
Lenstra, J. K.; & Vakhania, N. (2023). On the complexity of scheduling unrelated parallel machines with limited preemptions.Operations Research Letters 51(2):187–89. https://doi.org/10.1016/j.orl.2023.02.004.
Li, K.; Shi, Y.; Yang, S.; & Cheng, B. (2011). Parallel machine scheduling problem to minimize the makespan with resource dependent processing times. Applied Soft Computing 11(8):5551–57. https://doi.org/10.1016/j.asoc.2011.05.005.
Monch, L. (2008). Heuristics to Minimize Total Weighted Tardiness of Jobs on Unrelated Parallel Machines. 2008 IEEE International Conference on Automation Science and Engineering 572–77. doi: 10.1109/COASE.2008.4626531.
Ratanasanya, S.; Chindapan, N.; Polvichai, J.; Sirinaovakul, B.; & Devahastin, S. (2022). Model-based optimization of coffee roasting process: model development, prediction, optimization and application to upgrading of robusta coffee beans. Journal of Food Engineering 318:110888. doi: https://doi.org/10.1016/j.jfoodeng.2021.110888.
Ruíz, R.; García-Díaz, J. C.; & Álvarez, C. M. (2007). Considering scheduling and preventive maintenance in the flowshop sequencing problem. Computers & Operations Research 34(11):3314–30. doi: https://doi.org/10.1016/j.cor.2005.12.007.
Sanati, H.; Moslehi, G.; & Reisi‐Nafchi, M. (2023). Unrelated parallel machine energy-efficient scheduling considering sequence-dependent setup times and time-of-use electricity tariffs. EURO Journal on Computational Optimization 11:100052. doi: https://doi.org/10.1016/j.ejco.2022.100052.
Tanaka, S.; & Araki, M. (2008). A branch-and-bound algorithm with lagrangian relaxation to minimize total tardiness on identical parallel machines. International Journal of Production Economics 113(1):446–58. doi: https://doi.org/10.1016/j.ijpe.2007.10.006.
Vincent, B. G.; Duhamel, C.; Ren, L.; & Tchernev, N. (2016). An efficient heuristic for scheduling on identical parallel machines to minimize total tardiness. IFAC-PapersOnLine 49(12):1737–42. https://doi.org/10.1016/j.ifacol.2016.07.833
Wang, B.; Feng, K.; & Wang, X. (2023). Bi-objective scenario-guided swarm intelligent algorithms based on reinforcement learning for robust unrelated parallel machines scheduling with setup times. Swarm and Evolutionary Computation 80:101321. https://doi.org/10.1016/j.swevo.2023.101321
Wang, H.; Li, R.; & Gong, W. (2023). Minimizing tardiness and makeSpan for distributed heterogeneous unrelated parallel machine scheduling by knowledge and Pareto-based memetic algorithm. Egyptian Informatics Journal 24(3):100383. https://doi.org/10.1016/j.eij.2023.05.008
Wang, S.; Wu, R.; Chu, F.; & Yu, J. (2023). An exact decomposition method for unrelated parallel machine scheduling with order acceptance and setup times. Computers & Industrial Engineering 175:108899. https://doi.org/10.1016/j.cie.2022.108899
Yalaoui, F.; & Chen, C. (2002). Parallel machine scheduling to minimize total tardiness. International Journal of Production Economics 76(3):265–79. https://doi.org/10.1016/S0925-5273(01)00175-X
Zhao, Y.; Xu, X.; Xu, E.; & Niu, B. (2021). Stochastic customer order scheduling on heterogeneous parallel machines with resource allocation consideration. Computers & Industrial Engineering 160:107539. https://doi.org/10.1016/j.cie.2021.107539