An estimation of distribution algorithm with multiple intensification strategies for two-stage hybrid flow-shop scheduling problem with sequence-dependent setup time | Applied Intelligence Skip to main content
Springer Nature Link
Log in

An estimation of distribution algorithm with multiple intensification strategies for two-stage hybrid flow-shop scheduling problem with sequence-dependent setup time

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

The estimation of distribution algorithm (EDA) has recently emerged as a promising alternative to the traditional evolutionary algorithms for solving combinatorial optimization problems. In this paper, an estimation of distribution algorithm with multiple intensification strategies (EDA-MIS) is proposed to solve a typical kind of hybrid flow-shop scheduling problem. The two-stage heterogeneous hybrid flow-shop scheduling problem is investigated. The sequence-dependent setup time at the first stage is also considered. In the proposed EDA-MIS, the initial population is constructed through the heuristic method and random strategy. An order matrix is established to estimate the probabilistic model of promising solutions. Then the solutions of the algorithm are evolved through the processes of selection, recombination, sampling, and local search. The obtained results indicate that the EDA-MIS provides good solutions in the aspects of solution quality and computational efficiency.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Shao Z, Shao W, Pi D (2020) Effective constructive heuristic and metaheuristic for the distributed assembly blocking flow-shop scheduling problem. Appl Intell 50:4647–4669. https://doi.org/10.1007/s10489-020-01809-x

    Article  Google Scholar 

  2. Zhao F, Xue F, Zhang Y, Ma W, Zhang C, Song H (2019) A discrete gravitational search algorithm for the blocking flow shop problem with total flow time minimization. Appl Intell 49:3362–3382. https://doi.org/10.1007/s10489-019-01457-w

    Article  Google Scholar 

  3. Li H, He F, Chen Y, Pan Y (2021) MLFS-CCDE: multi-objective large-scale feature selection by cooperative coevolutionary differential evolution. Memetic Computing 13:1–18. https://doi.org/10.1007/s12293-021-00328-7

    Article  Google Scholar 

  4. Zhao F, He X, Zhang Y, Lei W, Ma W, Zhang C, Song H (2020) A jigsaw puzzle inspired algorithm for solving large-scale no-wait flow shop scheduling problems. Appl Intell 50:87–100

    Article  Google Scholar 

  5. Ruiz R, Vazquez-Rodriguez JA (2010) The hybrid flow shop scheduling problem. Eur J Oper Res 205:1–18. https://doi.org/10.1016/j.ejor.2009.09.024

    Article  MathSciNet  MATH  Google Scholar 

  6. Lin S-W, Cheng C-Y, Pourhejazy P, Ying KC, Lee CH (2021) New benchmark algorithm for hybrid flowshop scheduling with identical machines. Expert Syst Appl 183:1–10. https://doi.org/10.1016/j.eswa.2021.115422

    Article  Google Scholar 

  7. Cai J, Lei D (2020) Distributed two-stage hybrid flow shop scheduling with setup times. Comput Integr Manuf Syst 26:2170–2179. https://doi.org/10.13196/j.cims.2020.08.017

    Article  Google Scholar 

  8. Li J, Li W, Tao X et al (2020) A survey on time constrained hybrid flow shop scheduling problems. Control Theory Appl 37:2273–2290

    MATH  Google Scholar 

  9. Long J, Zheng Z, Gao X, Pardalos PM (2018) Scheduling a realistic hybrid flow shop with stage skipping and adjustable processing time in steel plants. Appl Soft Comput 64:536–549

    Article  Google Scholar 

  10. Cai J, Lei D (2021) A cooperated shuffled frog-leaping algorithm for distributed energy-efficient hybrid flow shop scheduling with fuzzy processing time. Complex Intell Syst 7:2235–2253. https://doi.org/10.1007/s40747-021-00400-2

    Article  Google Scholar 

  11. Li Y, Li X, Gao L, Meng L (2020) An improved artificial bee colony algorithm for distributed heterogeneous hybrid flowshop scheduling problem with sequence-dependent setup times. Comput Ind Eng 147:106638. https://doi.org/10.1016/j.cie.2020.106638

    Article  Google Scholar 

  12. Meng L, Zhang C, Shao X, Zhang B, Ren Y, Lin W (2020) More MILP models for hybrid flow shop scheduling problem and its extended problems. Int J Prod Res 58:3905–3930. https://doi.org/10.1080/00207543.2019.1636324

    Article  Google Scholar 

  13. Meng L, Zhang C, Shao X, Ren Y, Ren C (2019) Mathematical modelling and optimisation of energy-conscious hybrid flow shop scheduling problem with unrelated parallel machines. Int J Prod Res 57:1119–1145. https://doi.org/10.1080/00207543.2018.1501166

    Article  Google Scholar 

  14. Zhong W, Shi Y (2018) Two-stage no-wait hybrid flowshop scheduling with inter-stage flexibility. J Comb Optim 35:108–125. https://doi.org/10.1007/s10878-017-0155-8

    Article  MathSciNet  MATH  Google Scholar 

  15. Missaoui A, Boujelbene Y (2021) An effective iterated greedy algorithm for blocking hybrid flow shop problem with due date window. Oper Res 55:1603–1616. https://doi.org/10.1051/ro/2021076

    Article  MathSciNet  Google Scholar 

  16. Chamnanlor C, Sethanan K, Gen M, Chien C-F (2017) Embedding ant system in genetic algorithm for re-entrant hybrid flow shop scheduling problems with time window constraints. J Intell Manuf 28:1915–1931. https://doi.org/10.1007/s10845-015-1078-9

    Article  Google Scholar 

  17. Wang S, Wang X, Yu L (2020) Two-stage no-wait hybrid flow-shop scheduling with sequence-dependent setup times. Int J Syst Sci: Operations and Logistics 7:291–307. https://doi.org/10.1080/23302674.2019.1575997

    Article  Google Scholar 

  18. Wang S, Kurz M, Mason SJ, Rashidi E (2019) Two-stage hybrid flow shop batching and lot streaming with variable sublots and sequence-dependent setups. Int J Prod Res 57:6893–6907. https://doi.org/10.1080/00207543.2019.1571251

    Article  Google Scholar 

  19. Shao W, Pi D, Shao Z (2019) A Pareto-based estimation of distribution algorithm for solving multiobjective distributed no-wait flow-shop scheduling problem with sequence-dependent setup time. IEEE Trans Autom Sci Eng 16:1344–1360. https://doi.org/10.1109/TASE.2018.2886303

    Article  Google Scholar 

  20. Li Y, Li X, Gao L, Zhang B, Pan QK, Tasgetiren MF, Meng L (2021) A discrete artificial bee colony algorithm for distributed hybrid flowshop scheduling problem with sequence-dependent setup times. Int J Prod Res 59:3880–3899. https://doi.org/10.1080/00207543.2020.1753897

    Article  Google Scholar 

  21. Shao W, Shao Z, Pi D (2020) Modeling and multi-neighborhood iterated greedy algorithm for distributed hybrid flow shop scheduling problem. Knowl-Based Syst 194:1–17. https://doi.org/10.1016/j.knosys.2020.105527

    Article  Google Scholar 

  22. Chen Y, He F, Li H, Zhang D, Wu Y (2020) A full migration BBO algorithm with enhanced population quality bounds for multimodal biomedical image registration. Appl Soft Comput J 93:106335

    Article  Google Scholar 

  23. Liang Y, He F, Zeng X, Luo J (2022) An improved loop subdivision to coordinate the smoothness and the number of faces via multi-objective optimization. Integr Comput Aided Eng 29:23–41. https://doi.org/10.3233/ICA-210661

    Article  Google Scholar 

  24. Liang Y, He F, Zeng X (2020) 3D mesh simplification with feature preservation based on whale optimization algorithm and differential evolution. Integr Comput Aided Eng 27:417–435

    Article  Google Scholar 

  25. Wang S, Liu M, Chu C (2015) A branch-and-bound algorithm for two-stage no-wait hybrid flow-shop scheduling. Int J Prod Res 53:1143–1167. https://doi.org/10.1080/00207543.2014.949363

    Article  Google Scholar 

  26. Öztop H, Fatih Tasgetiren M, Eliiyi DT, Pan Q-K (2019) Metaheuristic algorithms for the hybrid flowshop scheduling problem. Comput Oper Res 111:177–196. https://doi.org/10.1016/j.cor.2019.06.009

    Article  MathSciNet  MATH  Google Scholar 

  27. Marichelvam MK, Geetha M, Tosun Ö (2020) An improved particle swarm optimization algorithm to solve hybrid flowshop scheduling problems with the effect of human factors – a case study. Comput Oper Res 114:1–9. https://doi.org/10.1016/j.cor.2019.104812

    Article  MathSciNet  MATH  Google Scholar 

  28. Zhang B, Pan Q, Gao L et al (2020) A three-stage multiobjective approach based on decomposition for an energy-efficient hybrid flow shop scheduling problem. IEEE Trans Syst Man Cybern, Syst 50:4984–4999. https://doi.org/10.1109/TSMC.2019.2916088

    Article  Google Scholar 

  29. Lu C, Gao L, Pan Q, Li X, Zheng J (2019) A multi-objective cellular grey wolf optimizer for hybrid flowshop scheduling problem considering noise pollution. Appl Soft Comput 75:728–749. https://doi.org/10.1016/j.asoc.2018.11.043

    Article  Google Scholar 

  30. Shao W, Shao Z, Pi D (2021) Multi-objective evolutionary algorithm based on multiple neighborhoods local search for multi-objective distributed hybrid flow shop scheduling problem. Expert Syst Appl 183:1–17. https://doi.org/10.1016/j.eswa.2021.115453

    Article  Google Scholar 

  31. Zhang B, Pan Q-K, Meng L-L, Zhang XL, Ren YP, Li JQ, Jiang XC (2021) A collaborative variable neighborhood descent algorithm for the hybrid flowshop scheduling problem with consistent sublots. Appl Soft Comput 106:1–20. https://doi.org/10.1016/j.asoc.2021.107305

    Article  Google Scholar 

  32. Luo J, Liu Z, Xing K (2019) Hybrid branch and bound algorithms for the two-stage assembly scheduling problem with separated setup times. Int J Prod Res 57:1398–1412. https://doi.org/10.1080/00207543.2018.1489156

    Article  Google Scholar 

  33. Zhao F, Zhao J, Wang L, Tang J (2021) An optimal block knowledge driven backtracking search algorithm for distributed assembly No-wait flow shop scheduling problem. Appl Soft Comput 112:107750. https://doi.org/10.1016/j.asoc.2021.107750

    Article  Google Scholar 

  34. Wu C, Wang L, Wang J (2021) A path relinking enhanced estimation of distribution algorithm for direct acyclic graph task scheduling problem. Knowl-Based Syst 228:107255. https://doi.org/10.1016/j.knosys.2021.107255

    Article  Google Scholar 

  35. Sun Z, Gu X (2017) A novel hybrid estimation of distribution algorithm for solving hybrid flowshop scheduling problem with unrelated parallel machine. J Cent S Univ Technol 24:1779–1788

    Article  Google Scholar 

  36. Du Y, Li J, Luo C, Meng L (2021) A hybrid estimation of distribution algorithm for distributed flexible job shop scheduling with crane transportations. Swarm Evol Comput 62:1–24. https://doi.org/10.1016/j.swevo.2021.100861

    Article  Google Scholar 

  37. Vignier A, Billaut JC, Proust C (1999) Hybrid flowshop scheduling problems: state of the art

  38. Graham RL, Lawler EL, Lenstra JK, Kan A (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey - ScienceDirect. Anna Discrete Math 5:287–326

    Article  MATH  Google Scholar 

  39. Gupta JND (1988) Two-stage, hybrid Flowshop scheduling problem. Oper Res 39:359–364

    Article  MATH  Google Scholar 

  40. Liang JJ, Qu BY, Suganthan PN, Hernández-Díaz AG (2013) Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization. Technical Report, Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou China and Technical Report, Nanyang Technological University, Singapore

  41. Wang S, Wang L, Liu M, Xu Y (2015) An order-based estimation of distribution algorithm for stochastic hybrid flow-shop scheduling problem. Int J Comput Integr Manuf 28:307–320. https://doi.org/10.1080/0951192x.2014.880803

    Article  Google Scholar 

  42. Wang L, Wang S, Liu M (2013) A Pareto-based estimation of distribution algorithm for the multi-objective flexible job-shop scheduling problem. Int J Prod Res 51:3574–3592. https://doi.org/10.1080/00207543.2012.752588

    Article  Google Scholar 

  43. Zhou S, Li X, Chen H, Guo C (2016) Minimizing makespan in a no-wait flowshop with two batch processing machines using estimation of distribution algorithm. Int J Prod Res 54:4919–4937. https://doi.org/10.1080/00207543.2016.1140920

    Article  Google Scholar 

  44. Cui Z, Gu X (2015) An improved discrete artificial bee colony algorithm to minimize the makespan on hybrid flow shop problems. Neurocomputing 148:248–259. https://doi.org/10.1016/j.neucom.2013.07.056

    Article  Google Scholar 

  45. Umam MS, Mustafid M, Suryono S (2021) A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem. J King Saud Univ Comput Inf Sci. https://doi.org/10.1016/j.jksuci.2021.08.025

  46. Feinleib M, Zar J (1975) Biostatistical analysis. J Am Stat Assoc 70:257. https://doi.org/10.2307/2285423

    Article  Google Scholar 

Download references

Acknowledgments

This work was financially supported by the National Natural Science Foundation of China under grant 62063021. It was also supported by the Key talent project of Gansu Province (ZZ2021G50700016), the Key Research Programs of Science and Technology Commission Foundation of Gansu Province (21YF5WA086), Lanzhou Science Bureau project (2018-rc-98), and Project of Gansu Natural Science Foundation (21JR7RA204).

Author information

Authors and Affiliations

  1. School of Computer and Communication Technology, Lanzhou University of Technology, Lanzhou, China

    Huan Liu, Fuqing Zhao, Jie Cao & Jianxin Tang

  2. College of Information Science and Technology, Gansu Agricultural University, Lanzhou, 730070, China

    Huan Liu

  3. Department of Automation, Tsinghua University, Beijing, 10084, China

    Ling Wang

  4. Department of Industrial Engineering, University Andalas, Padang, 25163, Indonesia

    Jonrinaldi

Authors
  1. Huan Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fuqing Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ling Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jie Cao
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jianxin Tang
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Jonrinaldi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Fuqing Zhao.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Liu, H., Zhao, F., Wang, L. et al. An estimation of distribution algorithm with multiple intensification strategies for two-stage hybrid flow-shop scheduling problem with sequence-dependent setup time. Appl Intell 53, 5160–5178 (2023). https://doi.org/10.1007/s10489-022-03853-1

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-022-03853-1

Keywords

Search

Navigation