Resource-constrained Project Scheduling with Time-of-Use Energy Tariffs and Machine States: A Logic-based Benders Decomposition Approach

तकनीकी सारांश: समय-उपयोग (Time-of-Use) ऊर्जा टैरिफ और मशीन अवस्थाओं के साथ संसाधन-बाधित परियोजना शेड्यूलिंग

1. समस्या की परिभाषा

यह शोध पत्र संसाधन-बाधित परियोजना शेड्यूलिंग समस्या (RCPSP) के एक रूपांतर को संबोधित करता है जो समय-उपयोग (TOU) ऊर्जा टैरिफ और मशीन अवस्था संक्रमण (machine state transitions) को एकीकृत करता है। इस समस्या में पूर्ववर्ती बाधाओं (precedence constraints) और सीमित संसाधन क्षमताओं के अधीन गैर-पूर्वव्यापी (non-preemptive) कार्यों को शेड्यूल करना शामिल है।

मुख्य विशेषताएं निम्नलिखित हैं:

• ऊर्जा-गहन संसाधन: एक विशिष्ट संसाधन ($R_0$) की क्षमता एकत्मक (unitary) है और यह ऊर्जा-गहन है। यह तीन अवस्थाओं में हो सकता है: proc (प्रोसेसिंग), idle (आइडल), या off (ऑफ)।
• अवस्था संक्रमण (State Transitions): अवस्थाओं के बीच संक्रमण के लिए विशिष्ट अवधि और ऊर्जा लागत लगती है। उदाहरण के लिए, मशीन को चालू करने या बंद करने में महत्वपूर्ण ऊर्जा और समय खर्च होता है। मशीन को off अवस्था में शुरू और समाप्त होना चाहिए।
• कार्य वर्गीकरण: कार्यों को ऊर्जा-गहन कार्यों (जिनके लिए $R_0$ को proc अवस्था में होना आवश्यक है) और गैर-ऊर्जा-गहन कार्यों (जो $R_0$ का उपयोग नहीं करते हैं) में विभाजित किया गया है।
• उद्देश्य: लक्ष्य कुल ऊर्जा लागत (TEC) और मेकस्पैन ($C_{max}$) के एक उत्तल संयोजन (convex combination) को न्यूनतम करना है। TEC की गणना TOU टैरिफ के आधार पर की जाती है, जो समय के साथ भिन्न हो सकते हैं और नकारात्मक भी हो सकते हैं। उद्देश्य फलन (objective function) को TEC और $C_{max}$ के स्वतंत्र अनुकूलन से प्राप्त निचली सीमाओं का उपयोग करके सामान्यीकृत (normalized) किया गया है।

2. कार्यप्रणाली

लेखक तीन अलग-अलग मॉडलिंग दृष्टिकोणों का प्रस्ताव करते हैं और उनकी तुलना करते हैं:

A. मोनोलिथिक मॉडल (Monolithic Models)
दो संक्षिप्त मॉडल तैयार किए गए हैं जो पूरी समस्या को एक साथ हल करते हैं:

1. मोनोलिथिक ILP: एक टाइम-इंडेक्स्ड वेरिएबल्स वाला इंटीजर लीनियर प्रोग्रामिंग मॉडल। इसमें मशीन अवस्थाओं को संभालने के लिए प्रोसेसिंग अंतराल के बीच पूर्व-परिकलित इष्टतम संक्रमण लागतों (SPACES एल्गोरिदम के माध्यम से) को शामिल किया गया है।
2. मोनोलिथिक CP: वैकल्पिक अंतराल वेरिएबल्स (optional interval variables) का उपयोग करने वाला एक कंस्ट्रेंट प्रोग्रामिंग मॉडल। यह दृष्टिकोण कार्य प्रसंस्करण और इष्टतम अवस्था संक्रमणों को अंतराल वेरिएबल्स के रूप में प्रस्तुत करता है, जिससे सॉल्वर संक्रमणों की संख्या और प्लेसमेंट को गतिशील रूप से निर्धारित कर सकता है।

B. लॉजिक-बेस्ड बेंडर्स डिकंपोजिशन (LBBD)
मुख्य योगदान एक हाइब्रिड LBBD दृष्टिकोण है जो समस्या को दो युग्मित उप-समस्याओं में विभाजित करता है:

• मास्टर प्रॉब्लम (ILP): मशीन अवस्था और ऊर्जा लागत अनुकूलन को हल करता है। यह ऊर्जा-गहन कार्यों के प्रारंभ समय और अवस्था संक्रमणों के अनुक्रम को निर्धारित करता है। यह संक्रमण लागत की गणना के लिए एक संशोधित SPACES ग्राफ का उपयोग करता है।
• सबप्रॉब्लम (CP): RCPSP घटक के लिए एक व्यवहार्यता जांच (feasibility check)। मास्टर द्वारा ऊर्जा-गहन कार्यों के निश्चित प्रारंभ समय दिए जाने के बाद, यह संसाधन क्षमताओं और पूर्ववर्ती बाधाओं का सम्मान करते हुए शेष गैर-ऊर्जा-गहन कार्यों को शेड्यूल करने का प्रयास करता है।
• कटिंग प्लेन्स (Cutting Planes):
  • व्यवहार्यता कट (Feasibility Cuts): तब उत्पन्न होते हैं जब उप-समस्या अव्यवहार्य होती है, जो मास्टर को ऊर्जा-ग गहन कार्यों के समान संघर्षपूर्ण सेट का चयन करने से रोकते हैं।
  • इष्टतमता कट (Optimality Cuts): तब उत्पन्न होते हैं जब उप-समस्या व्यवहार्य होती है लेकिन वह मास्टर के अनुमान से भिन्न मेकस्पैन प्रदान करती है। ये कट मेकस्पैन पर निचली सीमा लागू करने के लिए रिसोर्स-फ्लो ग्राफ के क्रिटिकल पाथ का उपयोग करते हैं।

3. मुख्य योगदान

1. समस्या का सूत्रकरण: मशीन अवस्था गतिशीलता (proc, idle, off) को TOU टैरिफ के साथ जोड़ने वाले एक नए RCPSP रूपांतर का परिचय, जो एकल-मशीन अध्ययनों को मल्टी-रिसोर्स प्रोजेक्ट शेड्यूलिंग संदर्भ तक विस्तारित करता है।
2. नवीन LBBD ढांचा: एक डिकंपोजिशन रणनीति का विकास जो ऊर्जा प्रबंधन (मास्टर) को संयोजी शेड्यूलिंग (सबप्रॉब्लम) से अलग करती है। लेखक मशीन अवस्थाओं और RCPSP बाधाओं के बीच परस्पर क्रिया के लिए विशेष रूप से तैयार किए गए बेंडर्स कट्स प्राप्त करते हैं।
3. सामान्यीकरण: यह प्रदर्शन करना कि LBBD आर्किटेक्चर अन्य शेड्यूलिंग समस्याओं के लिए भी लागू है, विशेष रूप से:
   • ब्लॉकिंग समय और कुल भारित विलंबता (total weighted tardiness) उद्देश्य के साथ RCPSP।
   • फ्लेक्सिबल जॉब शॉप शेड्यूलिंग (FJSP)।

4. प्रयोगात्मक परिणाम

प्रयोग PSPLIB डेटासेट से प्राप्त इंस्टेंस पर किए गए, जिन्हें ऊर्जा-गहन कार्यों के घनत्व (Sparse, Standard, Dense) और ऊर्जा लागत एवं मेकस्पैन के बीच बदलते वेटिंग पैरामीटर ($\alpha$) के आधार पर वर्गीकृत किया गया था।

• मोनोलिथिक मॉडलों के विरुद्ध प्रदर्शन:
  • अधिकांश परिदृश्यों में, विशेष रूप से बड़े इंस्टेंस (480 कार्यों तक) के लिए और जब मेकस्पैन मानदंड कम प्रभावी हो ($\alpha \to 1$), दोनों मोनोलिथिक ILP और CP दृष्टिकोणों की तुलना में LBBD बेहतर प्रदर्शन करता है।
  • LBBD दृष्टिकोण बड़े खोज स्थानों (search spaces) के साथ संघर्ष करने वाले मोनोलिथिक CP की तुलना में काफी तेजी से इष्टतम समाधानों तक पहुँचता है।
  • मोनोलिथिक ILP उचित रूप से कार्य करता है लेकिन आम तौर पर LBBD की तुलना में धीमा होता है।
• पैरामीटर्स का प्रभाव:
  • $\alpha = 1$ (केवल ऊर्जा): LBBD असाधारण रूप से अच्छा प्रदर्शन करता है, क्योंकि उप-समस्या एक शुद्ध व्यवहार्यता जांच में बदल जाती है, जिसे CP सॉल्वर कुशलतापूर्वक संभालते हैं।
  • $\alpha < 1$ (मिश्रित उद्देश्य): LBML Standard और Dense इंस्टेंस में श्रेष्ठ बना रहता है। हालांकि, कम $\alpha$ (उच्च मेकस्पैन वेट) वाले Sparse इंस्टेंस में, मोनोलिथिक CP कभी-कभी LBBD से बेहतर प्रदर्शन करता है क्योंकि LBBD में उप-समस्या की समय सीमा खोज स्थान के अन्वेषण में बाधा डाल सकती है।
• सामान्यीकरण के परिणाम:
  • ब्लॉकिंग समय वाले RCPSP में, LBBD ने 30 मिनट के भीतर लगभग 90% इंस्टेंस के लिए इष्टतम समाधान खोजे, जबकि मोनोलिथिक CP के लिए यह 5% से कम था।
  • फ्लेक्सिबल जॉब शॉप समस्या में, LBBD ने समय प्रतिबंधों के तहत मोनोलिथिक ILP (83/120 बार) की तुलना में अधिक बार व्यवहार्य समाधान (107/120 बार) खोजे।

5. महत्व और दावे

यह शोध पत्र दावा करता है कि प्रस्तावित LBBD दृष्टिकोण जटिल मशीन अवस्थाओं वाले ऊर्जा-जागरूक शेड्यूलिंग समस्याओं के लिए एक महत्वपूर्ण प्रगति है। इसका प्राथमिक महत्व निरंतर ऊर्जा लागत अनुकूलन को असतत संयोजी शेड्यूलिंग बाधाओं से विच्छेदित (decouple) करने की इसकी क्षमता में निहित है, जिससे प्रत्येक को सबसे उपयुक्त सॉल्वर (ऊर्जा के लिए ILP, शेड्यूलिंग के लिए CP) द्वारा हल किया जा सके।

लेखक तर्क देते हैं कि यह डिकंपोजिशन न केवल विशिष्ट RCPSP-TOU समस्या के लिए प्रभावी है, बल्कि यह एक सामान्यीकरण योग्य ढांचा (generalizable framework) है जो किसी भी ऐसी शेड्यूलिंग समस्या के लिए लागू है जहाँ ऊर्जा-गहन गतिविधियों को शेष संसाधन आवंटन तर्क से अलग किया जा सकता है। यह कार्य रेखांकित करता है कि जबकि मोनोलिथिक मॉडल सहज होते हैं, वे अक्सर समस्या के आकार और जटिलता के साथ स्केल करने में विफल रहते हैं, जबकि LBBD दृष्टिकोण विभिन्न इंस्टेंस घनत्वों और उद्देश्य वेटिंग्स के बीच मजबूती बनाए रखता है।

शोध पत्र यह उल्लेख करते हुए समाप्त होता है कि भविष्य के कार्य कई ऊर्जा-गहन संसाधनों, अधिक जटिल अवस्था संक्रमणों और ऊर्जा भंडारण या ऑन-साइट जनरेशन के एकीकरण के साथ-साथ ऊर्जा टैरिफ में अनिश्चितता के प्रभाव का पता लगा सकते हैं।