خوارزميات حل مشكلة التباطؤ الموزون للآلة الواحدة - كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 - المملكة العربية السعودية

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 schedule_tardiness += weights[job_id] * max(finish_times[pos] - deadlines[job_id], 0) return schedule_tardiness, finish_times

ستُستخدم الدالة ()compute_schedule_tardiness لتقييم الجداول، وستكون هذه الدالة بمثابة أداة مفيدة لكل الخوارزميات التي سيتم تقديمها في هذا الدرس لحل مشكلة التباطؤ الموزون للآلة الواحدة (SMWT).

دالة التباديل fx Itertools.Permutations() Function

تستخدم خوارزمية حل القوة المفرطة الدالة ()itertools.permutations لإنشاء كل الجداول الممكنة (تجميعات المهام). ثم تحسب تباطؤ كل جدول ممكن وتستخرج أفضل جدول (الجدول ذو التباطؤ الكلي الأدنى). تقبل الدالة ()itertools.permutations عنصرًا واحدًا متكررًا (مثل: قائمة) وتُنشئ كل تبديل ممكن لقيم المدخلات. ويوضح المثال البسيط التالي استخدام دالة ()permutations ويظهر التبديلات لكل عناوين المهام المعطاة:

تُستخدم خوارزميات حل القوة المفرطة بشكل أفضل لحل المشكلات الصغيرة. فالنسخة الخاصة بمشكلة التباطؤ الموزون للآلة الواحدة ذات عدد N من المهام، لديها عدد N! من الجداول الممكنة، فعندما يكون 5 = N، سيكون الناتج 120 = !5 جدولاً، ولكن هذا العدد يتزايد بشكل كبير عندما يكون 10 = N إلى !10 = 3,628,800، وعندما يكون 11 = N إلى !11 = 39,916,800.

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)

خوارزمية حل القوة المفرطة Brute-Force Solver

لقد تعلمت في الدرس السابق طريقة استخدام خوارزمية حل القوة المفرطة في مشكلة تكوين فريق. وعلى الرغم من أن خوارزمية الحل هذه أظهرت بطئًا شديدًا في المشكلات الأكبر حجمًا، إلا أن قدرتها على إيجاد الحل الأمثل (أفضل حل ممكن) لنسخ المشكلة ذات الحجم الصغير كانت مفيدة في تقييم جودة الحلول المنتجة بواسطة خوارزميات التحسين الأسرع التي لا تتضمن إيجاد الحل الأمثل. وبالمثل، يمكن استخدام خوارزمية حل القوة الموزون للآلة الواحدة (SMWT).

وزارة التعليم Ministry of Education 2023 - 1447 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 schedule_tardiness += weights[job_id] * max(finish_times[pos] - deadlines[job_id], 0) return schedule_tardiness, finish_timesستُستخدم الدالة ()compute_schedule_tardiness لتقييم الجداول، وستكون هذه الدالة بمثابة أداة مفيدة لكل الخوارزميات التي سيتم تقديمها في هذا الدرس لحل مشكلة التباطؤ الموزون للآلة الواحدة (SMWT).--- SECTION: دالة التباديل fx Itertools.Permutations() Function --- دالة التباديل fx Itertools.Permutations() Functionتستخدم خوارزمية حل القوة المفرطة الدالة ()itertools.permutations لإنشاء كل الجداول الممكنة (تجميعات المهام). ثم تحسب تباطؤ كل جدول ممكن وتستخرج أفضل جدول (الجدول ذو التباطؤ الكلي الأدنى). تقبل الدالة ()itertools.permutations عنصرًا واحدًا متكررًا (مثل: قائمة) وتُنشئ كل تبديل ممكن لقيم المدخلات. ويوضح المثال البسيط التالي استخدام دالة ()permutations ويظهر التبديلات لكل عناوين المهام المعطاة:تُستخدم خوارزميات حل القوة المفرطة بشكل أفضل لحل المشكلات الصغيرة. فالنسخة الخاصة بمشكلة التباطؤ الموزون للآلة الواحدة ذات عدد N من المهام، لديها عدد N! من الجداول الممكنة، فعندما يكون 5 = N، سيكون الناتج 120 = !5 جدولاً، ولكن هذا العدد يتزايد بشكل كبير عندما يكون 10 = N إلى !10 = 3,628,800، وعندما يكون 11 = N إلى !11 = 39,916,800.--- SECTION: Example Code for Permutations --- job_ids = [0,1,2] # the ids of 3 jobs for schedule in itertools.permutations(job_ids): print(schedule)--- SECTION: Output of Permutations Example --- (0, 1, 2) (0, 2, 1) (1, 0, 2) (1, 2, 0) (2, 0, 1) (2, 1, 0)--- SECTION: خوارزمية حل القوة المفرطة Brute-Force Solver --- خوارزمية حل القوة المفرطة Brute-Force Solverلقد تعلمت في الدرس السابق طريقة استخدام خوارزمية حل القوة المفرطة في مشكلة تكوين فريق. وعلى الرغم من أن خوارزمية الحل هذه أظهرت بطئًا شديدًا في المشكلات الأكبر حجمًا، إلا أن قدرتها على إيجاد الحل الأمثل (أفضل حل ممكن) لنسخ المشكلة ذات الحجم الصغير كانت مفيدة في تقييم جودة الحلول المنتجة بواسطة خوارزميات التحسين الأسرع التي لا تتضمن إيجاد الحل الأمثل. وبالمثل، يمكن استخدام خوارزمية حل القوة الموزون للآلة الواحدة (SMWT).2023 - 1447--- VISUAL CONTEXT --- **FIGURE**: ملاحظة حول خوارزميات القوة المفرطة Description: A pink highlighted box explaining the computational complexity of brute-force algorithms for the Weighted Tardiness problem, specifically how the number of possible schedules (N!) grows rapidly with N. It provides examples for N=5, N=10, and N=11. Key Values: N=5 -> 5! = 120 schedules, N=10 -> 10! = 3,628,800 schedules, N=11 -> 11! = 39,916,800 schedules Context: Illustrates why brute-force is only suitable for small problems due to factorial growth in complexity, making it impractical for larger problem sizes.