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

في هذا الدرس سنستخدم مشكلة التباطؤ الموزون للآلة الواحدة (Single-Machine Weighted Tardiness – SMWT) كمثال عملي لتوضيح كيف يمكن لخوارزميات التحسين أن تحل مشكلات الجدولة.

Single-Machine Weighted Tardiness (SMWT) Problem

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

الهدف

الهدف (Goal) من جدولة المهام بطريقة محددة هو تقليل المجموع الموزون للتأخير (التباطؤ) لكل مهمة، وهكذا فإن مجموع التباطؤ الموزون يكون بمثابة الدالة الموضوعية لخوارزميات التحسين المصممة لحل هذه المشكلة.

حساب التأخير

يُحسب التأخير (Lateness) في أداء المهمة على أساس الفرق بين زمن إنجازها والموعد المحدد لتسليمها. ثم تُستخدم أوزان المهام كعوامل ضرب (Multipliers) لإكمال المجموع الموزون النهائي. على سبيل المثال: افترض أن هناك جدولاً به ثلاث مهام هي 1م و 2م و 3م، وأوزان هذه المهام هي: 1 و 2 و 3 على الترتيب. ووفقًا لهذا الجدول، ستنجز المهمة رقم 1 في الموعد المحدد، وسيتأخر إنجاز المهمة رقم 2 ثلاث ساعات عن موعد تسليمها، أما المهمة رقم 3 فسيُتأخر إنجازها ساعة واحدة عن موعد تسليمها، ويعني ذلك أن مجموع التباطؤ الموزون يساوي 3×1+1×2=5.

تُستخدم خوارزميات التحسين للحصول على حلول شبه مثالية لمشكلة محددة في مدة زمنية معقولة.

توجد صعوبة في حل مشكلة التباطؤ الموزون للآلة الواحدة؛ لأن تعقيدها يتزايد تزايدًا أسيًا مع عدد المهام، مما يجعل إيجاد أفضل حل ممكن لأحجام المدخلات الكبيرة مكلفًا للغاية وعادة ما يكون مستحيلاً.

268

وزارة التعليم 2023 - 1447

في هذا الدرس سنستخدم مشكلة التباطؤ الموزون للآلة الواحدة (Single-Machine Weighted Tardiness – SMWT) كمثال عملي لتوضيح كيف يمكن لخوارزميات التحسين أن تحل مشكلات الجدولة.--- SECTION: مشكلة التباطؤ الموزون للآلة الواحدة --- Single-Machine Weighted Tardiness (SMWT) Problemلتوضيح هذه المشكلة، سنفترض أن مصنعًا يرغب في جدولة مهام إنتاج عدة سلع على آلة واحدة، على النحو التالي: • كل مهمة لها وقت معالجة محدد، وموعد محدد لابد أن تكتمل فيه. • كل مهمة مرتبطة بوزن يمثل أهميتها. إذا كان من المستحيل إنجاز كل المهام في الموعد النهائي، فسيكون عدم الالتزام بإنجاز المهام ذات الوزن الصغير في الموعد النهائي أقل تكلفة من عدم الالتزام بإنجاز المهام ذات الوزن الكبير في الموعد النهائي.--- SECTION: الهدف --- الهدف الهدف (Goal) من جدولة المهام بطريقة محددة هو تقليل المجموع الموزون للتأخير (التباطؤ) لكل مهمة، وهكذا فإن مجموع التباطؤ الموزون يكون بمثابة الدالة الموضوعية لخوارزميات التحسين المصممة لحل هذه المشكلة.--- SECTION: حساب التأخير --- حساب التأخير يُحسب التأخير (Lateness) في أداء المهمة على أساس الفرق بين زمن إنجازها والموعد المحدد لتسليمها. ثم تُستخدم أوزان المهام كعوامل ضرب (Multipliers) لإكمال المجموع الموزون النهائي. على سبيل المثال: افترض أن هناك جدولاً به ثلاث مهام هي 1م و 2م و 3م، وأوزان هذه المهام هي: 1 و 2 و 3 على الترتيب. ووفقًا لهذا الجدول، ستنجز المهمة رقم 1 في الموعد المحدد، وسيتأخر إنجاز المهمة رقم 2 ثلاث ساعات عن موعد تسليمها، أما المهمة رقم 3 فسيُتأخر إنجازها ساعة واحدة عن موعد تسليمها، ويعني ذلك أن مجموع التباطؤ الموزون يساوي 3×1+1×2=5.تُستخدم خوارزميات التحسين للحصول على حلول شبه مثالية لمشكلة محددة في مدة زمنية معقولة.توجد صعوبة في حل مشكلة التباطؤ الموزون للآلة الواحدة؛ لأن تعقيدها يتزايد تزايدًا أسيًا مع عدد المهام، مما يجعل إيجاد أفضل حل ممكن لأحجام المدخلات الكبيرة مكلفًا للغاية وعادة ما يكون مستحيلاً.2023 - 1447--- VISUAL CONTEXT --- **DIAGRAM**: شكل 5.4: رسم توضيحي لتسلسل المهام Description: A horizontal timeline diagram illustrating the scheduling of three tasks (المهمة 1, المهمة 3, المهمة 2) and their associated lateness. The timeline is marked with numerical values from 0 to 23. Task 1 is shown completing early, Task 3 with 'تأخير ساعة' (one hour lateness), and Task 2 with 'تأخير ثلاث ساعات' (three hours lateness). X-axis: الوقت Y-axis: EMPTY Data: The timeline shows segments representing tasks. Task 1 is from 0 to approximately 5. Task 3 is from approximately 5 to 11, with a 'تأخير ساعة' (one hour lateness) indicated around 11. Task 2 is from approximately 15 to 23, with a 'تأخير ثلاث ساعات' (three hours lateness) indicated around 20. The timeline has major grid lines at 0, 5, 10, 15, 20, 23. Key Values: Timeline marks: 0, 5, 10, 15, 20, 23, Task 1 (المهمة 1), Task 3 (المهمة 3) with تأخير ساعة, Task 2 (المهمة 2) with تأخير ثلاث ساعات Context: This diagram visually represents the concept of task sequencing and lateness, complementing the textual explanation of the Single-Machine Weighted Tardiness problem and the calculation of lateness for individual tasks. (Note: Some details are estimated)**TABLE**: شكل 5.5: حساب التباطؤ الموزون Description: A table presenting the details for three tasks, including their due dates, actual completion dates, calculated lateness, and weighted lateness. Table Structure: Headers: المهمة | الموعد المحدد لإنجازها | موعد تسليمها | التأخير | التباطؤ الموزون Rows: Row 1: 1م | 14 | 11 | 0 | 0 Row 2: 2م | 20 | 23 | 3 | 3 Row 3: 3م | 17 | 18 | 1 | 2 Calculation needed: The 'التأخير' (Lateness) is calculated as 'موعد تسليمها' (completion date) minus 'الموعد المحدد لإنجازها' (due date), if the result is positive, otherwise it's 0. The 'التباطؤ الموزون' (Weighted Lateness) is calculated by multiplying 'التأخير' by a specific weight for each task. Based on the example calculation 3×1+1×2=5 and the table values, Task 2 (lateness 3) has an implied weight of 1 (3*1=3), and Task 3 (lateness 1) has an implied weight of 2 (1*2=2). This differs from the text stating weights are 1, 2, 3 for tasks 1, 2, 3 respectively. Context: This table provides the numerical data for the tasks, their scheduling, and the resulting lateness and weighted lateness, which are central to understanding the Single-Machine Weighted Tardiness problem and its objective function. It directly supports the example calculation provided in the text.