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

Question

لقد بحثت هنا بأفضل ما أستطيع وعلى الرغم من أنني وجدت بعض الأسئلة ذات الصلة، لا أعتقد أنها غطت السؤال المطروح:

افترض موردًا واحدًا وقائمة طلبات معروفة لجدولة مهمة.يتضمن كل طلب start_after، وstart_by، والمدة المتوقعة، والإجراء.

الهدف هو جدولة المهام للتنفيذ في أسرع وقت ممكن مع الحفاظ على جدولة كل مهمة بين start_after وstart_by.

لقد قمت بترميز مثال Prolog بسيط "اعتقدت" أنه يجب أن يعمل ولكن لسوء الحظ أتلقى أخطاء أثناء وقت التشغيل:">=/2:لم يتم إنشاء الحجج بشكل كافٍ".

أي مساعدة أو مشورة موضع تقدير كبير

startAfter(1,0).
startAfter(2,0).
startAfter(3,0).

startBy(1,100).
startBy(2,500).
startBy(3,300).

duration(1,199).
duration(2,199).
duration(3,199).

action(1,'noop1').
action(2,'noop2').
action(3,'noop3').

can_run(R,T) :- startAfter(R,TA),startBy(R,TB),T>=TA,T=<TB.
conflicts(T,R1,T1) :- duration(R1,D1),T=<D1+T1,T>T1.
schedule(R1,T1,R2,T2,R3,T3) :- 
           can_run(R1,T1),\+conflicts(T1,R2,T2),\+conflicts(T1,R3,T3),
           can_run(R2,T2),\+conflicts(T2,R1,T1),\+conflicts(T2,R3,T3),
           can_run(R3,T3),\+conflicts(T3,R1,T1),\+conflicts(T3,R2,T2).

% when traced I *should* see T1=0, T2=400, T3=200

يحرر:لم يكن هدف الصراعات صحيحًا تمامًا:هناك حاجة إلى جملة T>T1 إضافية.

يحرر:يبدو أن هدف الجدول الزمني الخاص بي يعمل إذا قمت بتقديم طلب صالح، وأزواج زمنية ...لكنني عالق في محاولة إجبار Prolog على العثور على قيم صالحة لـ T1..3 عند إعطائي R1..3؟

Answer 1

هناك مشكلتان في التنفيذ الأصلي.قد يعمل بشكل جيد (مع تعديلات طفيفة) في نظام برمجة منطق القيد، ولكن ليس في Prolog المستقيم.في Prolog، ترتيب الأهداف أمر بالغ الأهمية.لقد قمت بتعديل الكود حتى يعمل:

can_run(R, T) :-
    startAfter(R,TA),
    startBy(R,TB),
    between(TA,TB,T).

conflicts(T,R1,T1) :- 
    duration(R1,D1),
    T=<D1+T1,
    T>=T1.

schedule(R1,T1,R2,T2,R3,T3) :- 
    can_run(R1,T1), 
    can_run(R2,T2), 
    R1 \= R2,
    \+ conflicts(T1,R2,T2),
    can_run(R3,T3),
    R3 \= R1, 
    R3 \= R2,
    \+ conflicts(T1,R3,T3),
    \+ conflicts(T2,R1,T1),
    \+ conflicts(T2,R3,T3),
    \+ conflicts(T3,R1,T1),
    \+ conflicts(T3,R2,T2).

between(Low, High, Between) :-
    Between is Low
    ;
    Low < High,
    Next is Low + 1,
    between(Next, High, Between).

أضفت استخدام المسند بين/3 (مدمج محدد في بعض تطبيقات Prolog).فهو يولد الأعداد الصحيحة بين نقطتي النهاية المعطاة.

لقد أضفت عمليات التحقق من عدم المساواة في الجدول/6 لإجبار R1 وR2 وR3 على أن تكون قيمًا مختلفة.

أخيرًا، قمت بإعادة ترتيب الأهداف في الجدول/6 للتأكد من تقييم المسند can_run/2 لزوج من متغيرات Ri/Ti قبل أن يتم فحص تلك المتغيرات عن طريق الصراعات/3.

يتم تشغيل جدول الاستعلام (R1,T1,R2,T2,R3,T3) لعدة دقائق وينتج في النهاية:

?-schedule(R1,T1,R2,T2,R3,T3)
R1 = 1
T1 = 0
R2 = 2
T2 = 400
R3 = 3
T3 = 200

هناك تطبيقات أكثر كفاءة لهذه المشكلة.