Optimización de la tardanza total en máquinas paralelas: caso de estudio en la industria del café
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é. Es... Ver más
Guardado en:
1794-1237
2463-0950
21
2024-01-01
4102 pp. 1
20
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.
Revista EIA - 2023
http://purl.org/coar/access_right/c_abf2
info:eu-repo/semantics/openAccess
| id |
deae715912578e3f52cf8d4f1ae25731 |
|---|---|
| record_format |
ojs |
| spelling |
Optimización de la tardanza total en máquinas paralelas: caso de estudio en la industria del café 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 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. 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. 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. 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 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. 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 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 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. 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 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. Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0. Revista EIA - 2023 https://creativecommons.org/licenses/by-nc-nd/4.0 Español 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. 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. Revista EIA http://purl.org/coar/resource_type/c_2df8fbb1 Text http://purl.org/coar/access_right/c_abf2 info:eu-repo/semantics/openAccess http://purl.org/coar/version/c_970fb48d4fbd8a85 info:eu-repo/semantics/publishedVersion http://purl.org/redcol/resource_type/ART http://purl.org/coar/resource_type/c_6501 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. info:eu-repo/semantics/article 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 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 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 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, 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 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 https://revistas.eia.edu.co/index.php/reveia/article/view/1710 Publication Fondo Editorial EIA - Universidad EIA Café 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. Uribe, Alejandro López Duque, Santiago Mesa López, Juan Pablo Montoya Echeverry, Jose Alejandro Programación Optimización Máquinas paralelas no relacionadas application/pdf Modelo matemático Heurística Mateheuristica ATC Retraso total Tostión 21 41 Núm. 41 , Año 2024 : . Artículo de revista Production scheduling is one of the most important tasks in manufacturing systems since it allows the allocation of jobs with a certain number of available resources. In the production and service industries, meeting the established commitments with the different customers and production deadlines can lead to higher levels of satisfaction and market competitive advantages. On the other hand, one of the main industries worldwide is the coffee industry. Indeed, coffee is the second most traded commodity in the world. Therefore, this research addresses the optimization of the total tardiness in the scheduling of jobs in parallel machines for a case study in a coffee roaster. This is an NP-hard problem where each job requires the roasting process and, in addition, has an associated delivery time. Each job’s processing time depends on the machine that is designated and not all machines can run all jobs. We present the mathematical model to describe the problem using mixed integer linear programming and then it is implemented in Python. Additionally, a mate heuristic model based on the ATC heuristic is proposed in order to reduce the computation time and to reach solutions close to the optimum. This model was evaluated with one thousand instances of real data from the roasting process. The Gurobi optimizer was used to solve the problem. The exact method shows high computational times, so we proposed to first perform the sequencing of jobs and then assign them to the machines by means of a simplified mathematical model. By using the proposed mate heuristic model, an average reduction of 53.98% of the execution time is achieved and with respect to the solution delay, this model achieves a median of 0.0% with respect to the optimum. Total tardiness optimization on parallel machines: case study in the coffee industry Scheduling Optimization Unrelated parallel machines Total tardiness Mathematical model Heuristics Mateheuristics ATC Coffee Roasting Journal article https://revistas.eia.edu.co/index.php/reveia/article/download/1710/1576 2024-01-01 09:26:25 2024-01-01 09:26:25 https://doi.org/10.24050/reia.v21i41.1710 10.24050/reia.v21i41.1710 2024-01-01 4102 pp. 1 20 1794-1237 2463-0950 |
| institution |
UNIVERSIDAD EIA |
| thumbnail |
https://nuevo.metarevistas.org/UNIVERSIDADEIA/logo.png |
| country_str |
Colombia |
| collection |
Revista EIA |
| title |
Optimización de la tardanza total en máquinas paralelas: caso de estudio en la industria del café |
| spellingShingle |
Optimización de la tardanza total en máquinas paralelas: caso de estudio en la industria del café Uribe, Alejandro López Duque, Santiago Mesa López, Juan Pablo Montoya Echeverry, Jose Alejandro Café Programación Optimización Máquinas paralelas no relacionadas Modelo matemático Heurística Mateheuristica Retraso total Tostión Scheduling Optimization Unrelated parallel machines Total tardiness Mathematical model Heuristics Mateheuristics Coffee Roasting |
| title_short |
Optimización de la tardanza total en máquinas paralelas: caso de estudio en la industria del café |
| title_full |
Optimización de la tardanza total en máquinas paralelas: caso de estudio en la industria del café |
| title_fullStr |
Optimización de la tardanza total en máquinas paralelas: caso de estudio en la industria del café |
| title_full_unstemmed |
Optimización de la tardanza total en máquinas paralelas: caso de estudio en la industria del café |
| title_sort |
optimización de la tardanza total en máquinas paralelas: caso de estudio en la industria del café |
| title_eng |
Total tardiness optimization on parallel machines: case study in the coffee industry |
| description |
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.
|
| description_eng |
Production scheduling is one of the most important tasks in manufacturing systems since it allows the allocation of jobs with a certain number of available resources. In the production and service industries, meeting the established commitments with the different customers and production deadlines can lead to higher levels of satisfaction and market competitive advantages. On the other hand, one of the main industries worldwide is the coffee industry. Indeed, coffee is the second most traded commodity in the world. Therefore, this research addresses the optimization of the total tardiness in the scheduling of jobs in parallel machines for a case study in a coffee roaster. This is an NP-hard problem where each job requires the roasting process and, in addition, has an associated delivery time. Each job’s processing time depends on the machine that is designated and not all machines can run all jobs. We present the mathematical model to describe the problem using mixed integer linear programming and then it is implemented in Python. Additionally, a mate heuristic model based on the ATC heuristic is proposed in order to reduce the computation time and to reach solutions close to the optimum. This model was evaluated with one thousand instances of real data from the roasting process. The Gurobi optimizer was used to solve the problem. The exact method shows high computational times, so we proposed to first perform the sequencing of jobs and then assign them to the machines by means of a simplified mathematical model. By using the proposed mate heuristic model, an average reduction of 53.98% of the execution time is achieved and with respect to the solution delay, this model achieves a median of 0.0% with respect to the optimum.
|
| author |
Uribe, Alejandro López Duque, Santiago Mesa López, Juan Pablo Montoya Echeverry, Jose Alejandro |
| author_facet |
Uribe, Alejandro López Duque, Santiago Mesa López, Juan Pablo Montoya Echeverry, Jose Alejandro |
| topicspa_str_mv |
Café Programación Optimización Máquinas paralelas no relacionadas Modelo matemático Heurística Mateheuristica Retraso total Tostión |
| topic |
Café Programación Optimización Máquinas paralelas no relacionadas Modelo matemático Heurística Mateheuristica Retraso total Tostión Scheduling Optimization Unrelated parallel machines Total tardiness Mathematical model Heuristics Mateheuristics Coffee Roasting |
| topic_facet |
Café Programación Optimización Máquinas paralelas no relacionadas Modelo matemático Heurística Mateheuristica Retraso total Tostión Scheduling Optimization Unrelated parallel machines Total tardiness Mathematical model Heuristics Mateheuristics Coffee Roasting |
| citationvolume |
21 |
| citationissue |
41 |
| citationedition |
Núm. 41 , Año 2024 : . |
| publisher |
Fondo Editorial EIA - Universidad EIA |
| ispartofjournal |
Revista EIA |
| source |
https://revistas.eia.edu.co/index.php/reveia/article/view/1710 |
| language |
Español |
| format |
Article |
| rights |
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0. Revista EIA - 2023 https://creativecommons.org/licenses/by-nc-nd/4.0 http://purl.org/coar/access_right/c_abf2 info:eu-repo/semantics/openAccess |
| references |
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 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. 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. 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. 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 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. 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 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 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. 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 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. 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. 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. 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 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 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 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, 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 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 |
| type_driver |
info:eu-repo/semantics/article |
| type_coar |
http://purl.org/coar/resource_type/c_2df8fbb1 |
| type_version |
info:eu-repo/semantics/publishedVersion |
| type_coarversion |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| type_content |
Text |
| publishDate |
2024-01-01 |
| date_accessioned |
2024-01-01 09:26:25 |
| date_available |
2024-01-01 09:26:25 |
| url |
https://revistas.eia.edu.co/index.php/reveia/article/view/1710 |
| url_doi |
https://doi.org/10.24050/reia.v21i41.1710 |
| issn |
1794-1237 |
| eissn |
2463-0950 |
| doi |
10.24050/reia.v21i41.1710 |
| citationstartpage |
4102 pp. 1 |
| citationendpage |
20 |
| url3_str_mv |
https://revistas.eia.edu.co/index.php/reveia/article/download/1710/1576 |
| _version_ |
1797376440352636928 |