SOLVING PROCESS PLANNING, WEIGHTED APPARENT TARDINESS COST DISPATCHING, AND WEIGHTED PROCESSING PLUS WEIGHT DUE-DATE ASSIGNMENT SIMULTANEOUSLY USING A HYBRID SEARCH

Year 2018, Volume: 13 Issue: 4, 285 - 300, 13.10.2018

Caner Erden , Halil Ibrahim Demir , Mumtaz Ipek , Abdullah Hulusi Kokcam

Abstract

Process planning, scheduling,
and due date assignment play crucial role in manufacturing systems in terms of
efficient and flexible production. Integration of the production functions has
been studied in the literature. In this context, there are hundreds of works on
integrated process planning and scheduling (IPPS) and scheduling with due date
assignment (SWDDA) problems. In this paper, we extend the existing literature
works on integrated process planning, scheduling and due date assignment
(IPPSDDA) using a hybrid search algorithm. Since the scheduling problem is in
the NP-Hard problem class without any integration, integrated problem is even
harder to solve. This study focuses on the integration of these functions. Sum
of weighted tardiness, earliness, and due date related costs are used as a
penalty function. Random search and hybrid meta-heuristics are used to solve
integrated problem. We used hybrid and random search techniques while solving
the integrated problem. Full integration with hybrid search is found as the
best combination. So, hybrid search outperformed random search and ordinary
solutions were very poor compared to the search results.

Keywords

Genetic Algorithms, Hybrid Search, Weighted Due-Date Assignment, Process Planning and Scheduling, Scheduling with due date Assignment, Weighted Due-Date Assignment

SOLVING PROCESS PLANNING, WEIGHTED APPARENT TARDINESS COST DISPATCHING, AND WEIGHTED PROCESSING PLUS WEIGHT DUE-DATE ASSIGNMENT SIMULTANEOUSLY USING A HYBRID SEARCH

Abstract

Process planning, scheduling, and due date assignment play crucial role in manufacturing systems in terms of efficient and flexible production. Integration of the production functions has been studied in the literature. In this context, there are hundreds of works on integrated process planning and scheduling (IPPS) and scheduling with due date assignment (SWDDA) problems. In this paper, we extend the existing literature works on integrated process planning, scheduling and due date assignment (IPPSDDA) using a hybrid search algorithm. Since the scheduling problem is in the NP-Hard problem class without any integration, integrated problem is even harder to solve. This study focuses on the integration of these functions. Sum of weighted tardiness, earliness, and due date related costs are used as a penalty function. Random search and hybrid metaheuristics are used to solve integrated problem. We used hybrid and random search techniques while solving the integrated problem. Full integration with hybrid search is found as the best combination. So, hybrid search outperformed random search and ordinary solutions were very poor compared to the search results.

Keywords

Process Planning and Scheduling, Scheduling with due date Assignment, Genetic Algorithms, Hybrid Search, Weighted Due-Date Assignment

References

• [1] Zhang, H.C. and Mallur, S., (1994). An Integrated Model of Process Planning and Production Scheduling, International Journal of Computer Integrated Manufacturing, Vol:7, No:6, 356–364. doi:10.1080/09511929408944623.
• [2] Gordon, V.S., Proth, J.M., and Chu, C., (2002). Due date Assignment and Scheduling: SLK, TWK and other due Date Assignment Models, Production Planning and Control, Vol:13, No:2, 117–132. doi:10.1080/09537280110069621.
• [3] Demir, H.I. and Taşkın, H., (2005). Integrated Process Planning, Scheduling and Due-Date Assignment, Sakarya Üniversitesi, Sakarya, Turkey.
• [4] Ceven, E. and Demir, H.I., (2007). Benefits of Integrating Due-Date Assignment with Process Planning and Scheduling.
• [5] Demir, H.I., Uygun, O., Cil, I., Ipek, M., and Sari, M., (2015). Process Planning and Scheduling with SLK Due-Date Assignment where Earliness, Tardiness and Due-Dates are Punished, Journal of Industrial and Intelligent Information, Vol:3, No:3, 173–180. doi:10.12720/jiii.3.3.173-180.
• [6] Demir, H., Cakar, T., Ipek, M., Uygun, O., and Sari, M. (2015). Process Planning and Due-date Assignment with ATC Dispatching where Earliness, Tardiness and Due-dates are Punished, J. Ind. Intell. Inf. Vol.
• [7] Wei, T. and Khoshnevis, B., (2000). Integration of Process Planning and Scheduling: A Review, Journal of Intelligent Manufacturing, Vol:24, No:6, 51–63. doi:10.1080/0951192X.2011.562543.
• [8] Li, X., Gao, L., Zhang, C., and Shao, X., (2010). A Review on Integrated Process Planning and Scheduling, International Journal Of, Vol:5, No:2, pp:161–180.
• [9] Phanden, R., Jain, A., and Verma, R., (2011). Integration of Process Planning and Scheduling: A state-of-the-art Review, International Journal of Computer.
• [10] Nasr, N. and Elsayed, E.A., (1990). Job Shop Scheduling with Alternative Machines, International Journal of Production Research, Vol:28, No:9, 1595–1609. doi:10.1080/00207549008942818.
• [11] Khoshnevis, B. and Chen, Q.M., (1991). Integration of Process Planning and Scheduling Functions, Journal of Intelligent Manufacturing, Vol:2, No:3, pp:165–175.
• [12] Hutchison, J., Leong, K., Snyder, D., and Ward, P., (1991). Scheduling Approaches for Random Job Shop Flexible Manufacturing Systems, International Journal of Production Research, Vol:29, No:5, pp:1053–1067. doi:10.1080/00207549108930119.
• [13] Jiang, J., Hsiao, W., (1994). Mathematical Programming for the Scheduling Problem with Alternate Process Plans in FMS, Computers and Industrial Engineering, Vol:27, No:1–4, pp:15–18. doi:10.1016/0360-8352(94)90226-7.
• [14] Chen, Q. and Khoshnevis, B., (1993). Scheduling with Flexible Process Plans, Production Planning and Control, Vol:4, No:4, pp:333–343. doi:10.1080/09537289308919455.
• [15] Brandimarte, P., (1999). Exploiting Process Plan Flexibility in production Scheduling: A multi-objective approach, European Journal of Operational Research, Vol:114, No:1, pp:59–71. doi:10.1016/S0377-2217(98)00029-0.
• [16] Kim, K.H. and Egbelu, P.J., (1999). Scheduling in a Production Environment with Multiple Process Plans Per Job, International Journal of Production Research, Vol:37, No:12, pp:2725–2753. doi:10.1080/002075499190491.
• [17] Morad, N. and Zalzala, A., (1999). Genetic Algorithms in Integrated Process Planning and Scheduling, Journal of Intelligent Manufacturing, Vol:10, No:2, pp:169–179.
• [18] Leung, C.W., Wong, T.N., Mak, K.L.L., and Fung, R.Y.K., (2010). Integrated Process Planning and Scheduling by an Agent-based Ant Colony Optimization, Computers and Industrial Engineering, Vol:59, No:1, 166–180. doi:10.1016/j.cie.2009.09.003.
• [19] Ming, X.G. and Mak, K.L., (2000). A Hybrid Hopfield Network-Genetic Algorithm Approach to Optimal Process Plan Selection, International Journal of Production Research, Vol:38, No:8, pp:1823–1839. doi:10.1080/002075400188618.
• [20] Lee, H. and Kim, S.S., (2001). Integration of Process Planning and Scheduling Using Simulation Based Genetic Algorithms, International Journal of Advanced Manufacturing Technology, Vol:18, No:8, pp:586–590. doi:10.1007/s001700170035.
• [21] Kim, Y.K., Park, K., and Ko, J., (2003). A Symbiotic Evolutionary Algorithm for the Integration of Process Planning and Job Shop Scheduling, Computers & Operations Research, Vol:30, No:8, pp:1151–1171. doi:10.1016/S0305-0548(02)00063-1.
• [22] Kumar, M. and Rajotia, S., (2006). Integration of Process Planning and Scheduling in a Job Shop Environment, The International Journal of Advanced Manufacturing Technology, Vol:28, No:1–2, pp:109–116. doi:10.1007/s00170-004-2317-y.
• [23] Ueda, K., Fujii, N., and Inoue, R., (2007). An Emergent Synthesis Approach to Simultaneous Process Planning and Scheduling, CIRP Annals - Manufacturing Technology, Vol:56, No:1, pp:463–466. doi:10.1016/j.cirp.2007.05.111.
• [24] Moon, C., Lee, Y.H., Jeong, C.S., and Yun, Y., (2008). Integrated Process Planning and Scheduling in a Supply Chain, Computers & Industrial Engineering, Vol:54, No:4, pp:1048–1061. doi:10.1016/j.cie.2007.06.018.
• [25] Guo, Y.W., Li, W.D., Mileham, A.R., and Owen, G.W., (2009). Optimisation of Integrated Process Planning and Scheduling Using a Particle Swarm Optimisation Approach, International Journal of Production Research, Vol:47, No:14, pp:3775–3796. doi:10.1080/00207540701827905.
• [26] Gordon, V., Proth, J., and Chu, C., (2002). A Survey of the State-of-the-art of Common due Date Assignment and Scheduling Research, European Journal of Operational Research.
• [27] Panwalkar, S. and Smith, M., (1982). Common due date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem, Operations Research, Vol:30, ppp:391–399.
• [28] Xia, Y., Chen, B., and Yue, J., (2008). Job Sequencing and due date Assignment in a Single Machine Shop with Uncertain Processing Times, European Journal of Operational Research, Vol:184, No:1, pp:63–75. doi:10.1016/j.ejor.2006.10.058.
• [29] Gordon, V.S. and Strusevich, V.A., (2009). Single Machine Scheduling and due Date Assignment with Positionally Dependent Processing Times, European Journal of Operational Research, Vol:198, No:1, pp:57–62. doi:10.1016/j.ejor.2008.07.044.
• [30] Li, J., Yuan, X., Lee, E.S., and Xu, D., (2011). Setting due Dates to Minimize the Total Weighted Possibilistic Mean Value of the Weighted Earlinesstardiness Costs on a Single Machine, Computers and Mathematics with Applications, Vol:62, No:11, pp:4126–4139. doi:10.1016/j.camwa.2011.09.063.
• [31] Gordon, V. and Kubiak, W., (1998). Single Machine Scheduling with Release and due date Assignment to Minimize The Weighted Number of Late Jobs, Information Processing Letters, Vol:68, No:3, pp:153–159. doi:10.1016/S0020-0190(98)00153-7.
• [32] Biskup, D. and Jahnke, H., (2001). Common due Date Assignment for Scheduling on a Single Machine with Jointly Reducible Processing Times, International Journal of Production Economics, Vol:69, No:3, pp:317–322. doi:10.1016/S0925-5273(00)00040-2.
• [33] Ventura, J.A. and Radhakrishnan, S., (2003). Single Machine Scheduling with Symetric Earliness and Tardiness Penalties, European Journal of Operational Research, Vol:144, pp:598–612.
• [34] Ji, M., Ge, J., Chen, K., and Cheng, T.C.E., (2013). Single-Machine due-window Assignment and Scheduling with Resource Allocation, Aging Effect, and a Deteriorating Rate-Modifying Activity, Computers and Industrial Engineering, Vol:66, No:4, pp:952–961. doi:10.1016/j.cie.2013.08.020.
• [35] Wang, J.B., (2006). Single Machine Scheduling with Common due Date and Controllable Processing Times, Applied Mathematics and Computation, Vol:174, No:2, pp:1245–1254. doi:10.1016/j.amc.2005.05.046.
• [36] Lin, S.W., Chou, S.Y., and Chen, S.C., (2007). Meta-heuristic Approaches for Minimizing Total Earliness and Tardiness Penalties of Single-Machine Scheduling with a Common due Date, Journal of Heuristics, Vol:13, No:2, pp:151–165. doi:10.1007/s10732-006-9002-2.
• [37] Ying, K.C., (2008). Minimizing Earliness–Tardiness Penalties for Common due date Single-machine Scheduling Problems by a Recovering Beam Search Algorithm, Computers & Industrial Engineering, Vol:55, No:2, pp:494–502. doi:10.1016/j.cie.2008.01.008.
• [38] Nearchou, A.C., (2008). A Differential Evolution Approach for the Common due Date early/tardy Job Scheduling Problem, Computers and Operations Research, Vol:35, No:4, pp:1329–1343. doi:10.1016/j.cor.2006.08.013.
• [39] Adamopoulos, G.I. and Pappis, C.P., (1998). Scheduling under a Common due-data on Parallel Unrelated Machines, European Journal of Operational Research, Vol:105, No:3, pp:494–501. doi:10.1016/S0377-2217(97)00057-X.
• [40] Cheng, T.C.E. and Kovalyov, M.Y., (1996). Batch Scheduling and Common due-date Assignment on a Single Machine, Discrete Applied Mathematics, Vol:70, No:3, pp:231–245. doi:10.1016/0166-218X(96)80468-9.
• [41] Mosheiov, G., (2001). A Common due-date Assignment Problem on Parallel Identical Machines, Computers and Operations Research, Vol:28, No:8, pp:719–732. doi:10.1016/S0305-0548(99)00127-6.
• [42] Birman, M. and Mosheiov, G., (2004). A Note on a due-date Assignment on a Two-machine Flow-shop, Computers and Operations Research, Vol:31, No:3, pp:473–480. doi:10.1016/S0305-0548(02)00225-3.
• [43] Lauff, V. and Werner, F., (2004). Scheduling with Common due Date, Earliness and Tardiness Penalties for Multimachine Problems: A Survey, Mathematical and Computer Modelling, Vol:40, Nos. 5–6, pp:637–655. doi:10.1016/j.mcm.2003.05.019.
• [44] Allaoua, H. and Osmane, I., (2010). Variable Parameters Lengths Genetic Algorithm for Minimizing Earliness-Tardiness Penalties of Single Machine Scheduling with a Common due date, Electronic Notes in Discrete Mathematics, Vol:36, pp:471–478. doi:10.1016/j.endm.2010.05.060.
• [45] Zhang, R. nad Wu, C., (2012). A Hybrid Local Search Algorithm F-for Scheduling Real-World Job Shops with Batch-Wise Pending due Dates, Engineering Applications of Artificial Intelligence, Vol:25, No:2, pp:209–221. doi:10.1016/j.engappai.2011.04.014.
• [46] Yin, Y., Cheng, S.R., Cheng, T.C.E., Wu, C.C., and Wu, W.H., (2012). Two-agent Single-Machine Scheduling with Assignable due Dates, Applied Mathematics and Computation, Vol:219, No:4, pp:1674–1685. doi:10.1016/j.amc.2012.08.008.
• [47] Yin, Y., Cheng, T.C.E., Xu, D., and Wu, C.C., (2012). Common due Date Assignment and Scheduling with a Rate-modifying Activity to Minimize the due Date, Earliness, Tardiness, Holding, and Batch Delivery Cost, Computers and Industrial Engineering, Vol:63, No:1, pp:223–234. doi:10.1016/j.cie.2012.02.015.
• [48] Iranpoor, M., Fatemi Ghomi, S.M.T., and Zandieh, M., (2013). Due-date Assignment and Machine Scheduling in a Low Machine-rate Situation with Stochastic Processing Times, Computers and Operations Research, Vol:40, No:4, pp:1100–1108. doi:10.1016/j.cor.2012.11.013.
• [49] Yin, Y., Cheng, T.C.E., Cheng, S.R., and Wu, C.C., (2013). Single-machine Batch Delivery Scheduling with an Assignable Common due date and Controllable Processing Times, Computers and Industrial Engineering, Vol:65, No:4, pp:652–662. doi:10.1016/j.cie.2013.05.003.
• [50] Zhao, F., Zhu, A., Ren, Z., and Yang, Y., (2006). Integration of Process Planning and Production Scheduling Based on A Hybrid {PSO} and {SA} Algorithm, Proceedings of the 2006 {IEEE} International Conference on Mechatronics and Automation, IEEE, 2290–2295. doi:10.1109/ICMA.2006.257669.
• [51] Yang, S.J., Yang, D.L., and Cheng, T.C.E., (2010). Single-Machine due-window Assignment and Scheduling with Job-dependent Aging Effects and Deteriorating Maintenance, Computers and Operations Research, Vol:37, No:8, pp:1510–1514. doi:10.1016/j.cor.2009.11.007.
• [52] Huynh Tuong, N. and Soukhal, A., (2010). Due dates Assignment and JIT Scheduling with Equal-size Jobs, European Journal of Operational Research, Vol:205, No:2, pp:280–289. doi:10.1016/j.ejor.2010.01.016.
• [53] Li, J., Sun, K., Xu, D., and Li, H., (2010). Single Machine due Date Assignment Scheduling Problem with Customer Service Level in Fuzzy Environment, Applied Soft Computing Journal, Vol:10, No:3, pp:849–858. doi:10.1016/j.asoc.2009.10.002.
• [54] Shabtay, D., (2010). Scheduling and due date assignment to Minimize Earliness, Tardiness, Holding, due date Assignment and Batch Delivery Costs, International Journal of Production Economics, Vol:123, No:1, 235–242. doi:10.1016/j.ijpe.2009.08.012.
• [55] Vinod, V. and Sridharan, R., (2011). Simulation Modeling and Analysis of due-date Assignment Methods and Scheduling Decision Rules in a Dynamic Job Shop Production System, International Journal of Production Economics, Vol:129, No:1, pp:127–146. doi:10.1016/j.ijpe.2010.08.017.
• [56] Li, S., Ng, C.T., and Yuan, J., (2011). Group Scheduling and due Date Assignment on a Single Machine, International Journal of Production Economics, Vol:130, No:2, pp:230–235. doi:10.1016/j.ijpe.2010.12.023.
• [57] Li, S., Ng, C.T., and Yuan, J., (2011). Scheduling Deteriorating Jobs with CON/SLK due date Assignment on a Single Machine, International Journal of Production Economics, Vol:131, No:2, pp:747–751. doi:10.1016/j.ijpe.2011.02.029.