Abstract
Motivated by a real-world application, we consider an Assembly Job Shop Scheduling Problem (AJSSP), with three objectives: product quality, product quantity, and first product lead time. Using real-world inspection data, we demonstrate the ability to model product quality transformations during assembly jobs via genetic programming by considering the quality attributes of subparts. We investigate integrating quality transformation models into an AJSSP. Through the use of the de facto standard multi-objective evolutionary algorithm, NSGA-II, and a novel genotype to handle the constraints, we describe an evolutionary approach to optimizing all stated objectives. This approach is empirically shown to outperform random search and hill climbing in both performance and usability metrics expected to be valuable to administrators involved in plant scheduling and operations.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ahmadi, E., Zandieh, M., Farrokh, M., Emami, S.M.: A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms. Comput. Oper. Res. 73, 56–66 (2016). https://doi.org/10.1016/j.cor.2016.03.009
Al-Hinai, N., ElMekkawy, T.Y.: Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm. Int. J. Prod. Econ. 132(2), 279–291 (2011). https://doi.org/10.1016/j.ijpe.2011.04.020
Chan, F.T., Wong, T., Chan, L.: A genetic algorithm-based approach to job shop scheduling problem with assembly stage. In: 2008 IEEE International Conference on Industrial Engineering and Engineering Management, pp. 331–335. IEEE (2008). https://doi.org/10.1109/IEEM.2008.4737885
Dabhi, V.K., Chaudhary, S.: Empirical modeling using genetic programming: a survey of issues and approaches. Natural Comput. 14(2), 303–330 (2014). https://doi.org/10.1007/s11047-014-9416-y
Deb, K., Jain, H.: An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: Solving problems with box constraints. IEEE Trans. Evol. Comput. 18(4), 577–601 (2013). https://doi.org/10.1109/TEVC.2013.2281535
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002). https://doi.org/10.1109/4235.996017
Elarbi, M., Bechikh, S., Gupta, A., Said, L.B., Ong, Y.S.: A new decomposition-based NSGA-II for many-objective optimization. IEEE Trans. Syst. Man Cybern. Syst. 48(7), 1191–1210 (2017). https://doi.org/10.1109/TSMC.2017.2654301
Frutos, M., Olivera, A.C., Tohmé, F.: A memetic algorithm based on a nsgaii scheme for the flexible job-shop scheduling problem. Annal. Oper. Res. 181(1), 745–765 (2010). https://doi.org/10.1007/s10479-010-0751-9
Gao, K., Cao, Z., Zhang, L., Chen, Z., Han, Y., Pan, Q.: A review on swarm intelligence and evolutionary algorithms for solving flexible job shop scheduling problems. IEEE/CAA J. Automatica Sinica 6(4), 904–916 (2019). https://doi.org/10.1109/JAS.2019.1911540
Gen, M., Lin, L.: Multiobjective evolutionary algorithm for manufacturing scheduling problems: state-of-the-art survey. J. Intell. Manuf. 25(5), 849–866 (2014). https://doi.org/10.1007/s10845-013-0804-4
Koza, J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection, vol. 1. MIT Press, Cambridge (1992)
Lu, H., Huang, G.Q., Yang, H.: Integrating order review/release and dispatching rules for assembly job shop scheduling using a simulation approach. Int. J. Prod. Res. 49(3), 647–669 (2011). https://doi.org/10.1080/00207540903524490
Lv, H., Han, G.: Research of assembly job shop scheduling problem based on modified genetic programming. In: 2017 10th International Symposium on Computational Intelligence and Design (ISCID), vol. 2, pp. 147–151. IEEE (2017). https://doi.org/10.1109/ISCID.2017.120
Poli, R., Langdon, W.B., McPhee, N.F., Koza, J.R.: A Field Guide to Genetic Programming. Lulu. com (2008)
Potts, C.N., Sevast’Janov, S., Strusevich, V.A., Van Wassenhove, L.N., Zwaneveld, C.M.: The two-stage assembly scheduling problem: Complexity and approximation. Oper. Res. 43(2), 346–355 (1995). https://doi.org/10.1287/opre.43.2.346
Rahm, E., Do, H.H.: Data cleaning: problems and current approaches. IEEE Data Eng. Bull. 23(4), 3–13 (2000)
Thiagarajan, S., Rajendran, C.: Scheduling in dynamic assembly job-shops to minimize the sum of weighted earliness, weighted tardiness and weighted flowtime of jobs. Comput. Industr. Eng. 49(4), 463–503 (2005). https://doi.org/10.1016/j.cie.2005.06.005
Wang, Y.M., Yin, H.L., Da Qin, K.: A novel genetic algorithm for flexible jobshop scheduling problems with machine disruptions. Int. J. Adv. Manuf. Technol. 68(5-8), 1317–1326 (2013).https://doi.org/10.1007/s00170-013-4923-z
Wong, T.C., Chan, F.T., Chan, L.: A resource-constrained assembly job shop scheduling problem with lot streaming technique. Comput. Industr. Eng. 57(3), 983–995 (2009). https://doi.org/10.1016/j.cie.2009.04.002
Wong, T.C., Ngan, S.C.: A comparison of hybrid genetic algorithm and hybrid particle swarm optimization to minimize makespan for assembly job shop. Appl. Soft. Comput. 13(3), 1391–1399 (2013). https://doi.org/10.1016/j.asoc.2012.04.007
Zhang, Q.s., Zhu, S.C.: Visual interpretability for deep learning: a survey. Frontiers Inf. Technol. Electron. Eng. 19(1), 27–39 (2018)
Zhang, S., Li, X., Zhang, B., Wang, S.: Multi-objective optimisation in flexible assembly job shop scheduling using a distributed ant colony system. Eur. J. Oper. Res. 283(2), 441–460 (2020). https://doi.org/10.1016/j.ejor.2019.11.016
Acknowledgements
This work is funded by the Department of Energy’s Kansas City National Security Campus, operated by Honeywell Federal Manufacturing & Technologies, LLC, under contract number DE-NA0002839.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG and Honeywell Federal Manufacturing & Technologies, LLC
About this paper
Cite this paper
Prince, M.H., DeHaan, K., Tauritz, D.R. (2021). A Multi-objective Evolutionary Algorithm Approach for Optimizing Part Quality Aware Assembly Job Shop Scheduling Problems. In: Castillo, P.A., Jiménez Laredo, J.L. (eds) Applications of Evolutionary Computation. EvoApplications 2021. Lecture Notes in Computer Science(), vol 12694. Springer, Cham. https://doi.org/10.1007/978-3-030-72699-7_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-72699-7_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-72698-0
Online ISBN: 978-3-030-72699-7
eBook Packages: Computer ScienceComputer Science (R0)