Branch and bound algorithm for solving the total weighted tardiness criterion for the permutation flowshop scheduling problem with time lags
DOI:
https://doi.org/10.2298/YJOR210615023AKeywords:
Branch & Bound Algorithm, Total Weighted Tardiness, Time Lags, Permutation Flowshop Scheduling ProblemAbstract
This paper deals with the permutation flowshop scheduling problem with time lags constraints to minimize the total weighted tardiness criterion by using the Branch and Bound algorithm. A new lower bound was developed for the flowshop scheduling problem. The computational experiments indicate that the proposed algorithm provides good solution in terms of quality and time requirements.References
Azizi, V., and Hu, G., “A branch and bound algorithm to solve a two-machine no-wait flowshop scheduling problem with truncated learning function,” International Journal of Management Science and Engineering Management, 15 (2) (2020) 89–95.
Basnet, C., Foulds, L. R., Wilson, J., “Scheduling contractors’ farm-to-farm crop harvesting operations,” International Transactions in Operational Research, 13 (1) (2006) 1–15.
Bellman, R., “Dynamic Programming,” Princeton University Press, Princeton, NJ, 1957.
Chu, C., and Proth, J. M., “Single machine scheduling with chain structured precedence constraints and separation time windows,” IEEE Trans Robot Autom, 12 (6) (1996) 835–844.
Companys, R., and Mateo, M., “Different behaviour of a double branch-and-bound algorithm Fm|perm|Cmax and Fm|block|Cmax problems,” Computers and Operations Research, 34 (4) (2007) 938–953.
Dell’Amico, M., “Shop problems with two machines and time lags,” Operations Research, 44 (5) (1996) 777–787.
Dhouib, E., Teghem, J., and Loukil, T., “Lexicographic optimization of a permutation flowshop with time lags constraint,” International Transactions in Operational Research, 20 (2) (2013) 213–232.
Dhouib, E., Teghem, J., and Loukil, T., “Minimizing the number of tardy jobs in a permutation flowshop scheduling problem with setup times and time lags constraints,” Journal of Mathematical Modeling and Algorithms, 12 (1) (2013) 85–99.
Fondrevelle, J., Oulamara, A., and Portmann, M. C., “Permutation flowshop scheduling problems with maximal and minimal time lags,” Comput Oper Res, 33 (6) (2006) 1540–1556.
Fondrevelle, J., Oulamara, A., and Portmann, M. C., “Permutation flowshop scheduling problems with time lags to minimize the weighted sum of machine completion times,” International Journal of Production Economics, 112 (1) (2008) 168–176.
Foulds, L. R., and Wilson, J. M., “Scheduling operations for the harvesting of renewable resources,” J Food Eng, 70 (3) (2005) 281–292.
Gargouri, E., “Ordonnancement coopératif en industries agroalimentaires,” Thèse de Doctorat, Université des Sciences et technologies de Lille 1.
Hamdi, I., and Loukil, T., “Minimizing total tardiness in the permutation flowshop scheduling problem with minimal and maximal time lags,” Operational Research, 15 (1) (2015) 95–114.
Hamdi, I., and Loukil, T., “Upper and lower bounds for the permutation flowshop scheduling problem with minimal time lags,” Optimization Letters, 9 (3) (2015) 465–482.
Hamdi, I., and Loukil, T., “The permutation flowshop scheduling problem with exact time lags to minimize the total earliness and tardiness,” International Journal of Operational Research, 28 (1) (2017) 70–86.
Hamdi, I., Oulamara, A., and Loukil, T., “A branch and bound algorithm to minimize total tardiness in the two machine flowshop problem with minimal time lags,” Enterprise Computing Series, McGraw-Hill, 2000. International Journal of Operational Research, 23 (4) (2015) 387–405.
Hamdi, I., and Toumi, S., “MILP models and valid inequalities for the two-machine permutation flowshop scheduling problem with minimal time lags,” Journal of Industrial Engineering International, 15 (2019) 223–229.
Huang, J. D., Liu, J. J., Chen, Q. X., and Mao, N., “Mixed integer formulation to tardiness objectives in a flowshop with two batches processing machines and release date,” in: CIE43 proceedings, 16–18 October, The University of Hong Kong, 2013.
Kharbeche, M., and Haouari, M., “MIP models for minimizing total tardiness in a two machine flowshop,” Journal of the Operational Research Society, 64 (5) (2013) 690–707.
Keshavarz, T., Salmasi, N., and Varmazyar, M., “Flowshop sequence dependent group scheduling with minimisation of weighted earliness and tardiness,” European Journal of Industrial Engineering, 13 (1) (2019) 54–80.
Moreno-Camacho, C. A., Montoya-Torres, J. R., and Vélez-Gallego, M. C., “A comparison of mixed-integer linear programming models for workforce scheduling with position-dependent processing times,” Engineering Optimization, 50 (6) (2018) 917–932.
Moslehi, G., Mahnam, M., Nayeri, M. A., and Azaron, A., “A branch and bound algorithm to minimise the sum of maximum earliness and tardiness in the single machine,” International Journal of Operational Research, 8 (4) (2010) 458–482.
Ronconi, D. P., “A branch and bound algorithm to minimize the makespan in a flowshop with blocking,” Annals of Operations Research, 138 (1) (2005) 53–65.
Toumi, S., Jarboui, B., Eddaly, M., and Rebai, A., “Branch and Bound algorithm for solving blocking flowshop scheduling problem with total tardiness and total weighted tardiness criteria,” International Journal of Operational Research, 30 (4) (2017) 441–459.
Toumi, S., Jarboui, B., Eddaly, M., and Rebai, A., “Branch and Bound algorithm for solving blocking flowshop scheduling problems with makespan criterion,” International Journal of Mathematics in Operational Research, 10 (1) (2017) 34–48.
Zribi, N., “Ordonnancement des job-shops flexibles sous contraintes de disponibilité des machines,” Thèse de Doctorat, Université des Sciences et Technologies de Lille, 2005.
Downloads
Published
Issue
Section
License
Copyright (c) 2022 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
