A Tabu Search and Hybrid Evolutionary Strategies Algorithms for the Integrated Process Planning and Scheduling with Due-date Agreement

Öz

There are three important functions of manufacturing which are process planning, scheduling and due date assignment. Instead of executing these functions separately, combining them together helps making more realistic and applicable plans. In this problem context random search, semi-tabu, random/semi-tabu hybrid, evolutionary strategies, and random/evolutionary strategies hybrid methods are utilized in solution. Different sized job shops are studied for performance tracking. As a result of study differences between individual solutions and integrated solutions was revealed. It is found that integrating these functions are advantageous in terms of total performance measure, and thus customer satisfaction. Random search is better than ordinary solutions. On the other hand, semi-tabu, evolutionary strategies and their hybrids are outperformed random search. Hybrid search methods are found promising.

Anahtar Kelimeler

• Process planning
• weighted due-date assignment
• weighted scheduling
• random search
• hybrid evolutionary strategies
• hybrid semi-tabu search

Teslim Tarihi Anlaşmalı Entegre Süreç Planlama ve Çizelgeleme için Tabu Arama ve Hibrit Evrimsel Stratejiler Algoritmaları

Öz

İmalatın, süreç planlama, çizelgeleme ve teslim tarihinin belirlenmesi olmak üzere üç önemli fonksiyonu bulunmaktadır. Bu fonksiyonları ayrı ayrı gerçekleştirmek yerine, üçünü birlikte değerlendirmek daha gerçekçi ve uygulanabilir planların hazırlanmasına yardımcı olacaktır. Bu problemin çözümünde rassal arama, kısmi tabu, rassal arama/kısmi tabu hibriti, evrimsel stratejiler ve rassal arama/evrimsel stratejiler hibriti yöntemleri kullanılmıştır. Yöntemlerin performansını değerlendirmek amacıyla farklı büyüklükteki atölyeler üzerinde çalışılmıştır. Çalışma sonucunda ayrık çözümler ile entegre çözümler arasındaki farklar ortaya çıkmıştır. Bu fonksiyonların entegrasyonunun toplam performans açısından ve dolayısıyla müşteri memnuniyeti açısından avantajlı olduğu bulunmuştur. Rassal aramanın sıradan çözümlerden daha iyi olduğu görülmüştür. Öte yandan, kısmi tabu, evrimsel stratejiler ve bunların melezleri rassal aramadan daha iyi performans göstermektedir. Hibrit arama yöntemlerinin gelecek vadettiği görülmüştür.

Anahtar Kelimeler

• Süreç planlama
• ağırlıklı teslim tarihi ataması
• ağırlıklı çizelgeleme
• rassal arama
• hibrit evrimsel stratejiler
• hibrit kısmi tabu arama

Kaynakça

1. Aldakhilallah, K.A., Ramesh, R., 1999. Computer-integrated process planning and scheduling (CIPPS): intelligent support for product design, process planning and control. International journal of production research 37, 481–500.
2. 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, ISCO 2010 - International Symposium on Combinatorial Optimization 36, 471–478. https://doi.org/10.1016/j.endm.2010.05.060
3. Baykasoğlu, A., Göçken, M., Unutmaz, Z.D., 2008. New approaches to due date assignment in job shops. European Journal of Operational Research 187, 31–45. https://doi.org/10.1016/j.ejor.2007.02.020
4. Bhaskaran, K., 1990. Process plan selection. THE INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 28, 1527–1539.
5. Birman, M., Mosheiov, G., 2004. A note on a due-date assignment on a two-machine flow-shop. Computers & Operations Research 31, 473–480. https://doi.org/10.1016/S0305-0548(02)00225-3
6. 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. https://doi.org/10.1016/S0925-5273(00)00040-2
7. Brandimarte, P., 1999. Exploiting process plan flexibility in production scheduling: A multi-objective approach. European Journal of Operational Research 114, 59–71. https://doi.org/10.1016/S0377-2217(98)00029-0
8. Cai, X., Lum, V.Y.S., Chan, J.M.T., 1997. Scheduling about a common due date with kob-dependent asymmetric earliness and tardiness penalties. European journal of operational research 98, 154–168.

9. Ceven, E., Demir, H.I., 2007. Benefits of Integrating Due-Date Assignment with Process Planning and Scheduling (Master of Science Thesis). Sakarya University.
10. Chen, Z.-L., 1997. Scheduling with batch setup times and earliness-tardiness penalties. European Journal of Operational Research 96, 518–537.
11. 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. https://doi.org/10.1016/S0377-2217(98)00111-8
12. Corti, D., Portioli-Staudacher, A., 2004. A concurrent engineering approach to selective implementation of alternative processes. Robotics and Computer-Integrated Manufacturing 20, 265–280. https://doi.org/10.1016/j.rcim.2003.10.012
13. Demir, H.I., Taskin, H., 2005. Integrated Process Planning, Scheduling and Due-Date Assignment (PhD Thesis). Sakarya University.
14. Drstvenšek, I., Balič, J., 2003. Responding ability in dynamic production circumstances. Journal of materials processing technology 133, 71–78.
15. Gindy, N.N., Saad, S.M., Yue, Y., 1999. Manufacturing responsiveness through integrated process planning and scheduling. International Journal of Production Research 37, 2399–2418.
16. Gordon, V., Kubiak, W., 1998. Single machine scheduling with release and due date assignment to minimize the weighted number of late jobs. Information Processing Letters 68, 153–159. https://doi.org/10.1016/S0020-0190(98)00153-7
17. 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. https://doi.org/10.1016/S0377-2217(01)00181-3
18. 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. https://doi.org/10.1016/j.ejor.2008.07.044
19. Gordon, V.S., Strusevich, V.A., 1999. Earliness penalties on a single machine subject to precedence constraints: SLK due date assignment. Computers & Operations Research 26, 157–177.
20. Khoshnevis, B., Chen, Q.M., 1991. Integration of process planning and scheduling functions. J Intell Manuf 2, 165–175. https://doi.org/10.1007/BF01471363
21. 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. https://doi.org/10.1016/S0305-0548(02)00063-1
22. Koulamas, C., 2017. Common due date assignment with generalized earliness/tardiness penalties. Computers & Industrial Engineering 109, 79–83. https://doi.org/10.1016/j.cie.2017.04.040
23. Kovalyov, M.Y., 1997. Batch scheduling and common due date assignment problem: an NP-hard case. Discrete applied mathematics 80, 251–254.
24. 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. https://doi.org/10.1016/j.mcm.2003.05.019
25. Lawrence, S.R., 1994. Negotiating due-dates between customers and producers. International Journal of Production Economics 37, 127–138.
26. 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. https://doi.org/10.1016/j.cie.2009.09.003
27. Li, S., Ng, C.T., Yuan, J., 2011. Scheduling deteriorating jobs with CON/SLK due date assignment on a single machine. International Journal of Production Economics 131, 747–751. https://doi.org/10.1016/j.ijpe.2011.02.029
28. Li, X., Gao, L., Li, W., 2012. Application of game theory based hybrid algorithm for multi-objective integrated process planning and scheduling. Expert Systems with Applications 39, 288–297. https://doi.org/10.1016/j.eswa.2011.07.019
29. Luss, H., Rosenwein, M.B., 1993. A due date assignment algorithm for multiproduct manufacturing facilities. European Journal of Operational Research 65, 187–198.
30. 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. https://doi.org/10.1080/002075400188618
31. Moon, C., Kim, J., Hur, S., 2002. Integrated process planning and scheduling with minimizing total tardiness in multi-plants supply chain. Computers & Industrial Engineering 43, 331–349. https://doi.org/10.1016/S0360-8352(02)00078-5
32. 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. https://doi.org/10.1016/j.cie.2007.06.018
33. Morad, N., Zalzala, A., 1999. Genetic algorithms in integrated process planning and scheduling. Journal of Intelligent Manufacturing 10, 169–179. https://doi.org/10.1023/A:1008976720878
34. Mosheiov, G., 2001. A common due-date assignment problem on parallel identical machines. Computers & Operations Research 28, 719–732. https://doi.org/10.1016/S0305-0548(99)00127-6
35. Özgüven, C., Özbakır, L., Yavuz, Y., 2010. Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Applied Mathematical Modelling 34, 1539–1548. https://doi.org/10.1016/j.apm.2009.09.002
36. 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.
37. 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. https://doi.org/10.1080/0951192X.2011.562543
38. Pinedo, M., Chao, X., 1998. Operations Scheduling with Applications in Manufacturing and Services. McGraw-Hill Higher Education.
39. Rechenberg, I., 1965. Cybernetic solution path of an experimental problem. Ministry of Aviation, Royal Aircraft Establishment, Library Translation.
40. Schwefel, H.-P., 1981. Numerical optimization of computer models. John Wiley & Sons, Inc.
41. Seker, A., Erol, S., Botsali, R., 2013. A neuro-fuzzy model for a new hybrid integrated Process Planning and Scheduling system. Expert Systems with Applications 40, 5341–5351. https://doi.org/10.1016/j.eswa.2013.03.043
42. Shabtay, D., 2016. Optimal restricted due date assignment in scheduling. European Journal of Operational Research 252, 79–89. https://doi.org/10.1016/j.ejor.2015.12.043
43. Shrestha, R., Takemoto, T., Ichinose, K., Sugimura, N., 2008. A study on integration of process planning and scheduling system for holonic manufacturing with modification of process plans. International Journal of Manufacturing Technology and Management 14, 359–378.
44. Tan, W., Khoshnevis, B., 2000. Integration of process planning and scheduling— a review. Journal of Intelligent Manufacturing 11, 51–63. https://doi.org/10.1023/A:1008952024606
45. Thomalla, C.S., 2001. Job shop scheduling with alternative process plans. International Journal of Production Economics 74, 125–134. https://doi.org/10.1016/S0925-5273(01)00119-0
46. Tuong, N.H., Soukhal, A., 2010. Due dates assignment and JIT scheduling with equal-size jobs. European Journal of Operational Research 205, 280–289. https://doi.org/10.1016/j.ejor.2010.01.016
47. Usher, J.M., 2003. Evaluating the impact of alternative plans on manufacturing performance. Computers & Industrial Engineering 45, 585–596. https://doi.org/10.1016/S0360-8352(03)00076-7
48. Usher, J.M., Fernandes, K.J., 1996. Dynamic process planning—the static phase. Journal of Materials Processing Technology 61, 53–58.
49. 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. https://doi.org/10.1016/j.ijpe.2010.08.017
50. Weintraub, A., Cormier, D., Hodgson, T., King, R., WIlson, J., Zozom, A., 1999. Scheduling with alternatives: a link between process planning and scheduling. IIE Transactions 31, 1093–1102. https://doi.org/10.1023/A:1007683710427
51. Wilhelm, W.E., Shin, H.-M., 1985. Effectiveness of alternate operations in a flexible manufacturing system. International Journal of Production Research 23, 65–79. https://doi.org/10.1080/00207548508904691
52. Yang, T., He, Z., Cho, K.K., 1994. An effective heuristic method for generalized job shop scheduling with due dates. Computers & industrial engineering 26, 647–660.
53. Zhang, H.-C., Mallur, S., 1994. An integrated model of process planning and production scheduling. International Journal of Computer Integrated Manufacturing 7, 356–364. https://doi.org/10.1080/09511929408944623
54. Zhang, L., Wong, T.N., 2015. An object-coding genetic algorithm for integrated process planning and scheduling. European Journal of Operational Research 244, 434–444. https://doi.org/10.1016/j.ejor.2015.01.032
55. 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.