शेड्यूलिंग प्रोग्राम

Question

के लिए क्या एल्गोरिदम मुझे शेड्यूलिंग कार्यों की समस्या है। प्रत्येक कार्य में एक प्रारंभिक समय टी सुझाया जाता है (इसे [टी -10, टी +10] से शुरू करने की आवश्यकता होती है), पूरा करने के लिए एल मिनट लगते हैं और कई संसाधनों का उपयोग करता है [आर 1, आर 2, ...]। जब संसाधन का उपयोग किया जा रहा है, तो कोई अन्य कार्य इसका उपयोग नहीं कर सकता है। यह देखते हुए कि केवल प्रारंभ समय ही लचीला है, मेरा लक्ष्य कार्यों को शेड्यूल करना है ताकि वे किसी भी संसाधन को एक्सेस कर सकें या हल करने की आवश्यकता वाले सभी संघर्षों को इंगित कर सकें।

इस उद्देश्य के लिए मैं कौन सा एल्गोरिदम उपयोग कर सकता हूं? धन्यवाद।

Answer 1

आप prolog के रूप में इस टैग किया है के बाद से, मैं इसे constraint logic programming (CLP) में लागू करने की सलाह देते हैं और एल्गोरिदम अपने CLP कार्यान्वयन में बनाया का उपयोग कर। आंशिक उदाहरण:

:- use_module(library(clpfd)). 

on_time([]). 
on_time([Task|Tasks]) :- 
    Task = task(TSuggested,TActual,L,Rs), 
    TActual #>= TSuggested - 10, 
    TActual #=< TSuggested + 10, 
    on_time(Tasks). 

एक और विधेय की जाँच करेगा कि कोई भी दो कार्यों समवर्ती एक ही संसाधन का उपयोग करें:

nonoverlap(R,Task1,Task2) :- 
    Task1 = task(_,T1,L1,Rs2), 
    Task2 = task(_,T2,L2,Rs2), 
    ((member(R,Rs1), member(R,Rs2)) -> 
     T2 #> T1+L1  % start Task2 after Task1 has finished 
     #\/    % OR 
     T1 #> T2+L2  % start Task1 after Task2 has finished 
    ; 
     true   % non-conflicting, do nothing 
    ). 

अंत में, सभी विवश चर पर labeling फोन उन्हें लगातार मान देना। यह CLP(fd) का उपयोग करता है, जो पूर्णांक समय इकाइयों के लिए काम करता है। CLP(R) वास्तविक मूल्य वाले समय के लिए समान है लेकिन यह थोड़ा अधिक जटिल है। लिंक एसडब्ल्यूआई-प्रोलॉग के लिए हैं लेकिन एसआईसीस्टस और ECLiPSe समान पुस्तकालय हैं।

Answer 2

इस तरह की शेड्यूलिंग समस्याओं को अक्सर कॉन्स्ट्रेंट प्रोग्रामिंग सीपी या मिश्रित इंटीजर प्रोग्रामिंग (एमआईपी) का उपयोग करके सबसे अच्छा संबोधित किया जाता है। दोनों घोषणात्मक दृष्टिकोण हैं, इसलिए आपको केवल अपनी समस्या के गुणों पर ध्यान केंद्रित करने की आवश्यकता है और एक विशेष इंजन अंतर्निहित एल्गोरिदम को संभालने दें। अधिक जानकारी विकिपीडिया पर पाया जा सकता:

http://en.wikipedia.org/wiki/Constraint_programming

http://en.wikipedia.org/wiki/Linear_programming

Answer 3

अगर आपका कमी या अपनी समस्या डोमेन बाहर स्केल करेगा, आप भी एक नज़र अपूर्ण एल्गोरिदम में, इस तरह के रूप में लेना चाहिए: तब्बू खोज और नकली annealing के रूप में

• Metaheuristics इस तरह के। वहाँ Drools Planner जैसे कुछ खुले स्रोत कार्यान्वयन हैं।

• आनुवांशिक एल्गोरिदम, जैसे कि जेजीएपी।