Solving Process Planning, Weighted Earliest Due Date Scheduling and Weighted Due Date Assignment Using Simulated Annealing and Evolutionary Strategies

Authors: Halil Ibrahim Demir, Abdullah Hulusi Kokcam, Fuat Simsir, Özer Uygun

Abstract:

Traditionally, three important manufacturing functions which are process planning, scheduling and due-date assignment are performed sequentially and separately. Although there are numerous works on the integration of process planning and scheduling and plenty of works focusing on scheduling with due date assignment, there are only a few works on integrated process planning, scheduling and due-date assignment. Although due-dates are determined without taking into account of weights of the customers in the literature, here weighted due-date assignment is employed to get better performance. Jobs are scheduled according to weighted earliest due date dispatching rule and due dates are determined according to some popular due date assignment methods by taking into account of the weights of each job. Simulated Annealing, Evolutionary Strategies, Random Search, hybrid of Random Search and Simulated Annealing, and hybrid of Random Search and Evolutionary Strategies, are applied as solution techniques. Three important manufacturing functions are integrated step-by-step and higher integration levels are found better. Search meta-heuristics are found to be very useful while improving performance measure.

Keywords: Evolutionary strategies, hybrid searches, process planning, simulated annealing, weighted due-date assignment, weighted scheduling.

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

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] 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.
[4] J. M. Usher, “Evaluating the impact of alternative plans on manufacturing performance,” Comput. Ind. Eng., vol. 45, no. 4, pp. 585–596, Dec. 2003.
[5] K. Bhaskaran, “Process plan selection,” Int. J. Prod. Res., vol. 28, no. 8, pp. 1527–1539, 1990.
[6] 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.
[7] H. Lee and S.-S. Kim, “Integration of Process Planning and Scheduling Using Simulation Based Genetic Algorithms,” Int. J. Adv. Manuf. Technol., vol. 18, no. 8, pp. 586–590, Oct. 2001.
[8] C. Moon, J. Kim, and S. Hur, “Integrated process planning and scheduling with minimizing total tardiness in multi-plants supply chain,” Comput. Ind. Eng., vol. 43, no. 1–2, pp. 331–349, Jul. 2002.
[9] 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.
[10] I. Drstvenšek and J. Balič, “Responding ability in dynamic production circumstances,” J. Mater. Process. Technol., vol. 133, no. 1, pp. 71–78, 2003.
[11] 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.
[12] X. Li, C. Zhang, L. Gao, W. Li, and X. Shao, “An agent-based approach for integrated process planning and scheduling,” Expert Syst. Appl., vol. 37, no. 2, pp. 1256–1264, Mar. 2010.
[13] A. Seker, S. Erol, and R. Botsali, “A neuro-fuzzy model for a new hybrid integrated Process Planning and Scheduling system,” Expert Syst. Appl., vol. 40, no. 13, pp. 5341–5351, Oct. 2013.
[14] L. Zhang and T. N. Wong, “An object-coding genetic algorithm for integrated process planning and scheduling,” Eur. J. Oper. Res., vol. 244, no. 2, pp. 434–444, Jul. 2015.
[15] R. Meenakshi Sundaram and S. Fu, “Process planning and scheduling — A method of integration for productivity improvement,” Comput. Ind. Eng., vol. 15, no. 1–4, pp. 296–301, 1988.
[16] N. Nasr and E. A. Elsayed, “Job shop scheduling with alternative machines,” Int. J. Prod. Res., vol. 28, no. 9, pp. 1595–1609, Sep. 1990.
[17] 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.
[18] J. Hutchison, K. Leong, D. Synder, 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.
[19] J. M. Usher and K. J. Fernandes, “Dynamic process planning—the static phase,” J. Mater. Process. Technol., vol. 61, no. 1–2, pp. 53–58, 1996.
[20] 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.
[21] 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.
[22] A. Weintraub, D. Cormier, T. Hodgson, R. King, J. WIlson, and A. Zozom, “Scheduling with alternatives: a link between process planning and scheduling,” IIE Trans., vol. 31, no. 11, pp. 1093–1102, Nov. 1999.
[23] C. Saygin, F. F. Chen, and J. Singh, “Real-time manipulation of alternative routeings in flexible manufacturing systems: a simulation study,” Int. J. Adv. Manuf. Technol., vol. 18, no. 10, pp. 755–763, 2001.
[24] C. S. Thomalla, “Job shop scheduling with alternative process plans,” Int. J. Prod. Econ., vol. 74, no. 1–3, pp. 125–134, Dec. 2001.
[25] J. Zhang, L. Gao, F. T. S. Chan, and P. Li, “A holonic architecture of the concurrent integrated process planning system,” J. Mater. Process. Technol., vol. 139, no. 1–3, pp. 267–272, Aug. 2003.
[26] C. Moon and Y. Seo, “Evolutionary algorithm for advanced process planning and scheduling in a multi-plant,” Comput. Ind. Eng., vol. 48, no. 2, pp. 311–325, Mar. 2005.
[27] X. Shao, X. Li, L. Gao, and C. Zhang, “Integration of process planning and scheduling—A modified genetic algorithm-based approach,” Comput. Oper. Res., vol. 36, no. 6, pp. 2082–2096, Jun. 2009.
[28] C. Özgüven, L. Özbakır, and Y. Yavuz, “Mathematical models for job-shop scheduling problems with routing and process plan flexibility,” Appl. Math. Model., vol. 34, no. 6, pp. 1539–1548, Jun. 2010.
[29] X. Li, X. Shao, L. Gao, and W. Qian, “An effective hybrid algorithm for integrated process planning and scheduling,” Int. J. Prod. Econ., vol. 126, no. 2, pp. 289–298, Aug. 2010.
[30] 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.
[31] X. Li, L. Gao, and W. Li, “Application of game theory based hybrid algorithm for multi-objective integrated process planning and scheduling,” Expert Syst. Appl., vol. 39, no. 1, pp. 288–297, Jan. 2012.
[32] C. Dewu, S. Li, and T. Guochun, “Single machine scheduling with common due date assignment in a group technology environment,” Math. Comput. Model., vol. 25, no. 3, pp. 81–90, 1997.
[33] M. Y. Kovalyov, “Batch scheduling and common due date assignment problem: an NP-hard case,” Discrete Appl. Math., vol. 80, no. 2–3, pp. 251–254, 1997.
[34] 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.
[35] 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.
[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.
[37] 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.
[38] H. Allaoua and I. Osmane, “Variable Parameters Lengths Genetic Algorithm for Minimizing Earliness-Tardiness Penalties of Single Machine Scheduling With a Common Due Date,” Electron. Notes Discrete Math., vol. 36, pp. 471–478, Aug. 2010.
[39] N. H. Tuong and A. Soukhal, “Due dates assignment and JIT scheduling with equal-size jobs,” Eur. J. Oper. Res., vol. 205, no. 2, pp. 280–289, Sep. 2010.
[40] Y. Yin, T. C. E. Cheng, D. Xu, and C.-C. Wu, “Common due date assignment and scheduling with a rate-modifying activity to minimize the due date, earliness, tardiness, holding, and batch delivery cost,” Comput. Ind. Eng., vol. 63, no. 1, pp. 223–234, Aug. 2012.
[41] H. Luss and M. B. Rosenwein, “A due date assignment algorithm for multiproduct manufacturing facilities,” Eur. J. Oper. Res., vol. 65, no. 2, pp. 187–198, 1993.
[42] 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.
[43] 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.
[44] V. S. Gordon and V. A. Strusevich, “Earliness penalties on a single machine subject to precedence constraints: SLK due date assignment,” Comput. Oper. Res., vol. 26, no. 2, pp. 157–177, 1999.
[45] A. Baykasoğlu, M. Göçken, and Z. D. Unutmaz, “New approaches to due date assignment in job shops,” Eur. J. Oper. Res., vol. 187, no. 1, pp. 31–45, May 2008.
[46] 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.
[47] S. Li, C. T. Ng, and J. Yuan, “Scheduling deteriorating jobs with CON/SLK due date assignment on a single machine,” Int. J. Prod. Econ., vol. 131, no. 2, pp. 747–751, Jun. 2011.
[48] X. Cai, V. Y. S. Lum, and J. M. T. Chan, “Scheduling about a common due date with kob-dependent asymmetric earliness and tardiness penalties,” Eur. J. Oper. Res., vol. 98, no. 1, pp. 154–168, 1997.
[49] M. Birman and G. Mosheiov, “A note on a due-date assignment on a two-machine flow-shop,” Comput. Oper. Res., vol. 31, no. 3, pp. 473–480, Mar. 2004.
[50] L. Min and W. Cheng, “Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems,” Robot. Comput.-Integr. Manuf., vol. 22, no. 4, pp. 279–287, Aug. 2006.
[51] T. Yang, Z. He, and K. K. Cho, “An effective heuristic method for generalized job shop scheduling with due dates,” Comput. Ind. Eng., vol. 26, no. 4, pp. 647–660, 1994.
[52] V. Vinod and R. Sridharan, “Simulation modeling and analysis of due-date assignment methods and scheduling decision rules in a dynamic job shop production system,” Int. J. Prod. Econ., vol. 129, no. 1, pp. 127–146, Jan. 2011.
[53] S. R. Lawrence, “Negotiating due-dates between customers and producers,” Int. J. Prod. Econ., vol. 37, no. 1, pp. 127–138, 1994.
[54] J. N. Gupta, K. Krüger, V. Lauff, F. Werner, and Y. N. Sotskov, “Heuristics for hybrid flow shops with controllable processing times and assignable due dates,” Comput. Oper. Res., vol. 29, no. 10, pp. 1417–1439, 2002.
[55] H. I. Demir, T. Cakar, M. Ipek, O. Uygun, and M. Sari, “Process Planning and Due-date Assignment with ATC Dispatching where Earliness, Tardiness and Due-dates are Punished,” J. Ind. Intell. Inf. Vol, vol. 3, no. 3, 2015.
[56] H. I. Demir and H. Taskin, “Integrated Process Planning, Scheduling and Due-Date Assignment,” PhD Thesis, Sakarya University, 2005.
[57] E. Ceven and H. I. Demir, “Benefits of Integrating Due-Date Assignment with Process Planning and Scheduling,” Master of Science Thesis, Sakarya University, 2007.
[58] 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, vol. 3, no. 3, 2015.
[59] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, and others, “Optimization by simmulated annealing,” science, vol. 220, no. 4598, pp. 671–680, 1983.
[60] I. Rechenberg, Cybernetic solution path of an experimental problem, vol. 1122. Ministry of Aviation, Royal Aircraft Establishment, Library Translation, 1965.
[61] H.-P. Schwefel, Numerical optimization of computer models. John Wiley & Sons, Inc., 1981.