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

Halil Ibrahim Demir, Onur Canpolat

Abstract


Process planning, scheduling and due-date assignment are three important manufacturing functions in our life. They all try to get local optima and there can be enormous loss in overall performance value if they are handled separately. That is why they should be handled concurrently. Although integrated process planning and scheduling with due date assignment problem is not addressed much in the literature, there are numerous works on integrated process planning and scheduling and many works on scheduling with due date assignment. Most of the works in the literature assign common due date for the jobs waiting and due dates are determined without taking into account of the weights of the customers. Here process planning function is integrated with weighted shortest processing times (WSPT) scheduling and weighted slack (WSLK) due date assignment. In this study unique due dates are given to each customer and important customers gets closer due dates. Integration of these three functions is tested for different levels of integration with genetic algorithms, evolutionary strategies, hybrid genetic algorithms, hybrid evolutionary strategies and random search techniques. Best combinations are found as full integration with genetic search and hybrid genetic search. Integration of these three functions provided substantial improvements in global performance.


Keywords


Process planning; weighted scheduling; weighted due-date assignment; genetic algorithm; evolutionary strategies; hybrid metaheuristics; random search

Full Text:

PDF

References


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 multi-objective 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). Meta-heuristic 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. (2011). 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. (2011). 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 Applications of Artificial Intelligence, 25, 209–221.

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.




DOI: http://dx.doi.org/10.11121/ijocta.01.2018.00412

Refbacks

  • There are currently no refbacks.


Copyright (c) 2017 Halil Ibrahim Demir

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

footer_771

   ithe_170     crossref_284         ind_131_43_x_117_117  Scopus  EBSCO_Host    ULAKBIM   PROQUEST   ZBMATH more...