Abstract
Process planning and scheduling are two crucial components in a manufacturing system. The integration of the two functions has an important significance on improving the performance of the manufacturing system. However, integrated process planning and scheduling is an intractable non-deterministic polynomial-time (NP)-hard problem, and the multiple objectives requirement widely exists in real-world production situations. In this paper, a multi-objective mathematical model of integrated process planning and scheduling is set up with three different objectives: the overall finishing time (makespan), the maximum machine workload (MMW), and the total workload of machines (TWM). A multi-objective memetic algorithm (MOMA) is proposed to solve this problem. In MOMA, all the possible schedules are improved by a problem-specific multi-objective local search method, which combines a variable neighborhood search (VNS) procedure and an effective objective-specific intensification search method. Moreover, we adopt the TOPSIS method to select a satisfactory schedule scheme from the optimal Pareto front. The proposed MOMA is tested on typical benchmark instances and the experimental results are compared with those obtained by the well-known NSGA-II. Computational results show that MOMA is a promising and very effective method for the multi-objective IPPS problem.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Mohammadi G, Karampourhaghghi A, Samaei F (2012) A multi-objective optimisation model to integrating flexible process planning and scheduling based on hybrid multi-objective simulated annealing. Int J Prod Res 50(18):5063–5076. doi:10.1080/00207543.2011.631602
X-y W, X-y L, Gao L, H-y S (2014) Honey bees mating optimization algorithm for process planning problem. J Intell Manuf 25(3):459–472. doi:10.1007/s10845-012-0696-8
Lian KL, Zhang CY, Shao XY, Gao L (2012) Optimization of process planning with various flexibilities using an imperialist competitive algorithm. Int J Adv Manuf Tech 59(5-8):815–828. doi:10.1007/s00170-011-3527-8
Jain A, Jain PK, Singh IP (2006) An integrated scheme for process planning and scheduling in FMS. Int J Adv Manuf Tech 30(11-12):1111–1118. doi:10.1007/s00170-005-0142-6
Salehi M, Bahreininejad A (2011) Optimization process planning using hybrid genetic algorithm and intelligent search for job shop machining. J Intell Manuf 22(4):643–652. doi:10.1007/s10845-010-0382-7
Li X, Gao L, Wen X (2013) Application of an efficient modified particle swarm optimization algorithm for process planning. Int J Adv Manuf Tech 67(5-8):1355–1369. doi:10.1007/s00170-012-4572-7
Lv S, Qiao L (2013) A cross-entropy-based approach for the optimization of flexible process planning. Int J Adv Manuf Tech 68(9-12):2099–2110. doi:10.1007/s00170-013-4815-2
Gopala Krishna A, Mallikarjuna Rao K (2006) Optimisation of operations sequence in CAPP using an ant colony algorithm. Int J Adv Manuf Tech 29(1-2):159–164. doi:10.1007/s00170-004-2491-y
Mohapatra P, Nayak A, Kumar SK, Tiwari MK (2014) Multi-objective process planning and scheduling using controlled elitist non-dominated sorting genetic algorithm. Int J Prod Res 1–24. doi:10.1080/00207543.2014.957872
Zhang WJ, Xie SQ (2007) Agent technology for collaborative process planning: a review. Int J Adv Manuf Tech 32(3-4):315–325. doi:10.1007/s00170-005-0345-x
Li XY, Shao XY, Gao L (2008) Optimization of flexible process planning by genetic programming. Int J Adv Manuf Tech 38(1-2):143–153. doi:10.1007/s00170-007-1069-x
Li XY, Shao XY, Gao L, Qian WR (2010) An effective hybrid algorithm for integrated process planning and scheduling. Int J Prod Econ 126(2):289–298. doi:10.1016/j.ijpe.2010.04.001
Lian KL, Zhang CY, Gao L, Li XY (2012) Integrated process planning and scheduling using an imperialist competitive algorithm. Int J Prod Res 50(15):4326–4343. doi:10.1080/00207543.2011.622310
Kim YK, Park K, Ko J (2003) A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling. Comput Oper Res 30(8):1151–1171. doi:10.1016/s0305-0548(02)00063-1
Kumar M, Rajotia S (2006) Integration of process planning and scheduling in a job shop environment. Int J Adv Manuf Tech 28(1-2):109–116. doi:10.1007/s00170-004-2317-y
Lee H, Kim SS (2001) Integration of process planning and scheduling using simulation based genetic algorithms. Int J Adv Manuf Tech 18(8):586–590. doi:10.1007/s001700170035
Saygin C, Kilic SE (1999) Integrating flexible process plans with scheduling in flexible manufacturing systems. Int J Adv Manuf Tech 15(4):268–280. doi:10.1007/s001700050066
Li XY, Gao L, Li WD (2012) Application of game theory based hybrid algorithm for multi-objective integrated process planning and scheduling. Expert Syst Appl 39(1):288–297. doi:10.1016/j.eswa.2011.07.019
Özgüven C, Özbakır L, Yavuz Y (2010) Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Appl Math Model 34(6):1539–1548. doi:10.1016/j.apm.2009.09.002
Tan W, Khoshnevis B (2004) A linearized polynomial mixed integer programming model for the integration of process planning and scheduling. J Intell Manuf 15(5):593–605. doi:10.1023/B:JIMS.0000037710.80847.b6
Shao XY, Li XY, Gao L, Zhang CY (2009) Integration of process planning and scheduling—a modified genetic algorithm-based approach. Comput Oper Res 36(6):2082–2096. doi:10.1016/j.cor.2008.07.006
Nowicki E, Smutnicki C (1996) A fast taboo search algorithm for the job shop problem. Manage Sci 42(6):797–813. doi:10.1287/mnsc.42.6.797
Li XY, Gao L, Shao XY (2012) An active learning genetic algorithm for integrated process planning and scheduling. Expert Syst Appl 39(8):6683–6691. doi:10.1016/j.eswa.2011.11.074
Lihong Q, Shengping L (2012) An improved genetic algorithm for integrated process planning and scheduling. Int J Adv Manuf Tech 58(5-8):727–740. doi:10.1007/s00170-011-3409-0
Zhang L, Wong TN (2015) An object-coding genetic algorithm for integrated process planning and scheduling. Eur J Oper Res 244(2):434–444. doi:10.1016/j.ejor.2015.01.032
Baykasoglu A, Ozbakir L (2009) A grammatical optimization approach for integrated process planning and scheduling. J Intell Manuf 20(2):211–221. doi:10.1007/s10845-008-0223-0
Seker A, Erol S, Botsali R (2013) A neuro-fuzzy model for a new hybrid integrated Process Planning and Scheduling system. Expert Syst Appl 40(13):5341–5351. doi:10.1016/j.eswa.2013.03.043
Li WD, McMahon CA (2007) A simulated annealing-based optimization approach for integrated process planning and scheduling. Int J Comp Integ M 20(1):80–95. doi:10.1080/09511920600667366
Guo YW, Li WD, Mileham AR, Owen GW (2009) Applications of particle swarm optimisation in integrated process planning and scheduling. Robot Cim-Int Manuf 25(2):280–288. doi:10.1016/j.rcim.2007.12.002
Jin L, Zhang C, Shao X (2015) An effective hybrid honey bee mating optimization algorithm for integrated process planning and scheduling problems. Int J Adv Manuf Tech 80(5-8):1253–1264. doi:10.1007/s00170-015-7069-3
Haddadzade M, Razfar MR, Zarandi MHF (2014) Integration of process planning and job shop scheduling with stochastic processing time. Int J Adv Manuf Tech 71(1-4):241–252. doi:10.1007/s00170-013-5469-9
Shukla SK, Tiwari MK, Son YJ (2008) Bidding-based multi-agent system for integrated process planning and scheduling: a data-mining and hybrid tabu-SA algorithm-oriented approach. Int J Adv Manuf Tech 38(1-2):163–175. doi:10.1007/s00170-007-1087-8
Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE T Evolut Comput 6(2):182–197. doi:10.1109/4235.996017
Hwang C-L, Yoon K (1981) Multiple attribute decision making: methods and applications a state-of-the-art survey. Springer-Verlag
Qiu X, Lau HK (2014) An AIS-based hybrid algorithm for static job shop scheduling problem. J Intell Manuf 25(3):489–503. doi:10.1007/s10845-012-0701-2
Gen M, Lin L (2014) Multiobjective evolutionary algorithm for manufacturing scheduling problems: state-of-the-art survey. J Intell Manuf 25(5):849–866. doi:10.1007/s10845-013-0804-4
Bierwirth C (1995) A generalized permutation approach to job shop scheduling with genetic algorithms. Oper Res Spektrum 17(2-3):87–92. doi:10.1007/BF01719250
Tseng HE (2006) Guided genetic algorithms for solving a larger constraint assembly problem. Int J Prod Res 44(3):601–625. doi:10.1080/00207540500270513
Bierwirth C, Mattfeld DC (1999) Production scheduling and rescheduling with genetic algorithms. Evol Comput 7(1):1–17. doi:10.1162/evco.1999.7.1.1
Cheng R, Gen M, Tsujimura Y (1996) A tutorial survey of job-shop scheduling problems using genetic algorithms—I. Representation. Comput Ind Eng 30(4):983–997. doi:10.1016/0360-8352(96)00047-2
Zhang F, Zhang YF, Nee AYC (1997) Using genetic algorithms in process planning for job shop machining. IEEE T Evolut Comput 1(4):278–289. doi:10.1109/4235.687888
Mastrolilli M, Gambardella L (1996) Effective neighborhood functions for the flexible job shop problem. J Sched 3(3):3–20
Zheng J, Ling C, Shi Z, Xue J, Li X (2004) A multi-objective genetic algorithm based on quick sort. In: Tawfik A, Goodwin S (eds) Advances in artificial intelligence, vol 3060, Lecture Notes in Computer Science. Springer, Berlin, pp 175–186. doi:10.1007/978-3-540-24840-8_13
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no competing interests.
Rights and permissions
About this article
Cite this article
Jin, L., Zhang, C., Shao, X. et al. A multi-objective memetic algorithm for integrated process planning and scheduling. Int J Adv Manuf Technol 85, 1513–1528 (2016). https://doi.org/10.1007/s00170-015-8037-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-015-8037-7