ترتيب المهام حسب المتطلبات: قد يصح أكثر من ترتيب

الخلاصة السريعة

في مثالنا الأصلي يصح الترتيب A,B,C,D,E، ويصح أيضًا B,D,A,C,E؛ فكل متطلب يسبق المهمة التابعة له. توجد خمسة ترتيبات صحيحة في المجموع. بعد إضافة الشرط C→B تتكون الدورة B→C→B، ولا يبقى ترتيب كامل يحترم جميع الشروط.

• الترتيب الطوبولوجي يضع كل رأس مرة واحدة في قائمة، ويجعل بداية كل حافة موجهة تسبق نهايتها. وقد يصح أكثر من ترتيب. [1]
• نعني بالسهم A→C أن A يجب أن تنتهي قبل C. في نموذجنا تحتاج C إلى A و B، وتحتاج D إلى B، وتحتاج E إلى C و D.
• قبل أي اختيار، المتاحتان A و B. إذا اخترنا A ثم B، تصبح C و D متاحتين؛ اختيار C أولًا يعطي A,B,C,D,E، واختيار D أولًا يعطي A,B,D,C,E.
• لفحص قائمة، تحقق من ظهور المهام الخمس مرة واحدة، ومن اتجاه الحواف الخمس كلها. القائمة A,C,B,D,E تخالف B→C، رغم احتوائها على كل الأسماء.
• يوجد ترتيب طوبولوجي كامل إذا وفقط إذا خلا المخطط الموجه من الدورات. في مثالنا الشرط الجديد C→B يجعل B تنتظر C بينما C تنتظر B. [1]
• بعد إضافة هذا الشرط، يمكن إنجاز A وحدها؛ وتتوقف B و C و D و E. تقع B و C على الدورة، أما D و E فمحجوبتان بسبب متطلباتهما. لا نحسب هنا مددًا أو أسرع جدول.

اقرأ السهم من المتطلب إلى المهمة التابعة

في الترتيب الطوبولوجي، تظهر الرؤوس جميعًا مرة واحدة، ويأتي مصدر كل حافة قبل وجهتها. قد تسمح العلاقات بأكثر من قائمة صحيحة. [1]

نعرف خمس مهام مجردة A و B و C و D و E. السهم هنا شرط سابق، وليس انتقال عامل بين مكانين: إذا كتبنا A→C، فلا نبدأ C قبل انتهاء A. الحواف كاملة هي A→C و B→C و B→D و C→E و D→E.

تحتاج C إلى الشرطين A و B معًا، لا إلى أحدهما فقط. وتحتاج E إلى C و D معًا. لا توجد متطلبات سابقة لـ A أو B، وليس لـ D في قائمتنا سوى B. لا نستنتج شرطًا جديدًا من قرب دائرتين في الرسم أو من طول السهم.

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

اختَر مهمة لا تنتظر مهمة غير منجزة

في بداية المثال، نستطيع أخذ A أو B؛ فكلاهما بلا متطلب سابق. نختار A للتوضيح، ونعدها منجزة، لكن C لا تصبح متاحة بعد: ما زالت تنتظر B. لذلك نأخذ B في الموضع الثاني.

بعد إنجاز A و B، تتحقق شروط C و D معًا. نختار C في الموضع الثالث، لكن E ما زالت تنتظر D. نأخذ D رابعًا، وعندئذ تصبح E متاحة، فنضعها أخيرًا. نحصل على A,B,C,D,E.

الجدول يسجل المتاح قبل كل اختيار في هذا المسار تحديدًا. لا نعيد مهمة إلى القائمة بعد إنجازها، ولا نكتفي بأن يكون أحد متطلبات المهمة منجزًا عندما تكون لها متطلبات متعددة.

في كل خطوة من هذا البناء اخترنا مهمة اكتملت متطلباتها. لهذا يسبق كل متطلب المهمة التابعة له في القائمة النهائية. هذا إثبات لصحة الاختيارات في نموذجنا، ويمكن مراجعته أيضًا من الحواف مباشرة.

افحص الحواف، ثم قارن القوائم المختلفة

في القائمة A,B,C,D,E تقع A و B قبل C، و B قبل D، و C و D قبل E. هذه الحواف الخمس كلها، لذا تحترم القائمة كل الشروط المعلنة. أما A,C,B,D,E فتضع C قبل B، فتخالف B→C. وجود الأسماء الخمسة دون تكرار شرط لازم هنا، لكنه لا يكفي.

لو اخترنا D قبل C بعد إنجاز A و B، لحصلنا على A,B,D,C,E. وتصح أيضًا B,D,A,C,E: إنجاز B يتيح D حتى لو لم ننجز A، لأن D لا تنتظر A. تظل C مؤجلة حتى تنتهي A.

يمكن حصر الترتيبات في هذا المثال دون تخمين. إذا بدأت A، فلا بد أن تأتي B ثانيًا، ثم نبدّل C و D، وتبقى E أخيرًا؛ هذه قائمتان. وإذا بدأت B، فالاختيار التالي إما A أو D. اختيار A يترك خيارين لـ C و D؛ واختيار D يجبرنا على A ثم C ثم E. تلك ثلاث قوائم أخرى.

المجموع 2 + 3 = 5، والقوائم الكاملة هي A,B,C,D,E و A,B,D,C,E و B,A,C,D,E و B,A,D,C,E و B,D,A,C,E. ليست الأسماء أبجدية ملزمة؛ الحواف هي التي تحدد المقبول. ولا يثبت تعدد الترتيبات أن كل تبديل بين مهمتين مسموح.

شرط إضافي واحد قد يصنع دورة انتظار

المخطط الموجه يقبل ترتيبًا طوبولوجيًا كاملًا إذا وفقط إذا لم يحتو دورة موجهة. وجود دورة يطلب تقديم رأس على نفسه عبر سلسلة الشروط، وهذا يناقض الترتيب. [1]

نضيف C→B إلى حواف المثال، ونترك كل الحواف السابقة. صار B يحتاج إلى C، بينما C يحتاج إلى B وإلى A. لذلك تشكل B→C→B دورة. لا يصلح اختيار B قبل C، لأنه يخالف C→B؛ ولا اختيار C قبل B، لأنه يخالف B→C.

يمكننا إنجاز A لأنها لا تنتظر شيئًا، لكن ذلك لا يحل انتظار B و C المتبادل. ولا تصبح D متاحة لأن B لم تنجز؛ كما تبقى E منتظرة C و D. لا يجوز وضع مهمة محجوبة في القائمة ثم إعلان حل كامل.

الرسم الداخلي يبرز الدورة بين B و C، ثم اعتماد D على B واعتماد E على C و D. المهمة A، التي أنجزناها في البداية، موضحة منفصلة مع شرطها السابق نحو C. الأسهم لا تعرض زمنًا، ولا نعالج الدورة بحذف شرط دون قرار يغيّر النموذج.

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

المتوقفات في المثال المعدل هي B و C و D و E، لكن الدورة تضم B و C فقط. لا يوجد سهم خارج من E، ولا مسار من D يعيدنا إلى D. إذن D و E خارج الدورة، رغم تعذر إنجازهما ما دامت المتطلبات قائمة.

يفرق هذا الفحص بين موضع التعارض وآثاره. لو أردنا تصحيح بيانات هذا المثال، لراجعنا الشرطين B→C و C→B ومعناهما؛ مجرد حذف أسماء D و E من تقرير التوقف لا يحل المشكلة الأصلية. ولا نستنتج من عدم وجود دورة أن المهمة ستنفذ فعليًا بلا موارد أو أعطال.

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