Abstract
We consider strongly NP-hard problem of two-machine task scheduling with due dates and minimizing of the total weighted tardiness. Task execution times are random variables. We propose methods of intermediate review of solutions, the so-called ‘block properties’, which we use in the tabu search algorithm. From computational experiments carried out it follows that the use of blocks significantly speeds up calculations.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Al-Salem, M., Valencia, L., Rabadi, G.: Heuristic and exact algorithms for the two-machine just in time job shop scheduling problem. Math. Prob. Eng. 5, 1–11 (2016)
Ardakan, M., Beheshti, A., Hamid Mirmohammadi, S., Ardakani, H.D.: A hybrid meta-heuristic algorithm to minimize the number of tardy jobs in a dynamic two-machine flow shop problem. Numer. Algebra Control Optim. 7(4), 465–480 (2017)
Bank, M., Fatemi, S., Ghomi, M.T., Jolai, F., Behnamian, J.: Two-machine flow shop total tardiness scheduling problem with deteriorating jobs. Appl. Math. Model. 36(11), 5418–5426 (2012)
Bożejko, W., Grabowski, J., Wodecki, M.: Block approach tabu search algorithm for single machine total weighted tardiness problem. Comp. Ind. Eng. 50(1–2), 1–14 (2006)
Bożejko, W., Hejducki, Z., Wodecki, M.: Flowshop scheduling of construction processes with uncertain parameters. Arch. Civil Mech. Eng. 19, 194–204 (2019)
Bożejko, W., Rajba, P., Wodecki, M.: Stable scheduling of single machine with probabilistic parameters. Bull. Pol. Acad. Sci. Tech. Sci. 65(2), 219–231 (2017)
Bulfin, R.L., M’Hallah, R.: Minimizing the weighted number of tardy jobs on two-machineflow shop. Comput. Oper. Res. 30, 1887–1900 (2003)
Gupta, J.N.D., Hariri, A.M.A.: Two-machine flowshop scheduling to minimize the number of tardy jobs. J. Oper. Res. Soc. 48, 212–220 (1997)
Johnson, S.M.: Optimal two- and three-stage production schedules with setup times included. Naval Res. Logist. Q. 1, 61–68 (1954)
Ahmadi-Darani, M., Moslehi, G., Reisi-Nafchi, M.: A two-agent scheduling problem in a two-machine flowshop. Int. J. Ind. Eng. Comput. 9(3), 289–306 (2018)
Lin, B.M.T.: Scheduling in the two-machine flowshop with due date constraints. Int. J. Prod. Econ. 70, 117–123 (2001)
Vondrák, J.: Probabilistic methods in combinatorial and stochastic optimization. PhD, MIT (2005)
Cai, X., Wu, X., Zhou, X.: Optimal Stochastic Scheduling. Springer, New York (2014)
Acknowledgments
This work was partially funded by the National Science Centre of Poland, grant OPUS no. 2017/25/B/ST7/02181 and a statutory subsidy 049U/0032/19.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bożejko, W., Rajba, P., Wodecki, M. (2021). Blocks of Jobs for Solving Two-Machine Flow Shop Problem with Normal Distributed Processing Times. In: Herrero, Á., Cambra, C., Urda, D., Sedano, J., Quintián, H., Corchado, E. (eds) 15th International Conference on Soft Computing Models in Industrial and Environmental Applications (SOCO 2020). SOCO 2020. Advances in Intelligent Systems and Computing, vol 1268. Springer, Cham. https://doi.org/10.1007/978-3-030-57802-2_28
Download citation
DOI: https://doi.org/10.1007/978-3-030-57802-2_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-57801-5
Online ISBN: 978-3-030-57802-2
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)