مشكلة جدولة الموارد - الذكاء الاصطناعي - ثالث ثانوي

الدرس الثاني مشكلة جدولة الموارد رابط الدرس الرقمي www.ien.edu.sa مشكلات الجدولة Scheduling Problems مشكلات الجدولة شائعة في مجال التحسين؛ لأنها تتطلب تخصيص موارد محدودة لمهام متعددة بطريقة تُحسن بعض الدوال الموضوعية، وعادة ما تكون لمشكلات الجدولة قيود إضافية مثل: الحاجة إلى تنفيذ المهام بترتيب معيّن أو إنجازها في الموعد النهائي المحدد ، وهذه المشكلات جوهرية في العديد من المجالات المختلفة بما فيها التصنيع والنقل والرعاية الصحية وإدارة المشاريع. ستتعمق في هذا الدرس في خوارزميات التحسين عن طريق إدخال تقنيات إضافية لحلّ جدولة المشكلات. جدول 5.1 تطبيقات من مجالات مختلفة بحاجة إلى حلول الجدولة جدولة المشاريع تخطيط الإنتاج جدولة خطوط الطيران تخصيص الموارد والمهام لأنشطة المشروع؛ لتقليل مدة المشروع وتكاليفه. تحديد خطة الإنتاج المثلى؛ لتلبية الطلب مع تقليل المخزون والتكاليف. جدولة إقلاع الطائرات وفترات عمل الطاقم؛ لتحسين جداول الرحلات مع تقليل التأخير والتكاليف. جدولة مركز الاتصالات تخصيص فترات عمل للموظفين؛ لضمان التغطية المناسبة لفترات العمل مع تقليل التكاليف والالتزام باتفاقيات مستوى الخدمة. جدولة الإنتاج حسب الطلب تخصيص الموارد في التصنيع؛ لتقليل زمن الإنتاج والتكاليف. جدولة وسائل الإعلام جدولة الممرضات جدولة توقيت الإعلانات على التلفاز أو الإذاعة لزيادة الوصول إلى الجمهور والإيرادات مع الالتزام بقيود الميزانية. تخصيص فترات عمل للممرضات في المستشفيات؛ لضمان التغطية الكافية خلال فترات العمل مع تقليل تكاليف العمالة. Task ect ID: 01234 Resource Project View Task name Week 01 Progress Week 02 Week 03 Week 04 Week 05 MTWTFMTWTFMTWTFMTWTFMTWT Week 06 FMTWTFMTWT Week 07 FM Project initiating 100% Create Project Charter 100% GO/NO GO 100% Project Planning 78% WBS 100% Resources 80% Schedule 80% Costs 75% Planning finished 0% 0001 شكل 5.3: مُخطّط قانت يبين جدول مشروع 267 وزارة التعليم Ministry of Education 2024-1446

268 في هذا الدرس ستستخدم مشكلة التباطؤ الموزون للآلة الواحدة (Single-Machine Weighted Tardiness - SMWT ) كمثال عملي لتوضيح كيف يُمكن لخوارزميات التحسين أن تحلّ مشكلات الجدولة. مشكلة التباطؤ الموزون للآلة الواحدة Single-Machine Weighted Tardiness (SMWT) Problem و لک لک لتوضيح هذه المشكلة سنفترض أن مصنعًا يرغب في جدولة مهام إنتاج عدة سلع على آلة واحدة، على النحو التالي: • كل مهمة لها وقت معالجة محدد، وموعد محدد لابد أن تكتمل فيه. كل مهمة مرتبطة بوزن يمثل أهميتها . إذا كان من المستحيل إنجاز كل المهام في الموعد النهائي، فسيكون عدم الالتزام بإنجاز المهام ذات الوزن الصغير في الموعد النهائي أقل تكلفة من عدم الالتزام بإنجاز المهام ذات الوزن الكبير في الموعد النهائي. الهدف الهدف (Goal) من جدولة المهام بطريقة محدَّدة هو تقليل المجموع الموزون للتأخير ( التباطؤ) لكل مُهمَّة ، وهكذا فإن مجموع التباطؤ الموزون يكون بمثابة الدالة الموضوعية لخوارزميات التحسين المصممة لحلّ هذه المشكلة. حساب التأخير يُحسب التأخير (Lateness) في أداء المُهمَّة على أساس الفرق بين زمن إنجازها والموعد المحدد لتسليمها، ثم تُستخدم أوزان المهام كعوامل ضرب Multipliers) لإكمال المجموع الموزون النهائي. على سبيل المثال: افترض أن هناك جدولا به ثلاث مهام هي: م1 وم 2 وم 3 ، وأوزان هذه المهام هي: 2 و 1 و 2 على الترتيب. وفقًا لهذا الجدول، ستنجز المُهِمَّة رقم 1 في الموعد المحدد، وسيتأخر إنجاز المهمة رقم 2 ثلاث ساعات عن موعد تسليمها ، أما المهمَّة رقم 3 فسيتأخر إنجازها ساعة واحدة عن موعد تسليمها ، ويعني ذلك أن مجموع التباطؤ الموزون يساوي 5=2×1+1×3. تأخير ساعة. تأخير ثلاث ساعات. 5 المهمة 1 15 10 20 المهمة 3 المهمة 2 - شكل 5.4 رسم توضيحي لتسلسل المهام المهمة الموعد المحدد لإنجازها موعد تسليمها م1 م2 م3 14 20 17 التباطؤ الموزون التأخير 0 0 11 3 3 23 2 1 18 شكل 5.5 حساب التباطؤ الموزون 23 1 توجد صعوبة في حلّ مشكلة التباطؤ الموزون للآلة الواحدة؛ لأن تعقدها يتزايد تُستخدم خوارزميات التحسين تزايدًا أُسِّيًا مع عدد المهام، مما يجعل إيجاد أفضل حلّ ممكن لأحجام المدخلات للحصول على حلول شبه الكبيرة مكلفا للغاية وعادة ما يكون مستحيلًا. مثالية لمشكلة محددة في مدة زمنية معقولة. وزارة التعليم Ministry of Education 2024-1446

269 وزارة التعليم Ministry of Education 2024-1446 و مشكلة جدولة الإنتاج حسب الطلب Job Shop Scheduling (JSS) Problem مشكلة جدولة الإنتاج حسب الطلب (JSS) هي مشكلة اعتيادية أخرى في الجدولة حظيت بدراسات موسعة في مجال التحسين، وتتضمن جدولة مجموعة من المهام على عدة آلات، حيث يجب معالجة كل مُهمَّة بترتيب ووقت معينان لكل آلة بالنسبة للمهام الأخرى. الهدف تقليل زمن الإنجاز الكلي (فترة التصنيع لجميع المهام. متغيرات المشكلة المتغيرات الأخرى من هذه المشكلة تفرض عدة قيود إضافية مثل: و وجوب الالتزام بتاريخ إصدار كل مُهمَّة؛ حيث إن لكل مهمة تاريخها الخاص ولا يمكن البدء بها قبل ذلك التاريخ، بالإضافة إلى مراعاة الموعد النهائي. وجوب جدولة بعض المهام قبل المهام الأخرى؛ بسبب ضوابط الأسبقية بينها. وجوب إخضاع كل آلة للصيانة الدورية وفقًا لضوابط جدول الصيانة، حيث لا يمكن للآلات تأدية المهام أثناء الصيانة، كما لا يمكن أن تتوقف المهمَّة بمجرد بدئها . لا بد أن تمر كل آلة بفترة توقف عن الإنتاج بعد إكمال المهمَّة، وقد يكون طول هذه الفترة ثابتًا، وقد يتفاوت من آلة إلى أخرى، ومن الممكن أن يعتمد على الوقت الذي استغرقته الآلة في إكمال المهمَّة السابقة. ما ورد أعلاه ليس سوى مجموعة فرعية من القيود المعقدة والمتعددة، ومن متغيّرات المشكلة الموجودة في مشكلات الجدولة التي نواجها في واقع الحياة، حيث أن لكل متغيّر خصائصه وتطبيقاته العملية الفريدة، وقد تكون خوارزميات التحسين المختلفة أكثر ملاءمة لحلّ كل متغيّر من متغيرات المشكلة. استخدام البايثون والتحسين لحلّ مشكلة التباطؤ الموزون للآلة الواحدة Using Python and Optimization to Solve the SMWT Problem يُمكن استخدام المقطع البرمجي التالي لإنشاء نُسَخ عشوائية لمشكلة التباطؤ الموزون للآلة الواحدة (SMWT): import random # creates an instance of the Single-Machine Weighted Tardiness problem. def create_problem_instance(job_num, # number of jobs to create duration_range, #job duration range deadline_range, # deadline range weight_range) : # importance weight range # generates a random duration, deadline, and weight for each job durations = [random.randint(*duration_range) for i in range(job_num)] deadlines = [random.randint(*deadline_range) for i in range(job_num) ] weights = [random.randint( *weight_range) for i in range( job_num)] # returns the problem instance as a dictionary return {'durations':durations, 'deadlines':deadlines, 'weights':weights}

وزارة التعليم Ministry of Education 2024-1446 تُستخدم الدالة (random.randint(x,y لتوليد عدد صحيح عشوائي بين x و y ، وهناك طريقة مختلفة لاستخدام هذه الدالة تتمثل في توفير قائمة [x] أو مجموعة (, ) ، وفي هذه الحالة لا بد من كتابة الرمز * قبل القائمة كما هو موضح في الدالة السابقة، على سبيل المثال: for i in range(5): # prints 5 random integers between 1 and 10 print(random.randint(*[1, 10])) 6 5 5 10 1 يستخدم المقطع البرمجي التالي دالة ( ) create_problem_instance لتوليد نسخة لمشكلة يتوفّر فيها ما يلي: • تشتمل كلّ نسخة على عشرة مهام. و لک يمكن لكل مُهمَّة أن تستمر ما بين 5 وحدات زمنية و20 وحدة زمنية، وسيتم افتراض أن الساعة هي الوحدة الزمنية المستخدمة فيما تبقى من هذا الدرس كل مُهِمَّة لها موعد نهائي يتراوح ما بين 5 ساعات و 50 ساعة ، وتبدأ ساعة الموعد النهائي من لحظة بدء المهِمَّة الأولى في استخدام الآلة، على سبيل المثال إذا كان الموعد النهائي مُهِمَّة ما يساوي عشر ساعات، فهذا يعني أنه بد من إكمال المهمَّة في غضون عشر ساعات من بداية المهمَّة الأولى في الجدول. وزن كل مهمة هو عدد صحيح يتراوح بين 1 و3 . لا و و نطاق مدة و لل المهمة. عدد المهام المراد إنشاؤها. نطاق الموعد النهائي. مدى أهمية الوزن. create_problem_instance(10, [5, 20], [5, 50], [1, 3]) {'durations': [18, 17, 17, 6, 9, 6, 20, 12, 9, 19], 'deadlines': [39, 31, 6, 42, 48, 10, 39, 16, 34, 35], 'weights': [2, 2, 3, 2, 1, 3, 2, 1, 3, 1]} يمكن استخدام الدالة التالية لتقييم جودة أي جدول أنتجته إحدى الخوارزميات لنسخة مشكلة محددة، حيث تقبل الدالة نسخة المشكلة وجدولاً لمهامها ، ثم تمر على كل المهام بترتيب جدولتها نفسه حتى تحسب أزمنة إنجازها ومجموع التباطؤ الموزون لكامل الجدول، ويُحسب هذا التباطؤ بحساب تباطؤ كل مُهمَّة ( مع مراعاة الموعد النهائي لها ) وضربه في وزن المهمة وإضافة الناتج إلى المجموع: #computes the total weighted tardiness of a given schedule for a given problem instance def compute_schedule_tardiness (problem, schedule): # gets the information for this problem durations, weights, deadlines=problem['durations'], problem['weights'], problem['deadlines'] job_num = len(schedule) # gets the number of jobs finish_times = [0] * job_num # stores the finish time for each job schedule tardiness = 0 #initializes the weighted tardiness of the overall schedule to 0 for pos in range(job_num): #goes over the jobs in scheduled order 270

271 job_id=schedule[pos] # schedule[pos] is the id in the 'pos' position of the schedule if pos == 0: # if this is the job that was scheduled first (position 0) # the finish time of the job that starts first is equal to its run time finish_times[pos] = durations[job_id] else: # for all jobs except the one that was scheduled first # the finish time is equal to the finish time of the previous time plus the job's run time finish_times[pos] = finish_times[pos-1] + durations[job_id] # computes the weighted tardiness of this job and adds it to the schedule's overall tardiness weights[job_id] * max(finish_times[pos] - schedule_tardiness += deadlines[job_id], 0) return schedule_tardiness,finish_times ستُستخدم الدالة ( )compute_schedule_tardiness لتقييم الجداول، وستكون هذه الدالة بمثابة أداة مفيدة لكل الخوارزميات التي سيتم تقديمها في هذا الدرس لحلّ مشكلة التباطؤ الموزون للآلة الواحدة (SMWT). عدالة التباديل Itertools.Permutations Function تستخدم خوارزمية حلّ القوة المفرطة الدالة ( )itertools.permutations لإنشاء كل الجداول الممكنة (تجميعات المهام) ، ثم تحسب تباطؤ كل جدول ممكن وتستخرج أفضل جدول ( الجدول ذو التباطؤ الكلي الأدنى). تقبل الدالة ( )itertools.permutations عنصرًا واحدًا متكرراً ( مثل : قائمة ) وتُنشئ كل تبديل ممكن لقيم المدخلات، ويوضّح المثال البسيط التالي استخدام دالة ( )permutations ويُظهر التبديلات لكل عناوين المهام المعطاة: job_ids [0,1,2] # the ids of 3 jobs = for schedule in itertools.permutations (job_ids): print(schedule) (0, 1, 2) (0, 2, 1) (1, 0, 2) (1, 2, 0) (2, 0, 1) (2, 1, 0) تُستخدم خوارزميات حلّ القوة المفرطة بشكل أفضل لحلّ المشكلات الصغيرة، فالنسخة الخاصة بمشكلة التباطؤ الموزون للآلة الواحدة ذات عدد N من المهام، لديها عدد !N من الجداول الممكنة، فعندما يكون 5 = N، سيكون الناتج 120 = 5 جدولا، ولكن هذا العدد يتزايد بشكل كبير عندما يكون 10 = N إلى 3,628,800 = 10 ، وعندما يكون 11 = N إلى 39,916,800 = !11. وزارة التعليم Ministry of Education 2024-1446 خوارزمية حلّ القوة المفرطة Brute-Force Solver لقد تعلمت في الدرس السابق طريقة استخدام خوارزمية حلّ القوة المفرطة في مشكلة تكوين فريق، وعلى الرغم من أن خوارزمية الحلّ هذه أظهرت بطئًا شديدًا في المشكلات الأكبر حجمًا ، إلا أن قدرتها على إيجاد الحل الأمثل (أفضل حلّ ممكن لنسخ المشكلة ذات الحجم الصغير كانت مفيدة في تقييم جودة الحلول المنتجة بواسطة خوارزميات التحسين الأسرع التي لا تضمن إيجاد الحل الأمثل. وبالمثل: يُمكن استخدام خوارزمية حلّ القوة المفرطة التالية لحلّ مشكلة التباطؤ الموزون للآلة الواحدة (SMWT).

import itertools def brute force_solver (problem): #gets the information for this problem durations, weights, deadlines problem['durations'], problem['weights'], problem['deadlines'] job_num = len(durations) # number of jobs # Generates all possible schedules all_schedules = itertools.permutations (range(job_num)) # Initializes the best solution and its total weighted tardiness best_schedule = None #initialized to None #'inf' stands for 'infnity'. Python will evaluate all numbers as smaller than this value. best_tardiness = float('inf') #stores the finish time of each job in the best schedule best_finish_times = None # initalized to None for schedule in all_schedules: # for every possible schedule #evalutes the schedule tardiness, finish_times-compute_schedule_tardiness(problem, schedule) if tardiness < best_tardiness: # this schedule is better than the best so far best tardiness = tardiness best_schedule = schedule best_finish_times = finish_times # returns the results as a dictionary return عدد المهام المراد إنشاؤها. وزارة التعليم Ministry of Education 2024-1446 {'schedule': best_schedule, 'tardiness': best_tardiness, 'finish_times': best_finish_times} Я خوارزمية الحلّ تعطي الجدول الأفضل، وزمن التباطؤ، وزمن إنجاز كل مُهِمَّة ثلاث مهام، معطاة في هذا الجدول. على سبيل المثال، إذا كان الجدول يحوي نطاق الموعد وكانت أوقات إنجاز جميع المهام تساوي [100]، فذلك يعني أن المهمَّة التي بدأت أولا انتهت بعد 10 ساعات والمهمَّة الثانية انتهت بعد ذلك بأربع ساعات، والمُهمَّة الأخيرة انتهت بعد ست ساعات من اكتمال المهمَّة الثانية. النهائي. sample_problem = create_problem_instance(5, [5, 20], [5, 30], [1, 3]) brute_force_solver(sample_problem) {'schedule': (0, 2, 1, 3, 4), 'tardiness': 164, 'finish_times': [5, 11, 21, 36, 51]} مدى أهمية الوزن. نطاق مدة المهمة. 272

خوارزمية الحلّ الاستدلالية الجشعة Greedy Heuristic Solver تستخدم خوارزمية الحلّ الجشعة أسلوبًا استدلاليًا بسيطًا لفرز المهام واتخاذ قرار الترتيب الذي يجب جدولتها وفقًا له، ثم تُرتب المهام لحساب زمن إكمال كل مُهِمَّة ومجموع التباطؤ الموزون لكامل الجدول، وفي هذا المثال الخاص تُظهر خوارزمية الحلّ الجشعة نوع المخرجات نفسه الذي أظهرته خوارزمية حلّ القوة المفرطة. تقبل خوارزمية الحلّ الجشعة مُعامِلان هما: نسخة المشكلة المراد حلّها، ودالة الاستدلال التي ستستخدم ( معيار فرز المهام)، مما يسمح للمستخدم بأن يُطبّق أي دالة استدلال يختارها كدالة البايثون، ثم يمرره إلى خوارزمية الحلّ الجشعة باعتباره معاملا. تُطبق الدالة التالية خوارزمية تحسين تستخدم دالةً استدلاليةً جشعةً لحل المشكلة: def greedy_solver(problem, heuristic): # gets the information for this problem durations, weights, deadlines = problem['durations'], problem['weights'], problem['deadlines'] job_num = len(durations)#gets the number of jobs # Creates a list of job indices sorted by their deadline in non-decreasing order = schedule sorted (range(job_num), key = lambda j: heuristic(j, problem)) # evaluates the schedule tardiness, finish_times = compute_schedule_tardiness(problem, schedule) # returns the results as a dictionary return {'schedule': schedule, 'tardiness': tardiness, 'finish_times':finish_times} يُستخدم في هذا المثال دالة استدلالية جشعة لتحديد المهمة التالية التي تحتاج إلى جدولة وهي المهمة التي لها أقرب موعد نهائي يستخدم بناء الجملة lambda مع دالة البايثون ( ) sorted عندما يتمثل الهدف في فرز قائمة عناصر بناءً على قيمة يتم حسابها بطريقة منفصلة لكل عنصر. تُظهر الدالة التالية الموعد النهائي لمهمَّة محدَّدة في نسخة مشكلة معطاة: # returns the deadline of a given job def deadline_heuristic(job, problem): # accesses the deadlines for this problem and returns the deadline for the job return problem['deadlines'][job] تمرير دالة deadline_heuristic كمعامل إلى خوارزمية الحلّ الجشعة (greedy_solver) يعني أن الخوارزمية ستجدول (تفرز) المهام وفق ترتيب تصاعدي حسب الموعد النهائي، مما يعني أن المهام التي لها أقرب موعد نهائي و ستجدول أولًا. 273 وزارة التعليم Ministry of Education 2024-1446

وزارة التعليم Ministry of Education 2024-1446 greedy_sol greedy_sol greedy_solver(sample_problem, deadline_heuristic) {'schedule': [3, 1, 4, 0, 2], 'tardiness': 124, 'finish_times': [15, 26, 32, 48, 57]} تُطبق الدالة التالية استدلالًا بديلًا يأخذ في اعتباره أوزان المهام عند اتخاذ قرار ترتيبها في الجدول: # returns the weighted deadline of a given job def weighted_deadline_heuristic(job,problem): # accesses the deadlines for this problem and returns the deadline for the job return problem[ 'deadlines'][job] / problem[ 'weights'][job] weighted_greedy_sol-greedy_solver(sample_problem, weighted_deadline_heuristic) weighted_greedy_sol {'schedule': [3, 2, 1, 4, 0], 'tardiness': 89, 'finish_times': [15, 24, 35, 41, 57]} البحث المحلي Local Search (Local Search) على الرغم من أن خوارزمية الحلّ الجشعة أسرع بكثير من خوارزمية القوة المفرطة، إلا أنها تميل إلى إنتاج حلول ذات جودة أقل بزمن تباطؤ أعلى، ويُعدُّ البحث المحلّي البحث المحلّي طريقة لتحسين حلّ تم حسابه بواسطة الخوارزمية الجشعة أو بأي طريقة أخرى. هو طريقة تحسين استدلالية في البحث المحلّي، يُعدل الحلّ الذي تم التوصل إليه في البداية بشكل متكرر تركّز على اكتشاف حلول مجاورة من خلال فحص الحلول المجاورة التي وُجدت عن طريق إجراء تعديلات بسيطة لحل معين بهدف تحسينه. على الحلّ الحالي. بالنسبة للعديد من مشكلات التحسين، فهناك طريقة شائعة لتعديل الحلّ تتمثل في تبديل العناصر بشكل متكرر. على سبيل المثال، في مشكلة تكوين الفريق التي تم توضيحها في الدرس السابق، سيحاول أسلوب البحث المحلّي إنشاء فريق أفضل وذلك من خلال تبديل أعضاء الفريق بالعمال الذين لا يُعدّون حاليا جزءًا من الفريق. أنشأت خوارزمية الحلّ الاستدلالية الجشعة (Greedy Heuristic Solver حلا للمشكلة خطوة خطوة حتى حصلت في النهاية على حلّ كامل ونهائي ، وعلى العكس من ذلك تبدأ طرائق البحث المحلية بحلّ كامل قد يكون ذا جودة متوسطة أو سيئة، وتعمل بطريقة تكرارية لتحسين جودته . في كل خطوة يكون هناك تغيير بسيط على الحلّ الحالي، وتُقيَّم جودة الحلّ الناتج ( يسمّى الحل المجاور) ، وإذا كان يتمتع بجودة أفضل، فإنه يستبدل الحلّ الحالي ويستمر في البحث، وإذا لم يكن كذلك، يتم تجاهل الحل المجاور وتتكرر العملية لتوليد حل مجاور آخر ، ثم ينتهي البحث عندما يتعذر العثور على حلّ مُجاور آخر يتمتع بجودة أفضل من الحلّ الحالي، ويتم تحديد أفضل حل تم و العثور عليه. 274

275 وزارة التعليم Ministry of Education 2024-1446 دالة خوارزمية حلّ البحث المحلّي Local_search_solver( ) Function تطبق الدالة التالية ()local_search_solver خوارزمية حلّ البحث المحلّي القائم على المبادلة لمشكلة التباطؤ الموزون للآلة الواحدة (SWT) ، حيث تقبل هذه الدالة أربعة معاملات وهي: نسخة المشكلة. خوارزمية استدلالية جشعة تستخدمها دالة ( )greedy_solver لحساب حلّ و ひろ دالة swap_selector المستخدمة لانتقاء مهمتين ستتبادلان موقعيهما في الجدول. على سبيل المثال، إذا كان الحلّ الحالي للمشكلة المكونة من أربع مهام هو 11 ، ، ، ، وقررت دالة swap_selector أن يحدث مبادلة بين المُهمَّة الأولى والمهمَّة الأخيرة، سيكون الحل المرشح هو [0 ،3 ،2 ،1]. • max_iterations عدد صحيح يُحدِّد عدد المبادلات التي يجب تجربتها قبل أن تتوصل الخوارزمية للحل الأفضل في حينه. و في كل تكرار، تنتقي الخوارزمية مهمتين للتبديل بينهما، ثم تُنشئ جدولاً سلوك خوارزميات التحسين القائمة جديدًا تتم فيه هذه المبادلة، وكل شيء في الجدول الجديد بخلاف ذلك على البحث المحلي يتأثر بشكل كبير سيكون مطابقًا للجدول الأصلي. إذا كان للجدول الجديد تباطؤ موزون بالاستراتيجية المستخدمة بطريقة أقل من الجدول الأفضل الذي تم إيجاده حتى الآن، فإن الجدول الجديد يُصبح هو الأفضل بدلًا منه. خوارزمية الحلّ هذه لها نفس مُخرَجات خوارزمية الحلّ الجشعة وخوارزمية حلّ القوة المفرطة. تكرارية لتعديل الحلّ. def local_search_solver(problem, greedy_heuristic, swap_selector, max_ iterations): #gets the information for this problem durations, weights, deadlines=problem[ 'durations'], problem[ 'weights'], problem['deadlines'] job_num = len (durations) # gets the number of jobs # uses the greedy solver to get a first schedule # this schedule will be then iteratively refined through local search greedy_sol = greedy_solver(problem, greedy_heuristic) # the best schedule so far best_schedule, best_tardiness, best_finish_times = greedy_sol['schedule'], greedy_sol['tardiness'], greedy_sol['finish_times'] # local search for i in range(max_iterations): #for each of the given iterations # chooses which two positions to swap pos1, pos2 = swap_selector(best_schedule). new_schedule = best_schedule.copy() # create a copy of the schedule # swaps jobs at positions pos1 and pos2 new_schedule[pos1], new_schedule[pos2] = best_schedule[pos2], best_schedule[pos1]

وزارة التعليم Ministry of Education 2024-1446 # computes the new tardiness after the swap new_tardiness, new_finish_times = compute_schedule_tardiness(problem, new_schedule) # if the new schedule is better than the best one so far if new_tardiness < best_tardiness: # the new_schedule becomes the best one best_schedule = new_schedule best_tardiness = new_tardiness best_finish_times = new_finish_times # returns the best solution return {'schedule':best_schedule, 'tardiness':best_tardiness, 'finish_times' :best_finish_times} جيران الحل في هذا المثال كلها حلول يتم الحصول عليها عن طريق انتقاء مهمتين داخل الحل ومبادلة موقعيهما في الجدول. تُطبق الدالة التالية مبادلة عشوائية بانتقاء مُهمَّتين عشوائيتين في الجدول المعطى الذي يستوجب تبديل مكانيهما: def random_swap(schedule): job_num = len(schedule) # gets the number of scheduled jobs pos1 = random.randint(0, job_num pos2 = pos1 - 1) # samples a random position while pos2 == pos1: #keeps sampling until it finds a position other than pos1 pos2 = random.randint(0, job_num 1) #samples another random position - return pos1, pos2 #returns the two positions that should be swapped تستخدم الدالة التالية استراتيجية مختلفة وذلك باختيارها الدائم مُهِمَّتين عشوائيتين متجاورتين في الجدول لتبادلهما. على سبيل المثال إذا كان الجدول الحالي لنسخة مشكلة مُكوَّنة من أربع مهام هو [2 ،1 ،3 ،0]، فإن المبادلات المرشحة ستكون فقط 0<>3 و3<>1 و1<>2. def adjacent_swap(schedule): one) job_num = len(schedule) # gets the number of scheduled jobs pos1 = random.randint(0, job_num - 2) #samples a random position (excluding the last pos2 = pos1 + 1 # gets the position after the sampled one return pos1, pos2 # returns the two positions that should be swapped 276

277 وزارة التعليم Ministry of Education 2024-1446 يستخدم المقطع البرمجي التالي استراتيجيتي المبادلة مع خوارزمية حلّ البحث المحلّي لحلّ المشكلة التي تم إنشاؤها في بداية هذا الدرس print(local_search_solver(sample_problem, weighted_deadline_heuristic, random_ swap, 1000) print(local_search_solver(sample_problem, weighted_deadline_heuristic, adjacent_swap, 1000)) {'schedule': [3, 4, 12, 1, 0], 'tardiness': 83, 'finish_times': [15, 21, 30, 41, 57]} {'schedule' [3, 4, 2, 1, 0], 'tardiness': 83, 'finish_times': [15, 21, 30, 41, 57]} تُظهر النتائج أفضل جدول [0، 1، 2، 4، 3] لهذا المثال، وإجمالي التباطؤ 83 ، وأزمنة إكمال المهام (ستنتهي المُهمَّة 3 في الوحدة 15 من الزمن، وتنتهي المُهمَّة 4 في الوحدة 21 منه، وهكذا). مقارنة خوارزميات الحل Comparing Solvers يستخدم المقطع البرمجي التالي الدالة ( )create_problem_instance لتوليد مجموعتي بيانات: مجموعة بيانات من 100 نسخة لمشكلة التباطؤ الموزون للآلة الواحدة، وفي كل منها 7 مهام. Я مجموعة بيانات من 100 نسخة لمشكلة التباطؤ الموزون للآلة الواحدة، وفي كل منها 30 مُهمَّة. سيتم استخدام مجموعة البيانات الأولى لمقارنة أداء جميع خوارزميات الحلّ الموضّحة في هذا الدرس: .1. خوارزمية حلّ القوة المفرطة. 2 خوارزمية الحلّ الجشعة المتضمنة على استدلال خاص بالموعد النهائي. 3. خوارزمية الحلّ الجشعة المتضمنة على استدلال خاص بالموعد النهائي الموزون. .4. خوارزمية حلّ البحث المحلّي المتضمنة على مبادلات عشوائية وخوارزمية الحلّ الجشعة ذات استدلال خاص بالموعد النهائي لإيجاد الحل الأولي. 5. خوارزمية حلّ البحث المحلّي المتضمنة على مبادلات عشوائية وخوارزمية الحلّ الجشعة ذات استدلال خاص بالموعد النهائي الموزون. 6. خوارزمية حلّ البحث المحلّي المتضمنة على مبادلات متجاورة وخوارزمية الحلّ الجشعة ذات استدلال خاص بالموعد النهائي. 7. خوارزمية حلّ البحث المحلّي المتضمنة على مبادلات متجاورة وخوارزمية الحلّ الجشعة ذات استدلال خاص بالموعد النهائي الموزون سيتم استخدام مجموعة البيانات الثانية لمقارنة جميع خوارزميات الحلّ باستثناء خوارزمية حلّ القوة المفرطة البطيئة جدا بالنسبة للمشكلات المشتملة على 30 مهمَّة. Я #Dataset 1 problems_7 = [] for i in range(100): problems_7.append(create_problem_instance(7, [5, 20], [5, 50], [1, 3])) #Dataset 2 problems_30 = [] for i in range(100): problems_30.append(create_problem_instance(30, [5,20], [5, 50], [1, 3]))

وزارة التعليم Ministry of Education 2024-1446 دالة المقارنة Compare() Function تستخدم الدالة التالية ( ) Compare كل خوارزميات الحل؛ لحلّ كل المشكلات في مجموعة بيانات معينة، ثم تُظهر متوسط التباطؤ الذي تحققه كل خوارزمية حلّ على كل المشكلات في مجموعة البيانات، وتقبل الدالة كذلك المعامل المنطقي use_brute لتحديد إمكانية استخدام خوارزمية الحلّ بالقوة المفرطة أم لا: Я from collections import defaultdict import numpy def compare(problems, use_brute): # comparison on Dataset 1 # maps each solver to a list of all tardiness values it achieves for the problems in the given dataset results = defaultdict(list) for problem in problems: # for each problem in this datset #uses each of the solvers on this problem if use_brute == True: results['brute-force'].append(brute_force_solver (problem) ['tardiness']) results['greedy-deadline'].append(greedy_solver (problem, deadline_ heuristic) ['tardiness']) results['greedy-weighted_deadline'].append(greedy_ solver(problem, weighted_deadline_heuristic) ['tardiness']) results['ls-random-wdeadline'].append(local_search_solver(problem, weighted_deadline_heuristic, random_swap, 1000) ['tardiness']) results['ls-random-deadline'].append(local_search_solver (problem, deadline heuristic, random_swap, 1000) ['tardiness']) results['ls-adjacent-wdeadline'].append(local_search_solver(problem, weighted_deadline_heuristic, adjacent_swap, 1000)['tardiness']) results['ls-adjacent-deadline'].append(local_search_solver(problem, deadline_heuristic, adjacent_swap, 1000) ['tardiness']) for solver in results: # for each solver # prints the solver's mean tardiness values print(solver, numpy.mean(results [solver])) يُمكن الآن استخدام دالة ( ) compare مع مجموعتي البيانات 7_problems و 30_problems كلتيهما: compare(problems 7, True) brute-force 211.49 greedy-deadline 308.14 greedy-weighted_deadline 255.61 ls-random-wdeadline 212.35 ls-random-deadline 212.43 ls-adjacent-wdeadline 220.62 ls-adjacent-deadline 224.36 compare(problems_30, False) greedy-deadline 10126.18 greedy-weighted_deadline 8527.61 ls-random-wdeadline 6647.73 ls-random-deadline 6650.99 ls-adjacent-wdeadline 6666.47 ls-adjacent-deadline 6664.67 278

279 تمرينات صف استراتيجيتين مختلفتين ( مبادلة، انعكاس، تحويل، إلخ) لأسلوب البحث المحلي لحلّ مشكلة التباطؤ الموزون وزارة التعليم Ministry of Education 2024-1446 للآلة الواحدة. كم عدد الجداول الممكنة (الحلول) لنسخة مشكلة التباطؤ الموزون للآلة الواحدة والتي تشتمل على تسع مهام؟ 1 2

3 أنشئ خوارزمية حلّ بالقوة المفرطة لمشكلة التباطؤ الموزون للآلة الواحدة، من خلال إكمال المقطع البرمجي التالي بحيث تستخدم الدالة القوة المفرطة لإيجاد تبديل الجدولة الأمثل. وزارة التعليم Ministry of Education 2024-1446 def brute force_solver (problem): # gets the information for this problem durations, weights, deadlines-problem['durations'], problem ['weights'], problem['deadlines'] job_num = len( # generates all possible schedules all_schedules = itertools. ) # number of jobs (range(job_num)) # initializes the best solution and its total weighted tardiness best_schedule = # initialized to None # 'inf' stands for 'infnity'. Python will evaluate all numbers as smaller than this value. best tardiness = float(' #stores the finish time of each job in the best schedule best_finish_times= ') # initalized to None for schedule in all_schedules: # for every possible schedule #evalute the schedule tardiness, finish_times-compute_schedule_tardiness(problem, schedule) if tardiness <best_tardiness: # this schedule is better than the best so far best tardiness= best_schedule= best_finish_times= # return the results as a dictionary return {'schedule': best_schedule, 'tardiness': best_tardiness, 'finish_times': best_finish_times} 280

281 أنشئ خوارزمية حلّ البحث المحلّي لمشكلة التباطؤ الموزون للآلة الواحدة من خلال إكمال المقطع البرمجي التالي بحيث تستخدم الدالة البحث المحلّي لإيجاد تبديل الجدولة الأمثل. وزارة التعليم Ministry of Education 2024-1446 def local_search_solver(problem, greedy_heuristic, swap_selector, max_ iterations): # gets the information for this problem durations, weights, deadlines=problem['durations'], problem['weights'], problem['deadlines'] job_num = len( )# gets the number of jobs # uses the greedy solver to get a first schedule. # this schedule will be then iteratively refined through local search greedy_sol = (problem, greedy_heuristic) # remembers the best schedule so far best_schedule, best_tardiness, best_finish_times=greedy_ sol['schedule'], greedy_sol['tardiness'], greedy_sol['finish_times'] # local search for i in range( ): # for each of the given iterations # chooses which two positions to swap schedule pos1, pos2= (best_schedule) new_schedule = best_schedule. () # creates a copy of the #swaps jobs at positions pos1 and pos2 new_schedule[pos1], new_schedule[pos2] = best_schedule[pos2], best_ schedule[pos1] # computes the new tardiness after the swap new_tardiness, new_finish_times = compute_schedule_tardiness (problem, new_schedule) # if the new schedule is better than the best one so far if new_tardiness < best_tardiness: # the new_schedule becomes the best one best_schedule = best tardiness = best_finish_times= # returns the best solution return {'schedule': best_schedule, 'tardiness': best_tardiness, 'finish_times': best_finish_times}

5 صف طريقة عمل البحث المحلي. اكتب ملاحظاتك عن نتائج خوارزميات الحلّ الجشعة مقارنة بخوارزميات حلّ البحث المحلّي في مشكلة تشتمل على ثلاثين مُهمَّة. من وجهة نظرك، لماذا لم تُستخدم خوارزمية حلّ القوة المفرطة في هذه المشكلة المكونة من ثلاثين مهمة؟ وزارة التعليم Ministry of Education 2024-1446 6 282