Fulltext

Nurse Scheduling Problem Using Hybrid Simulated Annealing Algorithm

جدولة عمل الممرضات باستعمال خوارزمية محاكاة التلدين المهجنة

محمد صادق عبد الرزاق --- علي ابراهيم هندي

journal of Economics And Administrative Sciences مجلة العلوم الاقتصادية والإدارية
ISSN: 2227 703X / 2518 5764 Year: 2018 Volume: 24 Issue: 107 Pages: 572-589
Publisher: Baghdad University جامعة بغداد

Abstract

Nurse scheduling problem is one of combinatorial optimization problems and it is one of NP-Hard problems which is difficult to be solved as optimal solution. In this paper, we had created an proposed algorithm which it is hybrid simulated annealing algorithm to solve nurse scheduling problem, developed the simulated annealing algorithm and Genetic algorithm. We can note that the proposed algorithm (Hybrid simulated Annealing Algorithm(GS-h)) is the best method among other methods which it is used in this paper because it satisfied minimum average of the total cost and maximum number of Solved , Best and Optimal problems. So we can note that the ratios of the optimal solution are 77% for the proposed algorithm(GS-h), 28.75% for Simulated annealing algorithm (SA), 35.7% for Improved Simulated annealing (SA*), 26.25% for Genetic algorithm ( GA) and 45.6% for Improved Genetic algorithm for all problems (2000 problems).

الملخصتعد مسألة جدولة عمل الممرضات (NSP) من مسائل الأمثلية المركبة والتي تنتمي بدرجة صعوبتها الى مسائل الامثلية الصعبة NP-Hard التي يصعب حلها بشكل امثل, اذ تقوم المسألة بإيجاد جدول زمني مناسب للممرضين وتوزيعهم على المناوبات وايام العُطل (الاستراحة) بشكل يضمن العدالة في فريق العمل الواحد وبأقل التكاليف ويتم ذلك بتحقيق انواع مختلفة من القيود الصعبة والبسيطة . فقد تم في هذا البحث انشاء خوارزمية مهجنة وهي خوارزمية محاكاة التلدين المهجنة (GS-h)لحل مسألة جدولة عمل الممرضات (NSP), حيث اقترحنا اولاً تحسين خوارزمية محاكاة التلدين وتحسين الخوارزمية الجينية ايضاً من خلال الاستفادة من مزاياهما ومحاولة التغلب على نقاط الضعف الموجودة فيهما وبالتالي دمج التحسين لهاتين الخوارزميتين معاً حيث يتم ذلك من خلال دمج الافكار التطويرية للخوارزميتين, حيث أوضحت النتائج التجريبية مدى تفوق الخوارزمية المهجنة (GS-h) على الخوارزميات الاخر,حيث إن نسب الحصول على الحل الامثل لجميع المسائل البالغ عددها (2000) مسألة هي (77%) بأستعمال خوارزمية محاكاة التلدين المهجنة (GS-h) وهي النسبة الاعلى في الحصول على الحلول المثلى من بين جميع الخوارزميات التي تم تطبيقها في هذا البحث, أما خوارزمية محاكاة التلدين التقليدية (SA) فقد حصلت على نسبة (28.75%) بينما نالت خوارزمية محاكاة التلدين المحسنة (SA*) على نسبة ((35.7%, أما الخوارزمية الجينية الاعتيادية فقد نالت على نسبة (26.25%) بينما حصلت الخوارزمية الجينية المحسنة (GA*) فقد نالت على نسبة (45.6%) .

Keywords

/ Nurse scheduling problem --- Simulated annealing algorithm --- Genetic algorithm. --- جدولة عمل الممرضات --- خوارزمية محاكاة التلدين --- الخوارزمية الجينية .