2025-11-14T12:46:11.790924

Minimizing the Weighted Makespan with Restarts on a Single Machine

Amouzandeh, Jansen, Pirotton et al.

We consider the problem of minimizing the weighted makespan on a single machine with restarts. Restarts are similar to preemptions but weaker: a job can be interrupted, but then it has to be run again from the start instead of resuming at the point of interruption later. The objective is to minimize the weighted makespan, defined as the maximum weighted completion time of jobs. We establish a lower bound of 1.4656 on the competitive ratio achievable by deterministic online algorithms. For the case where all jobs have identical processing times, we design and analyze a deterministic online algorithm that improves the competitive ratio to better than 1.3098. Finally, we prove a lower bound of 1.2344 for this case.

academic

एकल मशीन पर पुनः आरंभ के साथ भारित मेकस्पैन को कम करना

मूल जानकारी

पेपर ID: 2510.09589
शीर्षक: Minimizing the Weighted Makespan with Restarts on a Single Machine
लेखक: Aflatoun Amouzandeh, Klaus Jansen, Lis Pirotton, Rob van Stee, Corinna Wambsganz
वर्गीकरण: cs.DS (डेटा संरचना और एल्गोरिदम)
प्रकाशन तिथि: 10 अक्टूबर 2025
पेपर लिंक: https://arxiv.org/abs/2510.09589

सारांश

यह पेपर एकल मशीन वातावरण में पुनः आरंभ तंत्र के साथ भारित अधिकतम समापन समय न्यूनीकरण समस्या का अध्ययन करता है। पुनः आरंभ तंत्र पूर्वाधिकार के समान है लेकिन कमजोर है: कार्यों को बाधित किया जा सकता है, लेकिन उन्हें बाधित बिंदु से पुनः शुरू करने के बजाय शुरुआत से फिर से चलाया जाना चाहिए। उद्देश्य भारित अधिकतम समापन समय को कम करना है, जिसे सभी कार्यों के अधिकतम भारित समापन समय के रूप में परिभाषित किया गया है। अनुसंधान नियतात्मक ऑनलाइन एल्गोरिदम प्रतिस्पर्धा अनुपात के लिए 1.4656 की निचली सीमा स्थापित करता है, सभी कार्यों के समान प्रसंस्करण समय के मामले के लिए एक नियतात्मक ऑनलाइन एल्गोरिदम डिजाइन और विश्लेषण करता है, प्रतिस्पर्धा अनुपात को 1.3098 से बेहतर में सुधारता है, और इस मामले में 1.2344 की निचली सीमा साबित करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

इस पेपर में अध्ययन की गई मूल समस्या एकल मशीन शेड्यूलिंग में भारित अधिकतम समापन समय न्यूनीकरण समस्या है, जिसे 1|rj, online, restart|WCmax के रूप में दर्शाया गया है। प्रत्येक कार्य j की निम्नलिखित विशेषताएं हैं:

प्रसंस्करण समय pj
आगमन समय rj
भार wj

उद्देश्य फलन WCmax = max{wjCj} है, जहां Cj कार्य j का समापन समय है।

अनुसंधान का महत्व

सैद्धांतिक महत्व: अधिकतम समापन समय न्यूनीकरण शेड्यूलिंग सिद्धांत में एक मौलिक समस्या है, जिसका महत्वपूर्ण सैद्धांतिक मूल्य है
व्यावहारिक अनुप्रयोग: क्लाउड कंप्यूटिंग, ऑपरेटिंग सिस्टम कार्य शेड्यूलिंग आदि परिदृश्यों में, कार्यों को उच्च प्राथमिकता वाले कार्यों के आगमन के कारण बाधित और पुनः आरंभ किया जा सकता है
मॉडल नवाचार: पुनः आरंभ मॉडल पारंपरिक पूर्वाधिकार-पुनः शुरुआत मॉडल की तुलना में कुछ वास्तविक अनुप्रयोग परिदृश्यों के अनुरूप है

मौजूदा विधियों की सीमाएं

Li 12 ने एकल मशीन समस्या के लिए प्रतिस्पर्धा अनुपात निचली सीमा 2 स्थापित की और प्रतिस्पर्धा अनुपात 3 के साथ एक ऑनलाइन एल्गोरिदम प्रदान किया
Chai आदि 4 ने एकल मशीन समस्या के प्रतिस्पर्धा अनुपात को 2 तक सुधारा
समान प्रसंस्करण समय के मामले के लिए, Li ने (√5+1)/2 के इष्टतम प्रतिस्पर्धा अनुपात के साथ एक एल्गोरिदम प्रस्तावित किया
Liang आदि 13 ने एकल पुनः आरंभ सीमा के तहत समस्या का अध्ययन किया, लेकिन यह इस पेपर के असीमित पुनः आरंभ मॉडल से भिन्न है

मुख्य योगदान

सामान्य मामले के लिए निचली सीमा स्थापित करना: साबित किया कि किसी भी नियतात्मक ऑनलाइन एल्गोरिदम का प्रतिस्पर्धा अनुपात कम से कम R₁ ≈ 1.4656 है, जहां R₁ समीकरण R₁³ - R₁² - 1 = 0 का वास्तविक मूल है
सुधारा हुआ एल्गोरिदम डिजाइन करना: इकाई प्रसंस्करण समय के मामले के लिए, Limited Largest Weight (LLW) एल्गोरिदम प्रस्तावित किया, जिसका प्रतिस्पर्धा अनुपात 1.3098 से बेहतर है
कसी हुई विश्लेषण प्रदान करना: इकाई प्रसंस्करण समय के मामले में निचली सीमा R₂ ≈ 1.2344 साबित किया, जहां R₂ समीकरण 4R₂³ - R₂² - 6 = 0 का वास्तविक मूल है
सैद्धांतिक ढांचे को पूर्ण करना: पुनः आरंभ के साथ शेड्यूलिंग समस्याओं के लिए एक व्यवस्थित विश्लेषण विधि प्रदान करना

विधि विवरण

कार्य परिभाषा

इनपुट: ऑनलाइन आने वाली कार्यों की एक श्रृंखला, प्रत्येक कार्य j के आगमन समय rj, प्रसंस्करण समय pj और भार wj हैं आउटपुट: एक शेड्यूलिंग योजना जो भारित अधिकतम समापन समय WCmax = max{wjCj} को कम करती है बाधाएं: कार्यों को पुनः आरंभ किया जा सकता है (शुरुआत से), लेकिन बाधित बिंदु से पुनः शुरू नहीं किया जा सकता

मुख्य एल्गोरिदम: Limited Largest Weight (LLW)

LLW एल्गोरिदम का मूल विचार लालची रणनीति (भारी कार्यों को प्राथमिकता देना) और समय दक्षता के बीच संतुलन खोजना है। एल्गोरिदम नियम इस प्रकार हैं:

प्रारंभिक चरण: पहला आने वाला कार्य तुरंत प्रसंस्करण शुरू करता है
निर्णय नियम:
- यदि समय t ≥ (2-R)/(R-1) ≈ 2.2279 पर कार्य शुरू होता है, तो LW एल्गोरिदम चलाएं और बाधा की अनुमति न दें
- यदि समय t < (2-R)/(R-1) पर कार्य शुरू होता है, तो LW एल्गोरिदम चलाएं और समय t' = (t+2)/R - 1 तक बाधा की अनुमति दें
LW-phase अवधारणा: समय t < (2-R)/(R-1) पर शुरू होने वाले कार्य के लिए, अंतराल (t, t') को LW-phase कहा जाता है
बाधा अपडेट: यदि समय ti पर बाधा होती है, तो t := ti अपडेट करें और t' की पुनः गणना करें

तकनीकी नवाचार बिंदु

समय सीमा डिजाइन: गणितीय विश्लेषण के माध्यम से महत्वपूर्ण समय बिंदु (2-R)/(R-1) निर्धारित करें, इससे पहले बाधा की अनुमति दें, उसके बाद प्रतिबंधित करें
गतिशील सीमा समायोजन: LW-phase का अंत समय बाधा समय के अनुसार गतिशील रूप से समायोजित होता है
प्रतिस्पर्धा अनुपात विश्लेषण: "good set" की अवधारणा के माध्यम से एल्गोरिदम के प्रतिस्पर्धा अनुपात का व्यवस्थित विश्लेषण करें

सैद्धांतिक विश्लेषण

निचली सीमा प्रमाण विधि

सामान्य मामले की सीमा (प्रमेय 1): प्रतिकूल उदाहरण का निर्माण:

समय 0: कार्य 1 आता है, w₁=1, p₁=1
समय r₂ = 1/(R₁(R₁-1)) - 1: कार्य 2 आता है, w₂=1/(R₁-1), p₂=0

केस विश्लेषण के माध्यम से साबित करें कि किसी भी एल्गोरिदम का प्रतिस्पर्धा अनुपात कम से कम R₁ ≈ 1.4656 है।

इकाई समय मामले की सीमा (प्रमेय 3): अधिक जटिल प्रतिकूल उदाहरण का निर्माण, जिसमें 4 कार्यों की श्रृंखला शामिल है, साबित करें कि प्रतिस्पर्धा अनुपात कम से कम R₂ ≈ 1.2344 है।

ऊपरी सीमा प्रमाण विधि

प्रमेय 2 का प्रमाण विरोधाभास और केस विश्लेषण का उपयोग करता है:

न्यूनतम प्रतिउदाहरण का अस्तित्व मान लें
"good set" अवधारणा परिभाषित करें
5 प्रमुख गुणों के माध्यम से सभी संभावित प्रतिउदाहरण स्थितियों को क्रमिक रूप से समाप्त करें

प्रमुख गुण शामिल हैं:

गुण 1: कार्य 1 समय s₁ पर आता है और तुरंत शुरू होता है
गुण 2: एक बाधित कार्य मौजूद है, और विशेष समय बाधाओं को संतुष्ट करता है
गुण 3-5: संभावित शेड्यूलिंग पैटर्न को क्रमिक रूप से सीमित करें

प्रायोगिक सेटअप

सैद्धांतिक सत्यापन विधि

यह पेपर मुख्य रूप से सैद्धांतिक कार्य है, प्रायोगिक सत्यापन के बजाय गणितीय प्रमाण का उपयोग करता है:

निचली सीमा निर्माण: प्रतिकूल उदाहरण का निर्माण और पैरामीटर अनुकूलन
कंप्यूटर सहायता: प्रतिकूल उदाहरण के पैरामीटर को अनुकूलित करने के लिए कंप्यूटर का उपयोग करें
सटीक विश्लेषण: समीकरण समूह को हल करके सटीक प्रतिस्पर्धा अनुपात सीमा प्राप्त करें

प्रमुख पैरामीटर

R₁ ≈ 1.4656: सामान्य मामले प्रतिस्पर्धा अनुपात निचली सीमा
R ≈ 1.3098: इकाई समय मामले LLW एल्गोरिदम प्रतिस्पर्धा अनुपात
R₂ ≈ 1.2344: इकाई समय मामले प्रतिस्पर्धा अनुपात निचली सीमा

मुख्य परिणाम

प्रतिस्पर्धा अनुपात परिणाम सारांश

समस्या भिन्नता	निचली सीमा	ऊपरी सीमा (एल्गोरिदम)	अंतराल
सामान्य मामला	1.4656	-	-
इकाई प्रसंस्करण समय	1.2344	1.3098 (LLW)	0.0754

मौजूदा कार्य के साथ तुलना

सुधार परिमाण: Li के परिणामों की तुलना में, इकाई प्रसंस्करण समय के मामले में (√5+1)/2 ≈ 1.618 से 1.3098 तक सुधार
सैद्धांतिक योगदान: पुनः आरंभ मॉडल के तहत पहली बार कसी हुई विश्लेषण प्रदान करना

एल्गोरिदम प्रदर्शन गारंटी

LLW एल्गोरिदम गारंटी देता है:

प्रतिस्पर्धा अनुपात 1.3098 से कम है
यह सीमा कसी हुई है (ऐसे उदाहरण मौजूद हैं जो इस अनुपात तक पहुंचते हैं)

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

सैद्धांतिक सीमाएं: पुनः आरंभ के साथ भारित अधिकतम समापन समय समस्या की प्रतिस्पर्धा अनुपात सीमाएं स्थापित करना
एल्गोरिदम डिजाइन: LLW एल्गोरिदम इकाई प्रसंस्करण समय के मामले में महत्वपूर्ण सुधार प्राप्त करता है
विश्लेषण विधि: प्रतिस्पर्धा अनुपात विश्लेषण के लिए एक व्यवस्थित ढांचा प्रदान करना

सीमाएं

अंतराल का अस्तित्व: इकाई प्रसंस्करण समय के मामले में अभी भी लगभग 0.075 का ऊपरी-निचली सीमा अंतराल मौजूद है
सामान्य मामला: सामान्य प्रसंस्करण समय के मामले के लिए, केवल निचली सीमा प्रदान की गई है, मेल खाने वाले ऊपरी सीमा एल्गोरिदम की कमी है
व्यावहारिक अनुप्रयोग: सैद्धांतिक विश्लेषण में वास्तविक अनुप्रयोग परिदृश्यों का सत्यापन नहीं है

भविष्य की दिशाएं

अंतराल को कम करना: एल्गोरिदम को और सुधारना या निचली सीमा बढ़ाकर सैद्धांतिक अंतराल को कम करना
सामान्य मामले एल्गोरिदम: सामान्य प्रसंस्करण समय के मामले के लिए 1.4656 के करीब प्रतिस्पर्धा अनुपात वाला एल्गोरिदम डिजाइन करना
मॉडल विस्तार: बहु-मशीन, समानांतर बैच प्रसंस्करण आदि अधिक जटिल शेड्यूलिंग वातावरण पर विचार करना

गहन मूल्यांकन

लाभ

सैद्धांतिक कठोरता: गणितीय प्रमाण पूर्ण है, तर्क स्पष्ट है
तकनीकी नवाचार: LLW एल्गोरिदम का डिजाइन चतुर है, लालची रणनीति और दक्षता विचार को संतुलित करता है
विश्लेषण गहराई: "good set" अवधारणा के माध्यम से एक व्यवस्थित विश्लेषण ढांचा प्रदान करता है
व्यावहारिक महत्व: पुनः आरंभ मॉडल कुछ वास्तविक अनुप्रयोग परिदृश्यों के अधिक करीब है

कमियां

सैद्धांतिक अभिविन्यास: व्यावहारिक अनुप्रयोग सत्यापन और प्रायोगिक मूल्यांकन की कमी है
बड़ा अंतराल: सामान्य मामले में ऊपरी सीमा एल्गोरिदम की कमी है
जटिलता: प्रमाण प्रक्रिया अपेक्षाकृत जटिल है, पठनीयता में सुधार की आवश्यकता है

प्रभाव

सैद्धांतिक योगदान: शेड्यूलिंग सिद्धांत में पुनः आरंभ मॉडल के लिए महत्वपूर्ण सैद्धांतिक आधार प्रदान करता है
पद्धति मूल्य: विश्लेषण विधि अन्य शेड्यूलिंग समस्याओं तक विस्तारित की जा सकती है
व्यावहारिक संभावना: क्लाउड कंप्यूटिंग, वास्तविक समय प्रणाली आदि क्षेत्रों में अनुप्रयोग संभावना है

लागू परिदृश्य

क्लाउड कंप्यूटिंग: वर्चुअल मशीन शेड्यूलिंग में कार्य पुनः आरंभ
वास्तविक समय प्रणाली: उच्च प्राथमिकता वाले कार्यों की पूर्वाधिकार शेड्यूलिंग
ऑपरेटिंग सिस्टम: प्रक्रिया शेड्यूलिंग में समय स्लाइस राउंड-रॉबिन तंत्र

संदर्भ

यह पेपर 20 संबंधित संदर्भों का हवाला देता है, जिसमें शेड्यूलिंग सिद्धांत के शास्त्रीय कार्य और नवीनतम प्रगति शामिल है, जो अनुसंधान के लिए एक मजबूत सैद्धांतिक आधार प्रदान करता है। प्रमुख संदर्भों में Graham आदि की शेड्यूलिंग समस्या वर्गीकरण प्रणाली, Li के ऑनलाइन शेड्यूलिंग एल्गोरिदम और Shmoys आदि के पुनः आरंभ मॉडल की अग्रणी कार्य शामिल हैं।

समग्र मूल्यांकन: यह सैद्धांतिक कंप्यूटर विज्ञान का एक उच्च गुणवत्ता वाला पेपर है, जो शेड्यूलिंग सिद्धांत क्षेत्र में महत्वपूर्ण योगदान देता है। हालांकि मुख्य रूप से सैद्धांतिक विश्लेषण पर केंद्रित है, लेकिन व्यावहारिक अनुप्रयोगों के लिए महत्वपूर्ण सैद्धांतिक मार्गदर्शन प्रदान करता है। पेपर का गणितीय विश्लेषण कठोर है, परिणाम महत्वपूर्ण शैक्षणिक मूल्य रखते हैं।