SpringerLink
Log in

Hybrid artificial immune algorithm for energy-efficient distributed flexible job shop in semiconductor manufacturing

  • Published:
Cluster Computing Aims and scope Submit manuscript

Abstract

In semiconductor manufacturing, constraints, including multiple scheduling routes, complex production processes, and robotic transportation, particularly bring difficult challenges to production schedules. To address this issue, we investigated an energy-efficient distributed flexible job shop scheduling problem with robotic transportation. In the considered problem, two objectives, i.e., the maximum completion time and total energy consumption, are minimized simultaneously. First, two mixed integer linear programming models are constructed, including the sequence-based and position-based models. Then, a hybrid algorithm combining the artificial immune algorithm and variable neighborhood search algorithm is proposed. To generate a population with better performance and diversity, five initialization strategies and an active decoding method are designed. In addition, a novel clone mechanism and an improved suppression process are being developed to improve the exploration abilities. Furthermore, two distinct neighborhood structures and two object-oriented local search heuristics are designed to balance exploration and exploitation capabilities. Eventually, the proposed algorithm achieved better performance with the comparison of three other state-of-the-art algorithms with different scale instances.

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
EUR 32.99 /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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

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

Similar content being viewed by others

Data availability

The data sets supporting the results of this article are included within the article and its additional files.

Code availability

Custom code.

References

  1. Jamrus, T., Chien, C.F., Gen, M., Sethanan, K.: Hybrid particle swarm optimization combined with genetic operators for flexible job-shop scheduling under uncertain processing time for semiconductor manufacturing. IEEE Trans. Semicond. Manuf. 31(1), 32–41 (2017)

    Google Scholar 

  2. Park, I.B., Huh, J., Kim, J., Park, J.: A reinforcement learning approach to robust scheduling of semiconductor manufacturing facilities. IEEE Trans. Autom. Sci. Eng. 17(3), 1420–1431 (2019)

    Google Scholar 

  3. Knopp, S., Dauzère-Pérès, S., Yugma, C.: Flexible job-shop scheduling with extended route flexibility for semiconductor manufacturing. In: Proceedings of the Winter Simulation Conference 2014, pp. 2478–2489. IEEE (2014)

  4. Zheng, X.L., Wang, L., Wang, S.Y.: A novel fruit fly optimization algorithm for the semiconductor final testing scheduling problem. Knowl.-Based Syst. 57, 95–103 (2014)

    Google Scholar 

  5. Mönch, L., Fowler, J.W., Dauzère-Pérès, S., Mason, S.J., Rose, O.: A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. J. Sched. 14(6), 583–599 (2011)

    MathSciNet  Google Scholar 

  6. Wang, L., Deng, J., Wang, S.Y.: A review of distributed Job Shop scheduling Optimization algorithm. Control Decis. 01, 1–11 (2016). https://doi.org/10.13195/j.kzyjc.2014.1949

    Article  Google Scholar 

  7. Meng, L., Zhang, C., Ren, Y., Zhang, B., Lv, C.: Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem. Comput. Ind. Eng. 142, 106347 (2020)

    Google Scholar 

  8. Türkyılmaz, A., Şenvar, Ö., Ünal, İ, Bulkan, S.: A research survey: heuristic approaches for solving multi objective flexible job shop problems. J. Intell. Manuf. 31(8), 1949–1983 (2020)

    Google Scholar 

  9. De Giovanni, L., Pezzella, F.: An improved genetic algorithm for the distributed and flexible job-shop scheduling problem. Eur. J. Oper. Res. 200(2), 395–408 (2010)

    Google Scholar 

  10. Wang, H., Sheng, B., Lu, Q., Yin, X., Zhao, F., Lu, X., Fu, G.: A novel multi-objective optimization algorithm for the integrated scheduling of flexible job shops considering preventive maintenance activities and transportation processes. Soft Comput. 1–27 (2020)

  11. Li, J.Q., Chen, X.L., Duan, P.Y., Mou, J.H.: KMOEA: a knowledge-based multi-objective algorithm for distributed hybrid flow shop in a prefabricated system. IEEE Trans. Ind. Inf. (2022). https://doi.org/10.1109/TII.2021.3128405

    Article  Google Scholar 

  12. Li, J.Q., Han, Y.Y., Gao, K.Z., **ao, X.M., Duan, P.Y.: Bi-population balancing multi-objective algorithm for fuzzy flexible job shop with energy and transportation. IEEE Trans. Autom. Sci. Eng. (2023). https://doi.org/10.1109/TASE.2023.3300922

    Article  Google Scholar 

  13. Soto, C., Dorronsoro, B., Fraire, H., Cruz-Reyes, L., Gomez-Santillan, C., Rangel, N.: Solving the multi-objective flexible job shop scheduling problem with a novel parallel branch and bound algorithm. Swarm Evol. Comput. 53, 100632 (2020)

    Google Scholar 

  14. Li, J., Liu, Z.M., Li, C., Zheng, Z.: Improved artificial immune system algorithm for Type-2 fuzzy flexible job shop scheduling problem. IEEE Trans. Fuzzy Syst. (2020). https://doi.org/10.1109/TFUZZ.2020.3016225

    Article  Google Scholar 

  15. Chen, X.L., Li, J.Q., Du, Y.: A hybrid evolutionary immune algorithm for fuzzy flexible job shop scheduling problem with variable processing speeds. Expert Syst. Appl. 120891 (2023)

  16. Liu, T.K., Chen, Y.P., Chou, J.H.: Solving distributed and flexible job-shop scheduling problems for a real-world fastener manufacturer. IEEE Access 2, 1598–1606 (2014)

    Google Scholar 

  17. Lu, P.H., Wu, M.C., Tan, H., Peng, Y.H., Chen, C.F.: A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems. J. Intell. Manuf. 29(1), 19–34 (2018)

    Google Scholar 

  18. Chang, H.C., Liu, T.K.: Optimisation of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms. J. Intell. Manuf. 28(8), 1973–1986 (2017)

    Google Scholar 

  19. Wu, M.C., Lin, C.S., Lin, C.H., Chen, C.F.: Effects of different chromosome representations in develo** genetic algorithms to solve DFJS scheduling problems. Comput. Oper. Res. 80, 101–112 (2017)

    MathSciNet  Google Scholar 

  20. Wu, X., Liu, X., Zhao, N.: An improved differential evolution algorithm for solving a distributed assembly flexible job shop scheduling problem. Memetic Comput. 11(4), 1–21 (2019)

    Google Scholar 

  21. Luo, Q., Deng, Q., Gong, G., Zhang, L., Han, W., Li, K.: An efficient memetic algorithm for distributed flexible job shop scheduling problem with transfers. Expert Syst. Appl. 160, 113721 (2020)

    Google Scholar 

  22. Lin, C.S., Li, P.Y., Wei, J.M., Wu, M.C.: Integration of process planning and scheduling for distributed flexible job shops. Comput. Oper. Res. 124, 105053 (2020)

    MathSciNet  Google Scholar 

  23. Xu, W., Hu, Y., Luo, W., Wang, L., Wu, R.: A multi-objective scheduling method for distributed and flexible job shop based on hybrid genetic algorithm and Tabu search considering operation outsourcing and carbon emission. Comput. Ind. Eng. 157, 107318 (2021)

    Google Scholar 

  24. Wang, J., Liu, Y., Ren, S., Wang, C., Wang, W.: Evolutionary game based real-time scheduling for energy-efficient distributed and flexible job shop. J. Clean. Prod. 293, 126093 (2021)

    Google Scholar 

  25. Du, Y., Li, J.Q., Chen, X.L., Duan, P.Y., Pan, Qk.: A knowledge-based reinforcement learning and estimation of distribution algorithm for flexible job shop scheduling problem. IEEE Trans. Emerg. Topics Comput. Intell. (2022). https://doi.org/10.1109/TETCI.2022.3145706

    Article  Google Scholar 

  26. Qi, R., Li, J.Q., Liu, X.F.: A knowledge-driven multiobjective optimization algorithm for the transportation of assembled prefabricated components with multi-frequency visits. Autom. Constr. 152, 104944 (2023)

    Google Scholar 

  27. Shabtay, D., Arviv, K.: Optimal robot scheduling to minimize the makespan in a three-machine flow-shop environment with job-independent processing times. Appl. Math. Model. 40(5–6), 4231–4247 (2016)

    MathSciNet  Google Scholar 

  28. Karimi, S., Ardalan, Z., Naderi, B., Mohammadi, M.: Scheduling flexible job-shops with transportation times: mathematical models and a hybrid imperialist competitive algorithm. Appl. Math. Modell. 41, 667–682 (2017)

    MathSciNet  Google Scholar 

  29. Du, Y., Li, J., Li, C., Duan, P.: A reinforcement learning approach for flexible job shop scheduling problem with crane transportation and setup times. IEEE Trans. Neural Netw. Learn. Syst

  30. Dai, M., Tang, D., Giret, A., Salido, M.A.: Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints. Robot. Comput.-Integr. Manuf. 59, 143–157 (2019)

    Google Scholar 

  31. Li, J.Q., Du, Y., Gao, K.Z., Duan, P.Y., Gong, D.W., Pan, Q.K., Suganthan, P.N.: A hybrid iterated greedy algorithm for a crane transportation flexible job shop problem. IEEE Trans. Autom. Sci. Eng. 1–18 (2020)

  32. Wu, X., Peng, J., **ao, X., Wu, S.: An effective approach for the dual-resource flexible job shop scheduling problem considering loading and unloading. J. Intell. Manuf. 32(3), 707–728 (2021)

    Google Scholar 

  33. Lu, C., Gao, L., Li, X., **ao, S.: A hybrid multi-objective grey wolf optimizer for dynamic scheduling in a real-world welding industry. Eng. Appl. Artif. Intell. 57, 61–79 (2017)

    Google Scholar 

  34. Li, J.Q., Deng, J.W., Li, C.Y., Han, Y.Y., Tian, J., Zhang, B., Wang, C.G.: An improved Jaya algorithm for solving the flexible job shop scheduling problem with transportation and setup times. Knowl.-Based Syst. 200, 106032 (2020)

    Google Scholar 

  35. Luo, Q., Deng, Q., Gong, G., Zhang, L., Han, W., Li, K.: An efficient memetic algorithm for distributed flexible job shop scheduling problem with transfers. Expert Syst. Appl. 160, 113721 (2020)

    Google Scholar 

  36. Zhou, B., Liao, X.: Particle filter and Levy flight-based decomposed multi-objective evolution hybridized particle swarm for flexible job shop greening scheduling with crane transportation. Appl. Soft Comput. 91, 106217 (2020)

    Google Scholar 

  37. Du, Y., Li, J.Q., Luo, C., Meng, L.L.: A hybrid estimation of distribution algorithm for distributed flexible job shop scheduling with crane transportations. Swarm Evol. Comput. 62, 100861 (2021)

    Google Scholar 

  38. Wang, L., Wang, J.J., Wu, C.G.: Research progress on optimization of green job shop scheduling. Control Decis. 03, 385–391 (2018). https://doi.org/10.13195/j.kzyjc.2017.0215

    Article  Google Scholar 

  39. Piroozfard, H., Wong, K.Y., Wong, W.P.: Minimizing total carbon footprint and total late work criterion in flexible job shop scheduling by using an improved multi-objective genetic algorithm.Resources. Conserv. Recycl. 128, 267–283 (2018)

    Google Scholar 

  40. Ebrahimi, A., Jeon, H.W., Lee, S., Wang, C.: Minimizing total energy cost and tardiness penalty for a scheduling-layout problem in a flexible job shop system: a comparison of four metaheuristic algorithms. Comput. Ind. Eng. 141, 106295 (2020)

    Google Scholar 

  41. Wang, J.J., Wang, L.: A knowledge-based cooperative algorithm for energy-efficient scheduling of distributed flow-shop. IEEE Trans. Syst. Man Cybern. 99, 1–15 (2018)

    Google Scholar 

  42. Liu, Z., Guo, S., Wang, L.: Integrated green scheduling optimization of flexible job shop and crane transportation considering comprehensive energy consumption. J. Clean. Prod. 211, 765–786 (2019)

    Google Scholar 

  43. **e, J., Gao, L., Pan, Q.K., Tasgetiren, M.F.: An effective multi-objective artificial bee colony algorithm for energy efficient distributed job shop scheduling. Procedia Manuf. 39, 1194–1203 (2019)

    Google Scholar 

  44. Fu, Y., Tian, G., Fathollahi-Fard, A.M., Ahmadi, A., Zhang, C.: Stochastic multi-objective modelling and optimization of an energy-conscious distributed permutation flow shop scheduling problem with the total tardiness constraint. J. Clean. Prod. 226, 515–525 (2019)

    Google Scholar 

  45. Li, Y., Huang, W., Wu, R., Guo, K.: An improved artificial bee colony algorithm for solving multi-objective low-carbon flexible job shop scheduling problem. Appl. Soft Comput. 95, 106544 (2020)

    Google Scholar 

  46. Pan, Z., Lei, D., Wang, L.: A bi-population evolutionary algorithm with feedback for energy-efficient fuzzy flexible job shop scheduling. IEEE Trans. Syst. Man Cybern. (2021)

  47. Al-Anzi, F.S., Allahverdi, A.: An artificial immune system heuristic for two-stage multi-machine assembly scheduling problem to minimize total completion time. J. Manuf. Syst. 32(4), 825–830 (2013)

    Google Scholar 

  48. Lin, S., Ying, K.: Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm. Omega-Int. J. Manag. Sci. 41(2), 383–389 (2013)

    Google Scholar 

  49. Liu, X., Chung, T.P.: An outsourcing-scheduling problem in a two-stage supply chain via improved immunoglobulin-based artificial immune system. Comput. Ind. Eng. 113, 819–830 (2017)

    Google Scholar 

  50. Chung, T.P., Chen, F.: A complete immunoglobulin-based artificial immune system algorithm for two-stage assembly flowshop scheduling problem with part splitting and distinct due windows. Int. J. Prod. Res. 57(10), 3219–3237 (2019)

    Google Scholar 

  51. Chen, X.L., Li, J.Q., Han, Y.Y., Sang, H.Y.: Improved artificial immune algorithm for the flexible job shop problem with transportation time. Meas. Control 53(9–10), 2111–2128 (2020)

    Google Scholar 

  52. Zhang, P., Song, S., Niu, S., Zhang, R.: A hybrid artificial immune-simulated annealing algorithm for multiroute job shop scheduling problem with continuous limited output buffers. IEEE Trans. Cybern. 52(11), 12112–12125 (2021)

    Google Scholar 

  53. Roshanaei, V., Azab, A., Elmaraghy, H.A.: Mathematical modelling and a meta-heuristic for flexible job shop scheduling. Int. J. Prod. Res. 51(20), 6247–6274 (2013)

    Google Scholar 

  54. Lei, D., Li, M., Wang, L.: A two-phase meta-heuristic for multiobjective flexible job shop scheduling problem with total energy consumption threshold. IEEE Trans. Cybern. 49(3), 1097–1109 (2018)

    Google Scholar 

  55. Liu, Z., Wang, J., Zhang, C., Chu, H., Ding, G., Zhang, L.: A hybrid genetic-particle swarm algorithm based on multilevel neighbourhood structure for flexible job shop scheduling problem. Comput. Oper. Res. 135, 105431 (2021)

    MathSciNet  Google Scholar 

  56. Wu, R., Guo, S.S., Li, Y.B., Wang, L., Xu, W.X.: Improved artificial Bee Colony algorithm for distributed flexible Job Shop scheduling problem. Control Decis. 34(12), 2527–2536 (2019)

    Google Scholar 

Download references

Acknowledgements

The authors would like to declare that the work described was original research that has not been published previously, and not under consideration for publication elsewhere, in whole or in part.

Funding

This research has received no funding support.

Author information

Authors and Affiliations

  1. School of Information Science and Engineering, Shandong Normal University, **an, 250014, China

    Chen **aolong

  2. School of Information Engineering, Heng**ng University, Qingdao, China

    Chen **aolong

  3. School of Information Science and Engineering, University of **an, **an, 250022, China

    Du Yu

Authors
  1. Chen **aolong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Du Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

CX: Methodology, Writing—original draft, Formal analysis, Validation; DY: Data curation, Software, Supervision.

Corresponding author

Correspondence to Chen **aolong.

Ethics declarations

Competing interests

The authors declare no competing interests.

Ethical approval

Ethical approval is not applicable here.

Consent to participate

Consent to participate is not applicable here.

Consent for publication

Consent for publication is not applicable here.

Additional information

Publisher's Note

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

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

**aolong, C., Yu, D. Hybrid artificial immune algorithm for energy-efficient distributed flexible job shop in semiconductor manufacturing. Cluster Comput 27, 3075–3098 (2024). https://doi.org/10.1007/s10586-023-04127-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10586-023-04127-2

Keywords

Search

Navigation