logo

Total tardiness optimization on parallel machines: case study in the coffee industry

10.24050/reia.v21i41.1710
Published 2024-01-01
Articles

Abstract

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.

Keywords

Categories

Authors

  • Alejandro Uribe

    Universidad EAFIT

  • Santiago López Duque

    Universidad EAFIT

  • Juan Pablo Mesa López

    Universidad EAFIT

  • Jose Alejandro Montoya Echeverry

    Universidad EAFIT

References

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

Statistics

Abstract
0
PDF accesses
0

Dimensions

PlumX

Downloads

Download data is not yet available.