Onur CANPOLAT, Halil İbrahim DEMİR

Integrated process planning, WSPT scheduling and WSLK due-date assignment using genetic algorithms and evolutionary strategies

Process planning, scheduling and due-date assignment are three importantmanufacturing functions in our life. They all try to get local optima and there canbe an enormous loss in overall performance value if they are handled separately.That is why they should be handled concurrently. Although integrated processplanning and scheduling with due date assignment problem is not addressed muchin the literature, there are numerous works on integrated process planning andscheduling and many works on scheduling with due date assignment. Most of theworks in the literature assign common due date for the jobs waiting and due datesare determined without taking into account of the weights of the customers. Hereprocess planning function is integrated with weighted shortest processing times(WSPT) scheduling and weighted slack (WSLK) due date assignment. In thisstudy unique due dates are given to each customer and important customers getcloser due dates. Integration of these three functions is tested for different levelsof integration with genetic algorithms, evolutionary strategies, hybrid geneticalgorithms, hybrid evolutionary strategies and random search techniques. Bestcombinations are found as full integration with genetic search and hybrid geneticsearch. Integration of these three functions provided substantial improvements inglobal performance.

PDF

___

Zhang, H.C., & Mallur, S. (1994). An integrated model of process planning and production scheduling. International Journal of Computer Integrated Manufacturing, 7, 356–364.
Pinedo, M. and Chao, X. (1999). Operations scheduling with applications in manufacturing and services. McGraw-Hill Companies.
Gordon, V., Proth, J.M., & Chu, C. (2002). A survey of the state-of-the-art of common due date assignment and scheduling research. European Journal of Operational Research, 139, 1–25.
Demir, H.I. and Taskin, H. (2005). Integrated Process Planning, Scheduling and Due-Date Assignment. PhD Thesis.
Ceven, E. and Demir, H.I. (2007). Benefits of Integrating Due-Date Assignment with Process Planning and Scheduling. Master of Science Thesis.
Demir, H.I., Cakar, T., Ipek, M., Uygun, O., & Sari, M. (2015). Process Planning and Due-date Assignment with ATC Dispatching where Earliness, Tardiness and Due-dates are Punished. Journal of Industrial and Intelligent Information, 3, 197–204.
Demir, H.I., Uygun, O., Cil, I., Ipek, M., & 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, 3, 173–180.
Zhu, C. (2012). Applying Genetic Local Search Algorithm to Solve the Job-Shop Scheduling Problem. International Journal of Industrial Engineering: Theory, Applications and Practice, 19.
Wang, W., & Li, T. (2011). Improved cultural algorithms for job shop scheduling problem. International Journal of Industrial Engineering: Theory, Applications and Practice, 18.
Nasr, N., & Elsayed, E. (1990). A. Job shop scheduling with alternative machines. International Journal of Production Research, 28, 1595–1609.
Hutchison, J., Leong, K., Snyder, D., & Ward, P. (1991). Scheduling approaches for random job shop flexible manufacturing systems. International Journal of Production Research, 29, 1053–1067.
Chen, Q.M., & Khoshnevis, B. (1993). Scheduling with flexible process plans. Production Planning & Control, 4, 333–343.
Brandimarte, P. (1999). Exploiting process plan flexibility in production scheduling: A multiobjective approach. European Journal of Operational Research, 114, 59–71.
Morad, N., & Zalzala, A. (1999). Genetic algorithms in integrated process planning and scheduling. Journal of Intelligent Manufacturing, 10, 169–179.
Ming, X.G., & Mak, K.L. (2000). A hybrid Hopfield network-genetic algorithm approach to optimal process plan selection. International Journal of Production Research, 38, 1823–1839.
Tan, W., & Khoshnevis, B. (2000). Integration of process planning and scheduling - a review. Journal of Intelligent Manufacturing, 11, 51–63.
Kim, Y.K., Park, K., & Ko, J. (2003). A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling. Computers & Operations Research, 30, 1151–1171.
Kumar, M., & Rajotia, S. (2003). Integration of scheduling with computer aided process planning. Journal of Materials Processing Technology, 138, 297–300.
Lim, M.K., & Zhang, D.Z. (2004). An integrated agent-based approach for responsive control of manufacturing resources. Computers & Industrial Engineering, 46, 221–232.
Tan, W., & Khoshnevis, B. (2004). A linearized polynomial mixed integer programming model for the integration of process planning and scheduling. Journal of Intelligent Manufacturing, 15, 593–605.
Kumar, M., & Rajotia, S. (2005). Integration of process planning and scheduling in a job shop environment. The International Journal of Advanced Manufacturing Technology, 28, 109–116.
Moon, C., Lee, Y.H., Jeong, C.S., & Yun, Y. (2008). Integrated process planning and scheduling in a supply chain. Computers & Industrial Engineering, 54, 1048–1061.
Guo, Y.W., Li, W.D., Mileham, A.R., & Owen, G. W. (2009). Applications of particle swarm optimization in integrated process planning and scheduling. Robotics and Computer-Integrated Manufacturing, 25, 280–288.
Leung, C.W., Wong, T.N., Mak, K.L., & Fung, R.Y.K. (2010). Integrated process planning and scheduling by an agent-based ant colony optimization. Computers & Industrial Engineering, 59, 166–180.
Phanden, R.K., Jain, A., & Verma, R. (2011). Integration of process planning and scheduling: a state of the art review. International Journal of Computer Integrated Manufacturing, 24, 517–534.
Petrović, M., Vuković, N., Mitić, M., & Miljković, Z. (2016). Integration of process planning and scheduling using chaotic particle swarm optimization algorithm. Expert Systems with Applications, 64, 569–588.
Zhang, Z., Tang, R., Peng, T., Tao, L., & Jia, S. (2016). A method for minimizing the energy consumption of machining system: integration of process planning and scheduling. Journal of Cleaner Production, 137, 1647–1662.
Zhang, L., & Wong, T.N. (2016). Solving integrated process planning and scheduling problem with constructive meta-heuristics. Information Sciences, 340–341, 1–16.
Panwalkar, S.S., Smith, M.L., & Seidmann, A. (1982). Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem. Operations Research, 30, 391–399.
Biskup, D., & Jahnke, H. (2001). Common due date assignment for scheduling on a single machine with jointly reducible processing times. International Journal of Production Economics, 69, 317–322.
Cheng, T.C.E., Chen, Z.L., & Shakhlevich, N.V. (2002). Common due date assignment and scheduling with ready times. Computers & Operations Research, 29, 1957–1967.
Cheng, T.C.E., Kang, L.Y., & Ng, C.T. (2005). Single machine due-date scheduling of jobs with decreasing start-time dependent processing times. International Transactions in Operational Research, 12, 355–366.
Lin, S.W., Chou, S.Y., & Chen, S.C. (2006). Metaheuristic approaches for minimizing total earliness and tardiness penalties of single-machine scheduling with a common due date. Journal of Heuristics, 13, 151–165.
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, 55, 494–502.
Xia, Y., Chen, B., & Yue, J. (2008). Job sequencing and due date assignment in a single machine shop with uncertain processing times. European Journal of Operational Research, 184, 63–75.
Gordon, V.S., & Strusevich, V.A. (2009). Single machine scheduling and due date assignment with positionally dependent processing times. European Journal of Operational Research, 198, 57–62.
Li, J., Yuan, X., Lee, E.S., & Xu, D. (2011a). 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, 62, 4126–4139.
Adamopoulos, G.I., & Pappis, C.P. (1998). Scheduling under a common due-data on parallel unrelated machines. European Journal of Operational Research, 105, 494–501.
Cheng, T.C.E., & Kovalyov, M.Y. (1999). Complexity of parallel machine scheduling with processing-plus-wait due dates to minimize maximum absolute lateness. European Journal of Operational Research, 114, 403–410.
Birman, M., & Mosheiov, G. (2004). A note on a due-date assignment on a two-machine flow-shop. Computers & Operations Research, 31, 473–480.
Lauff, V., & Werner, F. (2004). Scheduling with common due date, earliness and tardiness penalties for multimachine problems: A survey. Mathematical and Computer Modelling, 40, 637– 655.
Allaoua, H., & 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, 36, 471– 478.
Yang, S.J., Yang, D.L., & Cheng, T.C.E. (2010). Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance. Computers & Operations Research, 37, 1510–1514.
Huynh Tuong, N., & Soukhal, A. (2010). Due dates assignment and JIT scheduling with equal-size jobs. European Journal of Operational Research, 205, 280–289.
Li, X., Gao, L., Zhang, C., & Shao, X. (2010). A review on Integrated Process Planning and Scheduling. International Journal of Manufacturing Research, 5, 161–180.
Vinod, V., & 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, 129, 127–146.
Li, S., Ng, C.T., & Yuan, J. (2011b). Group scheduling and due date assignment on a single machine. International Journal of Production Economics, 130, 230–235.
Zhang, R., & Wu, C. (2012). A hybrid local search algorithm for scheduling real-world job shops with batch-wise pending due dates. Engineering
Yin, Y., Cheng, S.R., Cheng, T.C.E., Wu, C.C., & Wu, W.H. (2012). Two-agent single-machine scheduling with assignable due dates. Applied Mathematics and Computation, 219, 1674–1685.
Iranpoor, M., Fatemi Ghomi, S.M.T., & Zandieh, M. (2013). Due-date assignment and machine scheduling in a low machine-rate situation with stochastic processing times. Computers & Operations Research, 40, 1100–1108.
Yin, Y., Cheng, T.C.E., Cheng, S.R., & Wu, C.C. (2013). Single-machine batch delivery scheduling with an assignable common due date and controllable processing times. Computers & Industrial Engineering, 65, 652–662.
Shabtay, D. (2016). Optimal restricted due date assignment in scheduling. European Journal of Operational Research, 252, 79–89.
Koulamas, C. (2017). Common due date assignment with generalized earliness / tardiness penalties. Computers & Industrial Engineering, 109, 79–83.
Mosheiov, G., & Sarig, A. (2010). Scheduling with a common due-window: Polynomially solvable cases. Information Sciences, 180, 1492–1505.
Cheng, T.C.E., Yang, S.J., & Yang, D.L. (2012). Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity. International Journal of Production Economics, 135, 154–161.
Zhao, C., & Tang, H. (2012). A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity. Computers & Operations Research, 39, 1300–1303.
Janiak, A., Janiak, W., Kovalyov, M.Y., Kozan, E., & Pesch, E. (2013). Parallel machine scheduling and common due window assignment with job independent earliness and tardiness costs. Information Sciences, 224, 109–117.
Wang, J.B., Liu, L., & Wang, C. (2013). Single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs. Applied Mathematical Modelling, 37, 8394–8400.
Ji, M., Ge, J., Chen, K., & Cheng, T.C.E. (2013). Single-machine due-window assignment and scheduling with resource allocation, aging effect, and a deteriorating rate-modifying activity. Computers & Industrial Engineering, 66, 952–961.
Ji, M., Chen, K., Ge, J., & Cheng, T.C.E. (2014). Group scheduling and job-dependent due window assignment based on a common flow allowance. Computers & Industrial Engineering, 68, 35–41.
Yang, D.L., Lai, C.J., & Yang, S.J. (2014). Scheduling problems with multiple due windows assignment and controllable processing times on a single machine. International Journal of Production Economics, 150, 96–103.
Liu, L., Wang, J.J. , Liu, F., & Liu, M. (2017). Single machine due window assignment and resource allocation scheduling problems with learning and general positional effects. Journal of Manufacturing Systems, 43, Part 1, 1–14.
Rechenberg, I. (1965). Cybernetic Solution Path of an Experimental Problem. Ministry of Aviation, Royal Aircraft Establishment Library Translation No: 1122.
Schwefel, H.P. (1981). Numerical Optimization of Computer Models. John Wiley & Sons, Inc.: New York, NY.