Solving Process Planning and Scheduling with Number of Operation Plus Processing Time Due-Date Assignment Concurrently Using a Genetic Search

Authors: Halil Ibrahim Demir, Alper Goksu, Onur Canpolat, Caner Erden, Melek Nur

Abstract:

Traditionally process planning, scheduling and due date assignment are performed sequentially and separately. High interrelation between these functions makes integration very useful. Although there are numerous works on integrated process planning and scheduling and many works on scheduling with due date assignment, there are only a few works on the integration of these three functions. Here we tested the different integration levels of these three functions and found a fully integrated version as the best. We applied genetic search and random search and genetic search was found better compared to the random search. We penalized all earliness, tardiness and due date related costs. Since all these three terms are all undesired, it is better to penalize all of them.

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

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

References:

[1] H.-C. Zhang and S. Mallur, “An integrated model of process planning and production scheduling,” Int. J. Comput. Integr. Manuf., vol. 7, no. 6, pp. 356–364, Nov. 1994.
[2] V. Gordon, J.-M. Proth, and C. Chu, “A survey of the state-of-the-art of common due date assignment and scheduling research,” Eur. J. Oper. Res., vol. 139, no. 1, pp. 1–25, May 2002.
[3] Demir, H.I. and Taskin, H., “Integrated Process Planning, Scheduling and Due-Date Assignment,” PhD Thesis, Sakarya University, 2005.
[4] Ceven, E. and Demir, H.I., “Benefits of Integrating Due-Date Assignment with Process Planning and Scheduling,” Master of Science Thesis, Sakarya University, 2007.
[5] H. I. Demir, O. Uygun, I. Cil, M. Ipek, and M. Sari, “Process Planning and Scheduling with SLK Due-Date Assignment where Earliness, Tardiness and Due-Dates are Punished,” J. Ind. Intell. Inf., vol. 3, no. 3, pp. 173–180, Sep. 2015.
[6] W. Tan and B. Khoshnevis, “Integration of process planning and scheduling— a review,” J. Intell. Manuf., vol. 11, no. 1, pp. 51–63, Feb. 2000.
[7] X. Li, L. Gao, C. Zhang, and X. Shao, “A review on Integrated Process Planning and Scheduling,” Int. J. Manuf. Res., vol. 5, no. 2, pp. 161–180, Jan. 2010.
[8] R. K. Phanden, A. Jain, and R. Verma, “Integration of process planning and scheduling: a state-of-the-art review,” Int. J. Comput. Integr. Manuf., vol. 24, no. 6, pp. 517–534, Jun. 2011.
[9] Demir, H.I. and Wu, S.D., “A Comparison of several Optimization Schemes for The Integration of Processing Planning and Production Scheduling Problems,” Master of Science Thesis, Lehigh University., 1996.
[10] B. Khoshnevis and Q. M. Chen, “Integration of process planning and scheduling functions,” J. Intell. Manuf., vol. 2, no. 3, pp. 165–175, Jun. 1991.
[11] J. Hutchison, K. Leong, D. Snyder, and P. Ward, “Scheduling approaches for random job shop flexible manufacturing systems,” Int. J. Prod. Res., vol. 29, no. 5, pp. 1053–1067, May 1991.
[12] Q. M. Chen and B. Khoshnevis, “Scheduling with flexible process plans,” Prod. Plan. Control, vol. 4, no. 4, pp. 333–343, Jan. 1993.
[13] P. Brandimarte, “Exploiting process plan flexibility in production scheduling: A multi-objective approach,” Eur. J. Oper. Res., vol. 114, no. 1, pp. 59–71, Apr. 1999.
[14] K.-H. Kim and P. J. Egbelu, “Scheduling in a production environment with multiple process plans per job,” Int. J. Prod. Res., vol. 37, no. 12, pp. 2725–2753, Aug. 1999.
[15] N. Morad and A. Zalzala, “Genetic algorithms in integrated process planning and scheduling,” J. Intell. Manuf., vol. 10, no. 2, pp. 169–179, Apr. 1999.
[16] Y. K. Kim, K. Park, and J. Ko, “A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling,” Comput. Oper. Res., vol. 30, no. 8, pp. 1151–1171, Jul. 2003.
[17] J. M. Usher, “Evaluating the impact of alternative plans on manufacturing performance,” Comput. Ind. Eng., vol. 45, no. 4, pp. 585–596, Dec. 2003.
[18] M. K. Lim and D. Z. Zhang, “An integrated agent-based approach for responsive control of manufacturing resources,” Comput. Ind. Eng., vol. 46, no. 2, pp. 221–232, Apr. 2004.
[19] W. Tan and B. Khoshnevis, “A linearized polynomial mixed integer programming model for the integration of process planning and scheduling,” J. Intell. Manuf., vol. 15, no. 5, pp. 593–605, Oct. 2004.
[20] M. Kumar and S. Rajotia, “Integration of process planning and scheduling in a job shop environment,” Int. J. Adv. Manuf. Technol., vol. 28, no. 1–2, pp. 109–116, Mar. 2005.
[21] C. Moon, Y. H. Lee, C. S. Jeong, and Y. Yun, “Integrated process planning and scheduling in a supply chain,” Comput. Ind. Eng., vol. 54, no. 4, pp. 1048–1061, May 2008.
[22] C. W. Leung, T. N. Wong, K. L. Mak, and R. Y. K. Fung, “Integrated process planning and scheduling by an agent-based ant colony optimization,” Comput. Ind. Eng., vol. 59, no. 1, pp. 166–180, Aug. 2010.
[23] S. S. Panwalkar, M. L. Smith, and A. Seidmann, “Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem,” Oper. Res., vol. 30, no. 2, pp. 391–399, Apr. 1982.
[24] V. Gordon and W. Kubiak, “Single machine scheduling with release and due date assignment to minimize the weighted number of late jobs,” Inf. Process. Lett., vol. 68, no. 3, pp. 153–159, Nov. 1998.
[25] D. Biskup and H. Jahnke, “Common due date assignment for scheduling on a single machine with jointly reducible processing times,” Int. J. Prod. Econ., vol. 69, no. 3, pp. 317–322, Feb. 2001.
[26] T. C. E. Cheng, Z.-L. Chen, and N. V. Shakhlevich, “Common due date assignment and scheduling with ready times,” Comput. Oper. Res., vol. 29, no. 14, pp. 1957–1967, Dec. 2002.
[27] J. A. Ventura and S. Radhakrishnan, “Single machine scheduling with symmetric earliness and tardiness penalties,” Eur. J. Oper. Res., vol. 144, no. 3, pp. 598–612, Feb. 2003.
[28] T. C. E. Cheng, L. Y. Kang, and C. T. Ng, “Single machine due-date scheduling of jobs with decreasing start-time dependent processing times,” Int. Trans. Oper. Res., vol. 12, no. 3, pp. 355–366, May 2005.
[29] J.-B. Wang, “Single machine scheduling with common due date and controllable processing times,” Appl. Math. Comput., vol. 174, no. 2, pp. 1245–1254, Mar. 2006.
[30] S.-W. Lin, S.-Y. Chou, and S.-C. Chen, “Meta-heuristic approaches for minimizing total earliness and tardiness penalties of single-machine scheduling with a common due date,” J. Heuristics, vol. 13, no. 2, pp. 151–165, Dec. 2006.
[31] Y. Xia, B. Chen, and J. Yue, “Job sequencing and due date assignment in a single machine shop with uncertain processing times,” Eur. J. Oper. Res., vol. 184, no. 1, pp. 63–75, Jan. 2008.
[32] V. S. Gordon and V. A. Strusevich, “Single machine scheduling and due date assignment with positionally dependent processing times,” Eur. J. Oper. Res., vol. 198, no. 1, pp. 57–62, Oct. 2009.
[33] J. Li, X. Yuan, E. S. Lee, and D. Xu, “Setting due dates to minimize the total weighted possibilistic mean value of the weighted earliness–tardiness costs on a single machine,” Comput. Math. Appl., vol. 62, no. 11, pp. 4126–4139, Dec. 2011.
[34] G. I. Adamopoulos and C. P. Pappis, “Scheduling under a common due-data on parallel unrelated machines,” Eur. J. Oper. Res., vol. 105, no. 3, pp. 494–501, Mar. 1998.
[35] T. C. E. Cheng and M. Y. Kovalyov, “Complexity of parallel machine scheduling with processing-plus-wait due dates to minimize maximum absolute lateness,” Eur. J. Oper. Res., vol. 114, no. 2, pp. 403–410, Apr. 1999.
[36] V. Lauff and F. Werner, “Scheduling with common due date, earliness and tardiness penalties for multimachine problems: A survey,” Math. Comput. Model., vol. 40, no. 5–6, pp. 637–655, Sep. 2004.