Due Date Determination in Dynamic Job Shop Scheduling with Artificial Neural Network

Öz

In this study, an artificial neural network approach that is thought to produce better results as an alternative to due date determination methods in dynamic job shop scheduling environment is presented and its feasibility is demonstrated. The performance of the neural network model is compared with five different regression models. An event oriented simulation software is developed for the determination of the coefficients of the regression models and for the generation of data to be used in the training of the neural network model. Back-propagation artificial neural network was used as an artificial neural network model and a software was developed. After the regression models were created and the neural network was trained, the simulation software was run for the shortest processing time and earliest due date priority rules for comparison purposes. In order to compare the models, average absolute deviation from the due date, mean square of absolute deviation from the due date, average tardiness, number of tardy jobs, average earliness and number of early jobs were used as performance metrics. As a result of the study, the artificial neural network model was found to be effective in due date determination. Both the shortest processing time first and the earliest due date first priority rules gave good results in terms of several performance metrics. It was observed that the neural network gave better results in the shortest processing time priority rule in general.

Anahtar Kelimeler

• Dynamic Job Shop
• Due Date Determination
• Artificial Neural Networks

Dinamik Atölye Çizelgelemede Yapay Sinir Ağları ile Teslim Tarihi Belirlenmesi

Öz

Bu çalışmada dinamik atölye çizelgeleme ortamında teslim tarihi belirleme yöntemlerine alternatif olarak daha iyi sonuçlar üreteceği düşünülen bir yapay sinir ağı yaklaşımı sunulmuş ve uygulanabilirliği gösterilmiştir. Sinir ağı modelinin performansı beş farklı regresyon modeliyle karşılaştırılmıştır. Regresyon modellerine ait katsayıların belirlenmesi ve sinir ağı modelinin eğitiminde kullanılacak verilerin üretilmesi amacıyla olay artımlı bir simülasyon yazılımı geliştirilmiştir. Yapay sinir ağı modeli olarak geriye yayılımlı yapay sinir ağı kullanılmış ve bir yazılım geliştirilmiştir. Regresyon modelleri oluşturulduktan ve sinir ağı eğitildikten sonra karşılaştırma amacıyla simülasyon yazılımı en kısa işlem süresi ve en erken bitiş tarihi öncelik kuralları için çalıştırılmıştır. Modellerin karşılaştırılması amacıyla performans ölçütleri olarak teslim tarihinden ortalama mutlak sapma, teslim tarihinden mutlak sapmanın ortalama karesi, ortalama gecikme, geciken iş sayısı, ortalama erkencilik ve erken iş sayısı kullanılmıştır. Çalışma sonucunda yapay sinir ağı modelinin teslim tarihi belirlenmesinde etkili olduğu görülmüştür. Hem en kısa işlem süreli önce hem de en erken teslim tarihli önce öncelik kuralları, çeşitli performans ölçümleri açısından iyi sonuçlar vermiştir. Yapay sinir ağının genel olarak en kısa işlem süresi öncelik kuralında daha iyi sonuçlar verdiği görülmüştür.

Anahtar Kelimeler

• Dinamik atölye
• Teslim tarihi belirleme
• Yapay sinir ağları

Kaynakça

1. Baker, K. R., “Introduction to Sequencing and Scheduling”, John Wiley & Sons, New York, 1974.
2. Baykasoglu, A., Gokcen, M., "Gene expression programming based due date assignment in a simulated job shop", Expert Systems with Applications, Cilt 26, Sayı 10, Sayfa 12143-12150, Aralık 2009.
3. Birman, M., Mosheiov, G., “A note on a Due Date Assignment on a Two Machine Flow Shop”, Computers and Operations Research, No. 31, s. 473-480, 2004.
4. Biskup, D., Jahnke, H., “Common Due Date Assignment for Scheduling on a Single Machine with Jointly Reducible Processing Times”, International Journal of Economics”, No. 69, s. 317-322, 2001.
5. Chen, T., “An Intelligent Hybrid System for Wafer Lot Output Time Prediction”, Advanced Engineering Informatics, No. 21, s. 55-65, 2007.
6. Cheng, T. C. E., Gupta, M. C.,” Survey of Scheduling Research Involving Ddue Date Determination Decisions”, European Journal of Operational Research, No. 38, s. 156-166, 1989.
7. Cheng, T. C. E., Chen, Z. L., Shakhlevich, N. V., “Common Due Date Assignment and Scheduling with Ready Times”, Computers and Operations Research, No. 29, s. 1957-1967, 2002.
8. French, S, “Sequencing and Scheduling: An Introduction to the Mathematics of the Job Shop”, John Wiley & Sons, New York, 1982.

9. Kohonen, T., “State of the Art in Neural Computing”, IEEE First International Conference on Neural Networks, No. 1, s. 79-90, 1987.
10. Gupta, J. N. D., Kruger, K., Lauff, V., Werner, F., Sotskov, Y. N., “Heuristics for Flow Shops with Controllable Processing Times and Assignable Due Dates”, Computers and Operations Research, No. 29, s. 1417-1439, 2002.
11. Inal, A., F., Sel, C., Aktepe, A., Turker, A., K., Ersoz, S., “A Multi-Agent Reinforcement Learning Approach to the Dynamic Job Shop Scheduling Problem”, Sustainability, Vol. 15 (10), 8262, 2023.
12. Kianpour, P., Gupta, D., Krishnan, K., K., Gopalakrishnan, B., “Automated job shop scheduling with dynamic processing times and due dates using project management and industry 4.0”, Journal of Industrial and Production Engineering, Cilt 38, Sayı 7, 2021.
13. Min, L., Cheng, W., “Genetic Algorithms fort he Optimal Common Due Date Assignment and the Optimal Scheduling Policy in Paralel Machine Earliness/Tardiness Scheduling Problems”, Robotics and Computer Integrated Manufacturing, No. 22, s. 279-287, 2006.
14. Mosheiov, G., “A Common Due Date Assignment Problem on Paralel Identical Machines”, Computers and Operations Research, N0. 28, s. 719-732, 2001.
15. Mosheiov, G., Oron, D., “Due Date Assignment and Maintenance Activitty Scheduling Problem”, Mathematical and Computer Modelling, No. 44, s. 1053-1057, 2006.
16. Mosheiov, G., Sarig, A., “The minmax due-date assignment problem with acceptable lead-times”, Annals of Operations Research, Vol. 343, pp. 401–410, 2024.
17. Negnevitsky, M., “Artificial Intelligence: A Guide to Intelligent Systems”, Addison-Wesley, 2002.
18. Neuralware Inc., “NeuralWorks Professional II/Plus: Neural Computing, Pittsburg, 1990.
19. Orhunbilge, N., “Uygulamalı Regresyon ve Korelasyon Analizi”, Avcıol Basım Yayın, İstanbul, 2000.
20. Oztemel, E., “Yapay Sinir Ağları”, Papatya Yayıncılık, İstanbul, 2003.
21. Philipoom, P. R., Rees, L. P., Wıegmann, L., “Using Neural Networks to Determine Internally Set Due Date Assignments for Shop Scheduling”, Decision Sciences, No. 25-5/6, s. 825-851, 1994.
22. Philipoom, P. R., “The Choice of Dispatching Rules in a Shop Using Internally Set Due Dates with Quoted Leadtime and Tardiness Costs”, International Journal of Production Research, No. 7, s. 1641-1655, 2000.
23. Sabuncuoglu, I, Comlekci, A., “Operation Based Flow Time Estimation in a Dynamic Job Shop”, Omega, No. 30, s. 423-442, 2002.
24. Sha, D. Y., Hsu, S. Y., “Due Date Assignment in Wafer Fabrication Using Artificial Neural Networks”, International Journal of Advanced Manufacturing Technology, No. 23, s. 768-775, 2004.
25. Sha, D. Y., Liu, C. H., “Using Data Mining for Due Date Assignment in a Dynamic Job Shop Environment”, International Journal of Advanced Manufacturing Technology, No. 25, s. 1164-1174, 2005.
26. Shabtay, D., Steiner, G., “Two Due Date Assignment Problems in Scheduling a Single Machine”, Operations Research Letters, No. 43, s. 683-691, 2006.
27. Song, D. P., Hicks, C., Earl, C. F., “Product Due Date Assignment for Complex Assemblies”, International Journal of Economics, No. 76, s. 243-256, 2002.
28. Tarı, R., “Ekonometri”, Alfa Basım Yayım, İstanbul, 1999.
29. Tasgetiren, M. F., “Atölye Tipi Çizelgeleme Problemi için Bir Uzman-Yapay Sinir Ağı Modeli”, Doktora Tezi, İstanbul Üniversitesi, 1996.
30. Teymourıfar, A, Ozturk, G., “New dispatching rules and due date assignment models for dynamic job shop scheduling problems”, International Journal of Manufacturing Research, Cilt 13, Sayı 4, 2018.
31. Veral, E. A., “Computer Simulation of Due Date Setting in Multimachine Job Shops”, Computers and Industrial Engineering, No. 41, s. 77-94, 2001.
32. Vinod, K., T., Prabagaran, S., Joseph, O., A., “Dynamic due date assignment method: A simulation study in a job shop with sequence-dependent setups”, Journal of Manufacturing Technology Management, Cilt 30, Sayı 6, 2019.
33. Wang, C. S., Uzsoy, R., “A Genetic Algoritm to Minimize Maximum Lateness on a Batch Processing Machine”, Computers and Operations Research, No. 29, s. 1621-1640, 2002.
34. Wang, X., Liu, W., Lu, L., Zhao, P., Zhang, R., “Due date assignment scheduling with positional-dependent weights and proportional setup times”, Mathematical Biosciences and Engineering, Vol. 19, Issue 5, pp. 5104-5119, 2022.
35. Xiao, W. Q., Lı, C. L., “Approximation Algorithms for Common Due Date Assignment and Job Schedulin on Parallel Machines”, IIE Transactions, No. 34, s. 467-477, 2002.
36. Yang, S. Wang, D., “A New Adaptive Neural Network and Heuristics Approach for Job Shop Scheduling”, Computers and Operations Research, No. 28, s. 955-971, 2001.
37. Yang, H., Sun, Q., Saygin, C., Sun, S., "Job shop scheduling based on earliness and tardiness penalties with due dates and deadlines: an enhanced genetic algorithm", The International Journal of Advanced Manufacturing Technology, Vol. 61, pp. 657–666, 2012.
38. Zhao, C., “Common duedate assignment and single-machine scheduling with release times to minimize the weighted number of tardy jobs”, Japan J. Indust. Appl. Math., Vol. 33, pp. 239–249, 2016.