حل مشاكل جدولة الآلة ثنائية المعايير وثنائية الأهداف باستخدام خوارزميتين متطورتين
محتوى المقالة الرئيسي
الملخص
تضمن العديد من الأنظمة الصناعية معايير وأهداف متعددة، مما يجعلها مشكلات معقدة للغاية في علم الحوسبة، مثل مشكلات جدولة المهام وغيرها. في هذا البحث، تم اقترح دراسة مشكلات جدولة الماكنة ثنائية المعايير وثنائية الأهداف، والتي تم حلها باستخدام خوارزميتين تطوريتين مستوحاتين من الطبيعة، وهما خوارزمية التلدين (Simulated Annealing - SA) وخوارزمية وكيل النحل (Bee Agent based Algorithm - BA).
يمكن تمثيل المشكلة اعلاه بجدولة مجموعة من المهام على عدة آلات، حيث تُعد هذه المسألة من المسائل الاساسية لجدولة الماكنة، لأن الحل يجب أن يركّز على تحقيق تحسين متزامن لهدفين متضاربين: تقليل وقت الإكمال الكلي (Makespan) وتقليل إجمالي التأخير (Total Tardiness). وتُصنف هذه المشكلة ضمن فئة المشكلات المعروفة بصعوبتها الحسابية (NP-Hard)، ولهذا السبب تم استخدام طريقتين تطوريتين للبحث عن حلول ذكية ضمن مساحة حلول واسعة ومعقدة للغاية.
ايضا، تم تطوير نموذج رياضي لمشكلة الجدولة متعددة الاهداف والمعاييراعتمادًا على الأهداف المذكورة أعلاه. وقد قمنا باقتراح تعديل ثنائي القاعدة (dual-based tune-up) لكل من خوارزميتي SA وBA، حيث تم برمجة كل منهما وتنفيذها خصيصًا لحل النموذج المقترح الخاص بالجدولة بما يتناسب مع الطبيعة الثنائية لوظائف المشكلة قيد الدراسة.
وأظهرت النتائج أن كلتا الخوارزميتين قادرتان على الحصول على حلول متوازنة وفعّالة من حيث الزمن. ومن ناحية أخرى، قدّمت خوارزمية النحل أداءً أفضل من حيث جودة وتنوّع الحلول، بينما تميّزت خوارزمية محاكاة التلدين بسرعة التقارب نحو الحلول المثلى. ومن النتاائج اعلاه نستطيع القول ان هذا البحث يمثل إضافة قيّمة نحو تطوير أداة ذكية لمواجهة مشكلات الجدولة المعقدة، كما يفتح المجال للتطبيق المستقبلي باستخدام خوارزميات هجينة أو متعددة السكان.
##plugins.themes.bootstrap3.displayStats.downloads##
تفاصيل المقالة
القسم
كيفية الاقتباس
المراجع
Al-Kayiem, H.H., 2010. Study on the thermal accumulation and distribution inside a parked car cabin. American Journal of Applied Sciences, 7(6), pp. 784–789.
Al-Nuaimi, A., 2015. Local search algorithms for multiobjective scheduling problem. Journal of Al-Rafidain University College for Sciences, pp. 201–217. https://doi.org/10.55562/jrucs.v36i2.255
Ali, F.H., 2020. Optimal and near optimal solutions for multi objective function on a single machine. In: 2020 International Conference on Computer Science and Software Engineering (CSASE). https://doi.org/10.1109/CSASE48920.2020.9142053
Bakar, M.R., Abbas, I.T., Kalal, M.A., AlSattar, H.A., Bakhayt, A.G. and Kalaf, B.A., 2017. Solution for multi-objective optimisation master production scheduling problems based on swarm intelligence algorithms. Journal of Computational and Theoretical Nanoscience, 14(11), pp. 5184–5194.
Błażewicz, J., Ecker, K.H., Pesch, E., Schmidt, G. and Węglarz, J., 2007. Handbook on scheduling: From theory to applications. Berlin: Springer.
Burmeister, S.C., Guericke, D. and Schryen, G., 2024. A memetic NSGA-II for the multi-objective flexible job shop scheduling problem with real-time energy tariffs. Flexible Services and Manufacturing Journal, 36, pp. 1530–1570.
Celik, E. and Topaloglu, S., 2021. A novel simulated annealing-based optimization approach for cluster-based task scheduling. Cluster Computing, 24(4), pp. 2927–2956.
Chen, B., Zeng, Z. and Zhang, Y., 2014. A new local search-based multiobjective optimization algorithm. IEEE Transactions on Evolutionary Computation, 19(1), pp. 50–73.
Chong, C.S., Low, M.Y.H., Sivakumar, A.I. and Gay, K.L., 2006. A bee colony optimization algorithm to job shop scheduling. In: Proceedings of the Winter Simulation Conference, pp. 1954–1961.
Colombo, F., 2014. Mathematical programming algorithms for network optimization problems. PhD thesis. Università degli Studi di Milano.
Davidović, T., Ramljak, D. and Šelmić, M., 2015. Bee colony optimization—Part I: The algorithm overview. YUJOR, 25(1), pp. 33–56.
Doctor, S., Venayagamoorthy, G.K. and Gudise, V.G., 2004. Optimal PSO for collective robotic search applications. In: Proceedings of the Congress on Evolutionary Computation, pp. 1390–1395.
Festa, P., 2014. A brief introduction to exact, approximation, and heuristic algorithms for solving hard combinatorial optimization problems. In: International Conference on Transparent Optical Networks, pp. 1–20.
Gulati, R. and Singh, N., 2014. A literature review of bee colony optimization algorithms. In: Innovative Applications of Computational Intelligence on Power, Energy and Controls (CIPECH), pp. 499–504.
Ibrahim, M.H., 2022. Solving multi-objectives function problem using branch and bound and local search methods. International Journal of Nonlinear Analysis and Applications, pp. 1649–1658.
Khan, K.A. and Khan, A.S., 2012. A comparison of BA, GA, PSO, BP and LM for training feed forward neural networks in e-learning context. International Journal of Intelligent Systems and Applications.
Khare, A. and Rangnekar, S., 2013. A review of particle swarm optimization and its applications in solar photovoltaic system. Applied Soft Computing, 13(5), pp. 2997–3006.
Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P., 1983. Optimization by simulated annealing. Science, 220(4598), pp. 671–680.
Lalwani, S., Sharma, H. and Dashora, Y., 2013. A comprehensive survey: Applications of multi-objective particle swarm optimization algorithm. Transactions on Combinatorics, 2(1), pp. 39–101.
Maraveas, C., 2022. Applications of IoT for optimized greenhouse environment and resources management. Computers and Electronics in Agriculture, 198, P. 106993.
Marini, F. and Walczak, B., 2015. Particle swarm optimization (PSO): A tutorial. Chemometrics and Intelligent Laboratory Systems, 149, pp. 153–165.
Meissner, M., Schmuker, M. and Schneider, G., 2006. Optimized particle swarm optimization and its application to artificial neural network training. BMC Bioinformatics, 7(1), P. 125.
Meng, L., Zhang, C., Zhang, B., Gao, K., Ren, Y. and Sang, H., 2023. MILP modelling and optimization of multi-objective flexible job shop scheduling problem with controllable processing times. Swarm and Evolutionary Computation, P. 101374.
Möhring, R.H., Schulz, A.S. and Uetz, M., 2003. Solving project scheduling problems by minimum cut computations. Management Science, 49(3), pp. 330–350.
Mou, J., Song, W. and Chen, Q., 2017. Multi-objective inverse scheduling optimization of single-machine shop system with uncertain due-dates. Cluster Computing, 20(1), pp. 371–390.
Mousa, A.A., El-Shorbagy, M.A. and Abd-El-Wahab, A., 2012. Local search-based hybrid particle swarm optimization algorithm for multiobjective optimization. Swarm and Evolutionary Computation, 3, pp. 1–14.
Onwunalu, J.E. and Durlofsky, L.J., 2010. Application of a particle swarm optimization algorithm for determining optimum well location and type. Computational Geosciences, 14(1), pp. 183–198.
Pham, D.T., Castellani, M., Ghanbarzadeh, A. and Koç, E., 2007. The bees algorithm: A novel tool for complex optimization problems. International Journal of Manufacturing Research, 2(4), pp. 454–472.
Pinedo, M.L., 2016. Scheduling: Theory, algorithms, and systems. 5th ed. Cham: Springer.
Poli, R., 2007. An analysis of publications on particle swarm optimization applications. Journal of Artificial Evolution and Applications.
Teodorovic, D., 2006. Bee colony optimization: Principles and applications. In: Neural Network Applications Conference, pp. 151–156.
Thomas, H., Cormen, T., Leiserson, C. and Rivest, R., 2009. Introduction to algorithms. 3rd ed.
Umar, M.F., 2025. Predicting the durability properties of concrete with recycled plastic aggregate. Journal of Engineering, 31(10), pp. 1–22. https://doi.org/10.31026/j.eng.2025.10.01
Wang, Y., Li, J. and Zhang, H., 2022. A hybrid particle swarm optimization and simulated annealing algorithm for job shop scheduling. European Journal of Operational Research, 299(3), pp. 1021–1035.
Wu, C.C., 2007. Heuristic algorithms for solving maximum lateness scheduling problem with learning considerations. Computers & Industrial Engineering, 52(1), pp. 124–132.
Wu, R., Luo, E., Li, X., Tang, H. and Li, Y., 2025. Hybrid artificial bee colony algorithm with Q-learning for distributed scheduling. Swarm and Evolutionary Computation.
Yousif, S.F., Ali, F.H. and Alshaikhli, K.F., 2023. Using local search methods for solving two multi-criteria machine scheduling problems, Al-Mustansiriyah Journal of Science, 34(4), pp. 96–103. https://doi.org/10.23851/mjs.v34i4.1430
Yousif, S.F., 2024. Solving maximum early jobs time and range of lateness jobs times problem. Iraqi Journal of Science, pp. 923–937. https://doi.org/10.24996/ijs.2024.65.2.28
Zhang, W., 2024. Enhancing multi-objective evolutionary algorithms with machine learning for scheduling problems. Frontiers in Industrial Engineering, 2, P. 1337174.
Zhang, Y., 2015. A comprehensive survey on particle swarm optimization algorithm and its applications. Mathematical Problems in Engineering, P. 931256.