جدولة الفترات بأقرب نهاية: اختيار أكبر عدد دون تداخل

حدد هدف العدد وموردًا واحدًا

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

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

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

[1]

سبع فترات مؤلفة بحدود نصف مفتوحة

الفترات الأصلية هي A من 0 إلى 7، وB من 1 إلى 3، وC من 3 إلى 5، وD من 5 إلى 7، وE من 6 إلى 9، وF من 7 إلى 10، وG من 9 إلى 11. تشمل الفترة بداية العمل ولا تشمل حد الانتهاء. لذلك B تنتهي عند 3 ويمكن أن تليها C التي تبدأ عند 3، دون أن يتشاركا مدة موجبة في نموذجنا.

لكل فترة هوية تميزها من غيرها، وبداية ونهاية يحددانها. A وD تنتهيان في الوقت نفسه، لكن A تبدأ قبل D وتستمر مدة أطول. لا نستبدل هويتيهما باسم نهاية واحدة؛ قد يختلف قبولهما بحسب الفترات التي اخترناها قبلهما. كما أن F وG تتداخلان بين 9 و10، رغم اختلاف نهايتيهما، فلا نختارهما معًا على المورد الواحد.

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

رتب النهاية ثم تتبع القرار

نرتب الفترات بحسب النهاية تصاعديًا، ثم بحسب البداية والهوية لفك التعادل في كودنا. يصبح الترتيب B ثم C ثم A ثم D ثم E ثم F ثم G. أول فترة B تنتهي عند 3 فنختارها، ونجعل آخر نهاية مختارة 3. تأتي C ببداية 3، فنجعلها التالية ونحدث آخر النهاية إلى 5. المساواة مع النهاية السابقة مقبولة وفق حدودنا.

بعد ذلك تصل A بنهاية 7 لكنها تبدأ عند 0، وهو قبل آخر نهاية مختارة 5، فنرفضها. تصل D بنهاية 7 أيضًا وبداية 5، فتلائم ما اخترناه ونقبلها. تصبح آخر النهاية 7. نرفض E لأن بدايتها 6 قبل هذا الحد، ثم نقبل F لأنها تبدأ عند 7 وتنتهي عند 10، ونرفض G لأنها تبدأ عند 9 قبل انتهاء F.

النتيجة المختارة B وC وD وF، وعددها أربعة. سجل القرار يحفظ آخر النهاية قبل تقييم كل مرشح، لا بعد قبوله فقط، كي يمكن تفسير سبب الرفض. رفض A لم يجعل آخر النهاية 7؛ بقيت 5 إلى أن قبلنا D. هذه نقطة عملية مهمة: لا تحدث الحالة من فترة لم تدخل الجدول، وإلا قد تمنع خيارًا لاحقًا متوافقًا بلا سبب من الاختيارات الفعلية.

لماذا يكفي آخر انتهاء مختار؟

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

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

عند البداية لا توجد فترة سابقة، لذلك يستعمل كودنا حالة None في آخر النهاية لقبول المرشح الأول. ليست None وقتًا صفريًا أو حدًا من البيانات. هذا يسمح بتجربة حدود سالبة مثل فترة من سالب 3 إلى سالب 1 تليها فترة إلى 2، دون رفض الأولى بسبب افتراض غير معلن أن كل بداية يجب أن تكون بعد صفر.

تلامس الأطراف يختلف من التداخل

في مثالنا، B وC تلتقيان عند الحد 3، وC وD عند 5، وD وF عند 7. شرط القبول هو أن البداية الجديدة أكبر من النهاية السابقة أو مساوية لها. كتابة شرط أكبر فقط تستبعد هذه الحالات المتلامسة، فتجيب مسألة أخرى تسمح بفراغ موجب إلزامي بين كل فترتين. لا نغير الرمز ثم نصف الناتج بأنه يحقق العقد نفسه.

وبالمقابل، بداية 6 لفترة E لا تلائم نهاية 7 لفترة D، لأن مدة من 6 إلى 7 تدخل في كلتيهما. كما لا يصبح التداخل مسموحًا لأن إحدى الفترتين أقصر أو لأن هويتهما مختلفة. التوافق علاقة بين الحدود في مورد واحد، ولم نضف قاعدة تعطي الأولوية لحرف أو لنوع طلب مختلف في هذا المثال.

يمكن للقارئ تجربة فترتين من 1 إلى 3 ومن 3 إلى 4 ليجد أنهما مقبولتان معًا، ثم تغيير البداية الثانية إلى 2 فيصبح الجمع غير ممكن. هذه حالة صغيرة تفصل المساواة من التداخل الحقيقي. نحتاج مثل هذا الفحص قبل الاعتماد على جدول يبدو مرتبًا بصريًا؛ تقارب حدود مرسومة لا يشرح وحده سياسة الأطراف التي اختارها البرنامج.

أقرب بداية قد يحجب بدائل أكثر

لو رتبنا الخيارات الأصلية بحسب البداية ثم أخذنا أول ما يلائم، نبدأ بـA عند 0 ونبقي المورد مشغولًا حتى 7. لا نختار B أوC أوD أوE بعد ذلك لأن بداياتها قبل 7. نصل إلى F التي تبدأ عند 7 فنقبلها، ثم نرفض G المتداخلة معها. النتيجة A وF فقط، وعددها اثنان بدل أربعة في اختيارنا بأقرب نهاية.

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

ولا يلزم أن تخفق قاعدة البداية في كل قائمة؛ قد توافق أقرب نهاية على خيارات معينة. وجود قائمة سهلة نجحت فيها لا يلغي المثال الفاصل الذي حسبناه. كما أن ناتج A وF صالح من حيث عدم التداخل، لكنه لا يحقق أكبر عدد هنا. نميز صلاحية الجدول من أمثليته: قد نختار مجموعة متوافقة بينما توجد مجموعة أخرى أكبر.

عرض الرسم بالحجم الكامل

الأقصر مدة ليس قاعدة كافية

في مثال مستقل، نأخذ H من 0 إلى 4، وI من 4 إلى 8، وJ من 3 إلى 5. مدة J اثنان، وهي أقل من مدة H أوI التي تساوي أربعة. إذا اخترنا الأقصر أولًا وحذفنا ما يتداخل معها، نقبل J ونفقد H وI، لأن J تتداخل مع نهاية الأولى وبداية الثانية. يصبح العدد واحدًا.

لكن H وI يمكن أن تعمل إحداهما بعد الأخرى عند الحد 4، فتكون المجموعة المتوافقة من فترتين. هذا المثال لا يحتاج وزنًا أو تجهيزًا ليبين أن قصر الفترة من نفسه ليس معيارًا كافيًا لتعظيم العدد. موضع الفترة بالنسبة لغيرها مهم؛ فترة قصيرة بين اثنتين قد تعارضهما معًا بدل إفساح المجال لهما.

قاعدة أقرب نهاية في المثال المستقل تبدأ بـH التي تنتهي عند 4، ثم تتجاوز J المتداخلة معها وتقبل I التي تبدأ عند 4. لا نخلط بين ترتيب المدد وترتيب النهايات؛ يمكن أن يكون أول المنتهين أطول من مرشح آخر يبدأ لاحقًا. نثبت الجدول والهدف ونراجع القرارات الفعلية قبل الاستنتاج من وصف مبسط مثل اختر ما يستهلك وقتًا أقل.

حجة التبادل ضمن الفرضيات

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

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

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

[2]

الكود يحتفظ بقرارات القبول والرفض

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

تحفظ الدالة نسختها من تسلسل الإدخال ثم ترتب قائمة جديدة، فلا تفرز قائمة المستدعي في مكانها. ترجع الفترات المختارة مع سجل قرارات لكل مرشح في ترتيب المرور. يحوي القرار هويته وحدوده وآخر نهاية مختارة قبله وعلم القبول. هذا يتيح مراجعة لماذا رفضنا A رغم أنها تنتهي مثل D، دون الاكتفاء بالعدد النهائي أربعة.

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

def select_intervals(records):
    jobs = tuple(records)
    labels = set()
    for label, start, finish in jobs:
        if not isinstance(label, str) or not label:
            raise ValueError("nonempty textual identity required")
        if label in labels:
            raise ValueError("duplicate identity")
        labels.add(label)
        if type(start) is not int or type(finish) is not int:
            raise TypeError("integer boundaries required")
        if start >= finish:
            raise ValueError("positive duration required")
    ordered = sorted(jobs, key=lambda job: (job[2], job[1], job[0]))
    selected = []
    decisions = []
    last_finish = None
    for job in ordered:
        label, start, finish = job
        previous_finish = last_finish
        accepted = last_finish is None or start >= last_finish
        if accepted:
            selected.append(job)
            last_finish = finish
        decisions.append({
            "identity": label,
            "start": start,
            "finish": finish,
            "previous_selected_finish": previous_finish,
            "accepted": accepted,
        })
    return {"selected": tuple(selected), "decisions": tuple(decisions)}

تساوي النهاية لا يعني رفض كل المتعادلين

تنتهي A وD عند 7، لكن البداية عند 0 في A وعند 5 في D. في ترتيب كودنا تأتي A أولًا بسبب البداية، فنرفضها بعدما اخترنا B وC. ثم نراجع D نفسها ونقبلها لأن بدايتها تساوي آخر نهاية 5. لا يعني رفض مرشح بنهاية 7 أن جميع أصحاب هذه النهاية غير مناسبين.

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

في أصلنا، B وC وD وG مجموعة أخرى من أربعة طلبات، لأن G تبدأ عند 9 بعد نهاية D عند 7. كودنا اختار F قبل G لأنها تنتهي عند 10 قبل 11، لكن العدد أربعة في الحالتين. لذلك لا نسمي G فترة لا تدخل أي حل مثالي لمجرد أن مرورنا رفضها بعد اختيار F؛ الرفض وصف لمسار قرارات محدد.

الأوزان تغير الشيء الذي نريد تعظيمه

نأخذ مثالًا مستقلًا بثلاث فترات: L من 0 إلى 6 بقيمة 20، وM من 0 إلى 3 بقيمة 6، وN من 3 إلى 6 بقيمة 6. إذا عظمنا العدد نختار M وN، فهما طلبان متتابعان مقابل طلب واحد L. وإذا عظمنا مجموع القيم، تعطي L مقدار 20 بينما تعطي M وN معًا 12 فقط.

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

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

التجهيز والموارد المتعددة يضيفان شروطًا

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

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

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

مرجع مستقل يبحث جميع المجموعات

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

وننشئ جميع الفترات الموجبة بين الحدود صفر وواحد واثنين وثلاثة وأربعة؛ عدد خياراتها المختلفة عشرة. نجرب كل مجموعة إدخال من هذه الخيارات، ونقارن عدد مختارات الدالة بالمرجع الذي يبحث كل المجموعات الجزئية. هذه فحوص محدودة على بيانات صحيحة صغيرة، وتختلف من البرهان العام ومن قياس أداء على ملف كبير.

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

بطاقة نتيجة تربط الجدول بالهدف

يمكن أن تصف بطاقة النتيجة سبع فترات معلومة، وموردًا واحدًا، وحدودًا ببداية مشمولة وانتهاء غير مشمول، وهدفًا هو أكبر عدد دون أوزان أو تجهيز. نكتب المختارات B وC وD وF وعددها أربعة، ونضيف سجل أسباب القبول والرفض. بهذه البيانات يستطيع المراجع معرفة أن رفض G حصل بعد F، لا لأن G فترة غير صالحة في أصلها.

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

قبل استعمال الفكرة، حدد معنى التداخل والمورد والهدف وثبات الحدود. جرب المثال الذي يبدأ فيه A أبكر لكنه يحجب بدائل أكثر، ثم قارن بسجل أقرب نهاية. ستعرف ما الذي حققه المرور: اختيار مجموعة أكبر في النموذج المعلن، مع قرارات قابلة للتتبع، دون ادعاء أنه يغطي كل معنى قد تحمله كلمة جدول في خدمة فعلية.