Abstract
This paper proposes a three-dimensional matrix Estimation of Distribution Algorithm (TDEDA) for distributed no-wait flow-shop scheduling problem (NFSSP) with sequence-independent setup times (SISTs) and release dates (RDs) to minimize the total completion time, which is a typical NP-hard combinatorial optimization problem with strong engineering background. First, a population is initialized in a hybrid way by modified NEH heuristic algorithm and the random method. Secondly, probabilistic model is developed to learn knowledge by accumulating the information of the blocks and the order of jobs from the elite individuals. Then, four search methods are developed to optimize the quality of solutions. Finally, computational results and comparisons demonstrate TDEDA obviously outperforms other considered optimization algorithms for addressing DNWFSP_SISTs_RTs.
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
Allahverdi, A.: A survey of scheduling problems with no-wait in process. Eur. J. Oper. Res. 255, 665–686 (2016)
Qian, B., Wang, L., Huang, D.X., Wang, W.L., Wang, X.: An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers. Comput. Oper. Res. 36(1), 209–233 (2009)
Kahn, K.B., Castellion, G., Griffin, A.: The PDMA Handbook of New Product Development, 2 ed, pp. 65–79. John Wiley & Sons, Hoboken (2005)
Wang, L., Shen, W.: Process planning and scheduling for distributed manufacturing. Springer 47(4), 1151–1152 (2007)
Naderi, B., Ruiz, R.: The distributed permutation flow shop scheduling problem. Comput. Oper. Res. 37(4), 754–768 (2010)
Gao, J., Chen, R.: An NEH-based heuristic algorithm for distributed permutation flow shop scheduling problems. Sci. Res. Essays 6(14), 3094–3100 (2011)
Gao, J., Chen, R., Deng, W.: An efficient tabu search algorithm for the distributed permutation flow-shop scheduling problem. Int. J. Prod. Res. 51, 1–11 (2013)
Wang, S.Y., Wang, L., Min, L.: An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem. Int. J. Prod. Econ. 145, 387–396 (2013)
Lin, S.W., Ying, K.C.: Minimizing makespan for solving the distributed no-wait flow shop scheduling problem. Comput. Ind. Eng. 99, 202–209 (2016)
Komaki, M., Malakooti, B.: General variable neighborhood search algorithm to minimize makespan of the distributed no-wait flow shop scheduling problem. Prod. Eng. Res. Devel. 11(3), 315–329 (2017). https://doi.org/10.1007/s11740-017-0716-9
Mühlenbein, H., Paaß, G.: From recombination of genes to the estimation of distributions I. Binary parameters. In: Voigt, Hans-Michael., Ebeling, Werner, Rechenberg, Ingo, Schwefel, Hans-Paul. (eds.) PPSN 1996. LNCS, vol. 1141, pp. 178–187. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61723-X_982
Jarboui, B., Eddaly, M., Siarry, P.: An estimation of distribution algorithm for minimizing the total flowtime in permutation flow shop scheduling problems. Comput. Oper. Res. 36(9), 2638–2646 (2009)
Pan, Q.K., Ruiz, R.: An estimation of distribution algorithm for lot-streaming flow shop problems with setup times. Omega 40(2), 166–180 (2012)
Xu, Y., Wang, L., Wang, S.: An effective hybrid immune algorithm for solving the distributed permutation flow-shop scheduling problem. Eng. Optim. 46(9), 1269–1283 (2014)
Wang, S.Y., Wang, L., Liu, M.: An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem. Int. J. Prod. Econ. 145(1), 387–396 (2013)
Ruiz, R., Stützle, T.: An Iterated Greedy heuristic for the sequence dependent setup times flow shop problem with makespan and weighted tardiness objectives. Eur. J. Oper. Res. 187(3), 1143–1159 (2008)
Acknowledgements
This research is partially supported by the National Science Foundation of China (61963022) and National Science Foundation of China (51665025).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Zhang, S., Hu, R., Qian, B., Zhang, ZQ., Wang, L. (2021). Multidimensional Estimation of Distribution Algorithm for Distributed No-Wait Flow-Shop Scheduling Problem with Sequence-Independent Setup Times and Release Dates. In: Huang, DS., Jo, KH., Li, J., Gribova, V., Bevilacqua, V. (eds) Intelligent Computing Theories and Application. ICIC 2021. Lecture Notes in Computer Science(), vol 12836. Springer, Cham. https://doi.org/10.1007/978-3-030-84522-3_54
Download citation
DOI: https://doi.org/10.1007/978-3-030-84522-3_54
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-84521-6
Online ISBN: 978-3-030-84522-3
eBook Packages: Computer ScienceComputer Science (R0)