Integrating Process Planning, WMS Dispatching, and WPPW Weighted Due Date Assignment Using a Genetic Algorithm

Authors: Halil Ibrahim Demir, Tarık Cakar, Ibrahim Cil, Muharrem Dugenci, Caner Erden

Abstract:

Conventionally, process planning, scheduling, and due-date assignment functions are performed separately and sequentially. The interdependence of these functions requires integration. Although integrated process planning and scheduling, and scheduling with due date assignment problems are popular research topics, only a few works address the integration of these three functions. This work focuses on the integration of process planning, WMS scheduling, and WPPW due date assignment. Another novelty of this work is the use of a weighted due date assignment. In the literature, due dates are generally assigned without considering the importance of customers. However, in this study, more important customers get closer due dates. Typically, only tardiness is punished, but the JIT philosophy punishes both earliness and tardiness. In this study, all weighted earliness, tardiness, and due date related costs are penalized. As no customer desires distant due dates, such distant due dates should be penalized. In this study, various levels of integration of these three functions are tested and genetic search and random search are compared both with each other and with ordinary solutions. Higher integration levels are superior, while search is always useful. Genetic searches outperformed random searches.

Keywords: Process planning, weighted scheduling, weighted due-date assignment, genetic algorithm, random search.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1126013

References:

[1] H. C. Zhang, S. Mallur, “An Integrated Model of Process Planning and Production Scheduling,” International Journal of Computer Integrated Manufacturing, vol. 7, no. 6, pp. 356-364, 1994.
[2] V. Gordon, J.M. Proth, C. Chu, “A survey of the state-of-the-art of common due date assignment and scheduling research,” European Journal of Operational Research, vol. 139, pp. 1-25, 2002.
[3] W. Tan, B. Khoshnevis, “Integration of process planning and scheduling – a review,” Journal of Intelligent Manufacturing, 11, no. 1, 51-63, 2000.
[4] X. Li, L. Gao, C. Zhang and X. Shao, “A review on integrated process planning and scheduling,” International Journal of Manufacturing Research, vol. 5, no. 2, pp. 161-180, 2010.
[5] R. K. Phanden, A. Jaina, R. Verma, “Integration of process planning and scheduling: a state-of-the-art review,” International Journal of Computer Integrated Manufacturing, vol. 24, no. 6, pp. 517-534, 2011.
[6] N. Nasr, E. A. Elsayed, “Job shop scheduling with alternative machines,” International Journal of Production Research, vol. 28, no. 9, pp. 1595-1609, 1990.
[7] B. Khoshnevis, Q. M. Chen, “Integration of Process Planning and Scheduling Functions,” Journal of Intelligent Manufacturing, vol. 2, no. 3, pp. 165-175, 1991.
[8] J. Hutchinson, K. Leong, D. Snyder, P. Ward, “Scheduling Approaches for Random Job Shop Flexible Manufacturing Systems,” International Journal of Production Research, vol. 29, no. 5, pp. 1053-1067, 1991.
[9] J. Jiang, M. Y. Chen, “The Influence of Alternative Process Planning in Job Shop Scheduling,” Computers and Industrial Engineering, vol. 25, no. 1-4, pp. 263-267, 1993.
[10] Q. Chen, B. Khoshnevis, “Scheduling with Flexible Process Plans,” Production Planning & Control, vol. 4, no. 4, pp. 333- 343, 1993.
[11] P. Brandimart, “Exploiting process plan flexibility in production scheduling: A multi-objective approach,” European Journal of Operational Research, vol. 114, no. 1, pp. 59-71, 1999.
[12] K. H. Kim, P. J. Egbelu, “Scheduling in a production environment with multiple process plans per job,” International Journal of Production Research, vol. 37, no. 12, pp. 2725-2753, 1999.
[13] N. Morad, A. Zalzala, “Genetic algorithms in integrated process planning and scheduling,” Journal of Intelligent Manufacturing, vol. 10, no. 2, pp. 169-179, 1999.
[14] X. G. Ming, K. L. Mak, “A hybrid Hopfield-genetic algorithm approach to optimal process plan selection,” International Journal of Production Research, vol. 38, no. 8, pp. 1823-1839, 2000.
[15] H. Lee, S. S. Kim, “Integration of process planning and scheduling using simulation based genetic algorithms,” International Journal of Advanced Manufacturing Technology, vol. 18, no. 8, pp. 586-590, 2001.
[16] Y. K. Kim, K. Park, J. Ko, “A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling,” Computers and Operations Research, vol. 30, no. 8, pp. 1151-1171, 2003.
[17] M. Kumar, S. Rajotia, “Integration of scheduling with computer aided process planning,” Journal of Materials Processing Technology, vol. 138, no. 1-3, pp. 297-300, 2003.
[18] J. M. Usher, “Evaluating the impact of alternative plans on manufacturing performance,” Computers and Industrial Engineering, vol. 45, no. 4, pp. 585-596, 2003.
[19] M. K. Lim, D.Z. Zhang, “An integrated agent-based approach for responsive control of manufacturing resources,” Computers and Industrial Engineering, vol. 46, no. 2, pp. 221-232, 2004.
[20] W. Tan, B. Khoshnevis, “A linearized polynomial mixed integer programming model for the integration of process planning and scheduling,” Journal of Intelligent Manufacturing, vol. 15, no. 5, pp. 593-605, 2004.
[21] M. Kumar, S. Rajotia, “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, 2006.
[22] K. Ueda, N. Fujii, R. Inoue, “An emergent synthesis approach to simultaneous process planning and scheduling,” CIRP Annals- Manufacturing Technology, vol. 56, no. 1, pp. 463-466, 2007.
[23] C. Moon, Y. H. Lee, C. S. Jeong, Y. Yun, “Integrated process planning and scheduling in a supply chain,” Computers and Industrial Engineering, vol. 54, no. 4, pp. 1048-1061, 2008.
[24] Y. W. Guo, W. D. Li, A. R. Mileham, G. W. Owen, “Optimization of integrated process planning and scheduling using a particle swarm optimization approach,” International Journal of Production Research, vol. 47, no. 4, pp. 3775-3796, 2009.
[25] C. W. Leung, T. N. Wong, K. L. Mak, R. Y. K. Fung, “Integrated process planning and scheduling by an agent-based ant colony optimization,” Computers and Industrial Engineering, 59, no. 1, pp. 166-180, 2010.
[26] H.I. Demir, T. Cakar, M. Ipek, O. Uygun, M. Sari, “Process planning and Due date assignment with ATC Dispatching where Earliness, Tardiness and Due dates are punished,” Journal of Industrial and Intelligent Information, vol. 3, no. 3, pp. 197–204, 2015.
[27] S.S. Panwalker, M.L. Smith, A. Seidmann, “Common due date assignment to minimize total penalty for the one machine scheduling problem,” Operations Research, vol. 30, pp. 391-399, 1982.
[28] V. Gordon, W. Kubiak, “Single machine scheduling with release and due date assignment to minimize the weighted number of late jobs,” Information Processing Letters, vol. 68, pp. 153-159, 1998.
[29] D. Biskup, H. Jahnke, “Common due date assignment for scheduling on a single machine with jointly reducible processing times,” International Journal of Production Economics, vol. 69, pp. 317-322, 2001.
[30] T.C.E. Cheng, Z. L. Chen, N.V. Shakhlevich, “Common due date assignment and scheduling with ready times,” Computers and Operations Research, vol. 29, pp. 1957-1967, 2002.
[31] J.A. Ventura, S. Radhakrishnan, “Single machine scheduling with symmetric earliness and tardiness,” European Journal of Operational Research, vol. 144, pp. 598-612, 2003.
[32] T. C. E. Cheng, L. Y. Kang, C. T. Ng, “Single machine due-date scheduling of jobs with decreasing start-time dependent processing times,” International Transactions In Operational Research, vol. 12, no. 3, pp. 355-366, May 2005.
[33] J. B. Wang, “Single machine scheduling with common due date and controllable processing times,” Applied Mathematics and Computation, vol. 174, no. 2, pp. 1245-1254, 2006.
[34] S.W. Lin, S.Y. Chou, S.C. Chen, “Meta-heuristic approaches for minimizing total earliness and tardiness penalties of single-machine scheduling with a common due date,” Journal of Heuristics, vol. 13, pp. 151-165, 2007.
[35] K.C. Ying, “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, 2008.
[36] A.C. Nearchou, “A differential evolution approach for the common due date early/tardy job scheduling problem,” Computers & Operations Research, vol. 35, pp. 1329-1343, 2008.
[37] Y. Xia, B. Chen, J. Yue, “Job sequencing and due date assignment in a single machine shop with uncertain processing times,” European Journal of Operational Research, vol. 184, pp. 63-75, 2008.
[38] V. S. Gordon, V. A. Strusevich, “Single machine scheduling and due date assignment with positionally dependent processing times,” European Journal of Operational Research, vol. 198, no. 1, pp. 57-62, October 2009.
[39] J. Li, X. Yuan, E.S. Lee, D. Xu, “Setting due dates to minimize the total weighted possibilistic mean value of the weighted earliness–tardiness costs on a single machine,” Computers & Mathematics with Applications, vol. 62, no. 11, pp. 4126-4139, 2011.
[40] G.I. Adamopoulos, C.P. Pappis, “Scheduling under a common due-date on parallel unrelated machines,” European Journal of Operational Research, vol. 105, pp. 494-501, 1998.
[41] T.C.E. Cheng, M.Y. Kovalyov, “Complexity of parallel machine scheduling with processing-plus-wait due dates to minimize maximum absolute lateness,” European Journal of Operational Research, vol. 114, pp. 403-410, 1999.
[42] G. Mosheiov, G, “A common due-date assignment problem on parallel identical machines,” Computers and Operations Research, vol. 28, pp. 719-732, 2001.
[43] M. Birman, G. Mosheiov, “A note on a due-date assignment on a two-machine flow-shop,” Computers and Operations Research, vol. 31, pp. 473-480, 2004.
[44] V. Lauff, F. Werner, “Scheduling with common due date, earliness and tardiness penalties for multimachine problems: A survey,” Mathematical and Computer Modelling, vol. 40, pp. 637-655, 2004.
[45] H. Allaoua, I. Osmane, “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, no. 1, pp. 471-478, 2010.
[46] S. Yang, D.L. Yang, T.C.E. Cheng, “Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance,” Computers & Operations Research, vol. 37, no. 8, pp. 1510-1514, 2010.
[47] N. H. Tuong and A. Soukhal, “Due dates assignment and JIT scheduling with equal-size jobs,” European Journal of Operational Research, vol. 205, no. 2, pp. 280-289, September 2010.
[48] J. Li, K. Sun, D. Xu, H. Li, “Single machine due date assignment scheduling problem with customer service level in fuzzy environment,” Applied Soft Computing, vol. 10, no. 3, pp. 849-858, 2010.
[49] D. Shabtay, “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, pp. 235-242, 2010.
[50] S. Li, C.T. Ng, J. Yuan, “Group scheduling and due date assignment on a single machine,” International Journal of Production Economics, vol. 130, no. 2, pp. 230-235, 2011.
[51] V. Vinod, R. Sridharan, “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, 2011.
[52] S. Li, C.T. Ng, J. Yuan, “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, 2011.
[53] R. Zhang, C. Wu, “A hybrid local search algorithm for scheduling real-world job shops with batch-wise pending due dates,” Engineering Applications of Artificial Intelligence, vol. 25, no. 2, pp. 209-221, 2012.
[54] Y. Yin, S.R. Cheng, T.C.E. Cheng, C.C. Wu, W.H. Wu, “Two-agent single-machine scheduling with assignable due dates,” Applied Mathematics and Computation, vol. 219, no. 4, pp. 1674-1685, 2012.
[55] Y. Yin, T.C.E. Cheng, C.C. Wu, W.H. Wu, “Common due date assignment and scheduling with a rate-modifying activity to minimize the due date, earliness, tardiness, holding, and batch delivery cost,” Computers & Industrial Engineering, vol. 63, no. 1, pp. 223-234, 2012.
[56] M. Iranpoor, S.M.T. Fatemi Ghomi, M. Zandieh, “Due-date assignment and machine scheduling in a low machine-rate situation with stochastic processing times,” Computers & Operations Research, vol. 40, no. 4, pp. 1100-1108, 2013.
[57] Y. Yin, S.R. Cheng, T.C.E. Cheng, C.C. Wu, W.H. Wu, “Single-machine batch delivery scheduling with an assignable common due date and controllable processing times,” Computers & Industrial Engineering, vol. 65, no. 4, pp. 652-662, 2013.
[58] H.I. Demir, H. Taskin, Integrated Process Planning, Scheduling and Due-Date Assignment, PhD Thesis, Sakarya University, 2005.
[59] E. Ceven, H.I. Demir, Benefits of Integrating Due-Date Assignment with Process Planning and Scheduling, Master of Science Thesis, Sakarya University, 2007.
[60] H.I. Demir, O. Uygun, I. Cil, M. Ipek, M. Sari, “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, pp. 173–180, 2015.