सामयिक योजना और निर्धारण (Temporal Planning and Scheduling)

सामयिक योजना और निर्धारण (temporal planning and scheduling) उन क्रियाओं को संभालने के लिए योजना का विस्तार करते हैं जिनमें समय लगता है, जो समवर्ती रूप से चल सकती हैं, और सीमित संसाधनों का उपभोग करती हैं, जिससे ऐसी योजनाएँ बनती हैं जो न केवल यह निर्दिष्ट करती हैं कि क्या करना है बल्कि यह भी कि कब करना है।

Definition

सामयिक योजना एक ऐसी योजना बनाती है जिसमें क्रियाओं की अवधि होती है और वे सामयिक और संसाधन बाधाओं के अधीन ओवरलैप हो सकती हैं; निर्धारण (scheduling) गतिविधियों के एक सेट को प्रारंभ समय (और संसाधन) निर्दिष्ट करता है ताकि सभी बाधाएँ, जैसे कि क्रम, समय-सीमा (deadlines), और क्षमताएँ, पूरी हों।

Scope

यह विषय स्पष्ट समय और संसाधनों के साथ योजना और निर्धारण को शामिल करता है: स्थायी क्रियाएँ (durative actions), समवर्तीता (concurrency) और सामयिक बाधाएँ (temporal constraints), सामयिक बाधा नेटवर्क (जैसे सरल सामयिक समस्या) और एलन के अंतराल बीजगणित (Allen's interval algebra) का प्रतिनिधित्व और समाधान, तथा संसाधन-बाधित गतिविधियों के निर्धारण के साथ योजना का एकीकरण। यह इस बात पर ध्यान देता है कि क्रिया चयन के साथ-साथ समय और संसाधन व्यवहार्यता पर कैसे विचार किया जाता है। शुद्ध संसाधन-मुक्त शास्त्रीय योजना को संबंधित विषयों में माना जाता है।

Core questions

• स्थायी क्रियाओं और उनकी प्रारंभ और समाप्ति स्थितियों का प्रतिनिधित्व कैसे किया जाता है?
• घटनाओं के बीच सामयिक बाधाओं को कैसे मॉडल किया जाता है और उनकी संगति की जाँच कैसे की जाती है?
• समवर्ती गतिविधियों के बीच सीमित संसाधनों का आवंटन कैसे किया जाता है?
• योजना (कौन सी क्रियाएँ तय करना) और निर्धारण (कब तय करना) को कैसे संयोजित या अलग किया जाता है?

Key concepts

• स्थायी क्रियाएँ
• समवर्तीता और ओवरलैप
• सामयिक बाधाएँ
• सरल सामयिक समस्या
• एलन का अंतराल बीजगणित
• संसाधन बाधाएँ
• निर्धारण
• समय-सीमा और मेकस्पैन (makespan)

Key theories

सामयिक बाधा नेटवर्क

समय बिंदुओं के बीच मात्रात्मक सामयिक बाधाओं को एक नेटवर्क के रूप में दर्शाया जा सकता है जिसकी संगति और सबसे तंग सीमाएँ सरल सामयिक समस्या के लिए कुशलता से गणना की जाती हैं, जो कई योजनाकारों और निर्धारकों की सामयिक-तर्क रीढ़ प्रदान करती हैं।

गुणात्मक समय के लिए अंतराल बीजगणित

एलन का अंतराल बीजगणित समय अंतरालों के बीच संभावित गुणात्मक संबंधों (पहले, दौरान, ओवरलैप, आदि) को दर्शाता है और जब सटीक समय अज्ञात होता है तो सामयिक ज्ञान के बारे में तर्क का समर्थन करता है।

निर्धारण के साथ योजना का एकीकरण

यथार्थवादी समस्याओं के लिए क्रियाओं का चयन करना और उन्हें एक साथ समय और संसाधन आवंटित करना आवश्यक है; स्वचालित योजना का सिद्धांत स्थायी क्रियाओं, समवर्तीता और संसाधन बाधाओं को ऐसे विस्तार के रूप में मानता है जो क्रिया चयन को बाधा-आधारित निर्धारण के साथ जोड़ते हैं।

Clinical relevance

सामयिक योजना और निर्धारण अंतरिक्ष यान और रोवर संचालन, विनिर्माण और परियोजना निर्धारण, परिवहन और चालक दल निर्धारण, और किसी भी ऐसी सेटिंग में आवश्यक हैं जहाँ समयबद्ध, समवर्ती, संसाधन-बाधित गतिविधियों का समन्वय किया जाना चाहिए; ऐसी प्रणालियों में वास्तविक अंतरिक्ष मिशनों के लिए नियोजित संचालन होते हैं।

History

गुणात्मक सामयिक तर्क को एलन के अंतराल बीजगणित (1983) द्वारा औपचारिक रूप दिया गया था, और मात्रात्मक सामयिक बाधा नेटवर्क को डेचर, मेइरी और पर्ल (1991) द्वारा। ये नींव, 2000 के दशक की शुरुआत में PDDL में जोड़े गए स्थायी-क्रिया मॉडल के साथ, स्वायत्त अंतरिक्ष यान नियंत्रण जैसे अनुप्रयोगों में उपयोग किए जाने वाले सामयिक योजनाकारों को सक्षम किया।

Key figures

• James F. Allen
• Rina Dechter
• Judea Pearl
• Itay Meiri
• Nicola Muscettola

Seminal works

• dechter1991
• allen1983

Frequently asked questions

योजना और निर्धारण में क्या अंतर है?

योजना यह तय करती है कि लक्ष्यों को प्राप्त करने के लिए कौन सी क्रियाएँ करनी हैं, जबकि निर्धारण यह तय करता है कि वे क्रियाएँ कब होंगी और वे किन संसाधनों का उपयोग करेंगी, दिए गए क्रम और क्षमता बाधाओं के साथ। कई वास्तविक समस्याओं के लिए दोनों की आवश्यकता होती है, और सामयिक योजना क्रिया चयन को समय और संसाधन तर्क के साथ एकीकृत करती है।

सरल सामयिक समस्या क्या है?

सरल सामयिक समस्या एक सामयिक बाधा नेटवर्क है जिसमें प्रत्येक बाधा दो समय बिंदुओं के बीच के अंतर को एक अंतराल द्वारा सीमित करती है। इसकी संगति और सबसे तंग निहित सीमाओं की कुशलता से गणना की जा सकती है, जो इसे योजनाकारों और निर्धारकों में सामयिक तर्क के लिए एक व्यावहारिक कोर बनाती है।