🔢 mathematics

Near-optimal scheduling with general service times and IHR abandonment times

यह शोध पत्र सामान्य सेवा समय और IHR परित्याग समय (abandonment times) वाले M/G/N कतार (queue) में गतिशील शेड्यूलिंग समस्या को संबोधित करता है, जो संबंधित डिस्क्रीट-टाइम समस्या की इंडेक्सेबिलिटी (indexability) को सिद्ध करके, एक स्पष्ट व्हिटल इंडेक्स (Whittle index) व्युत्पन्न करके, और सिमुलेशन के माध्यम से यह प्रदर्शित करके कि परिणामी नीति मानक $c\mu/\theta$ -नियम से व्यवस्थित रूप से बेहतर प्रदर्शन करती है।

मूल लेखक: Samuli Aalto

प्रकाशित 2026-07-28

📖 8 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Samuli Aalto

मूल पेपर CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

एक व्यस्त कॉफी शॉप की कल्पना करें जहाँ ग्राहक अपनी ड्रिंक पाने के लिए कतार में लगे हैं, लेकिन इसमें एक ट्विस्ट है: हर ग्राहक के पास एक गुप्त टाइमर है। यदि वे बहुत लंबे समय तक प्रतीक्षा करते हैं, तो वे निराश होकर बिना कुछ खरीदे चले जाते हैं। बरिस्ता (सर्वर) को यह तय करना होता है कि अगली बारी में किसे सेवा देनी है। क्या उन्हें उस व्यक्ति को सेवा देनी चाहिए जो सबसे लंबे समय से प्रतीक्षा कर रहा है? या उस व्यक्ति को जिसे केवल एक त्वरित एस्प्रेसो चाहिए? या उस व्यक्ति को जो बस हार मानने ही वाला है और जाने ही वाला है? यह एक समस्या के केंद्र में है जिसे "शेड्यूलिंग" (scheduling) कहा जाता है, जो गणित और कंप्यूटर विज्ञान की एक शाखा है जो यह निर्धारित करती है कि जब संसाधन सीमित हों और समय बीत रहा हो, तो कार्यों को व्यवस्थित करने का सबसे अच्छा तरीका क्या है।

शेड्यूलिंग की दुनिया में, चिंता करने के लिए दो मुख्य प्रकार के लागत (costs) होते हैं। पहला है "होल्डिंग कॉस्ट" (holding cost), जो कतार में प्रतीक्षा करते समय खोई हुई ऊर्जा और धैर्य की तरह है। दूसरा है "एबंडनमेंट पेनल्टी" (abandonment penalty), जो एक खोई हुई बिक्री और खराब प्रतिष्ठा है जब कोई ग्राहक गुस्से में चला जाता है। दशकों तक, गणितज्ञों ने इस पहेली को हल करने का प्रयास किया है, लेकिन उन्होंने आमतौर पर एक बड़ा सरलीकरण किया: उन्होंने माना कि सेवा समय (ड्रिंक बनने में लगने वाला समय) और धैर्य का समय (ग्राहक कितनी देर प्रतीक्षा करता है) एक सरल, अनुमानित पैटर्न जिसे "एक्सपोनेंशियल डिस्ट्रीब्यूशन" (exponential distribution) कहा जाता है, का पालन करते हैं। इसे ऐसे समझें जैसे मान लेना कि हर सिक्का उछालना पूरी तरह से यादृच्छिक और स्वतंत्र है। हालांकि यह गणित को आसान बनाता है, लेकिन यह वास्तविक जीवन को नहीं दर्शाता है, जहाँ कुछ कार्यों में बहुत लंबा समय लगता है और कुछ लोग अविश्वसनीय रूप से धैर्यवान या अविश्वसनीय रूप से अधीर होते हैं।

यह शोध पत्र, जिसे सामुली आल्टो (Samuli Aalto) द्वारा लिखा गया है, इस समस्या के अव्यवस्थित, वास्तविक दुनिया वाले संस्करण को संबोधित करता है। सरल, अनुमानित पैटर्न मानने के बजाय, लेखक किसी भी प्रकार के सेवा समय (जैसे कि एक जटिल लाटे जिसमें बहुत समय लगता है) और एक विशिष्ट प्रकार की अधीरता जिसे "IHR" (Increasing Hazard Rate) कहा जाता है, की अनुमति देता है। IHR एक फैंसी तरीका है यह कहने का कि आप जितना अधिक प्रतीक्षा करते हैं, आपके छोड़ने की संभावना उतनी ही बढ़ जाती है—ठीक वैसे ही जैसे एक वास्तविक इंसान धीरे चलती लाइन के कारण अधिक क्रोधित होता है। यह शोध पत्र "व्हिटल इंडेक्स" (Whittle index) नामक एक चतुर गणितीय उपकरण का उपयोग करता है ताकि यह तय किया जा सके कि किसे पहले सेवा दी जाए। मुख्य निष्कर्ष यह है कि यह नई विधि, जो इन जटिल, वास्तविक दुनिया के परिदृश्यों को संभालती है, कंप्यूटर सिमुलेशन में पुराने मानक नियम (जिसे $c\mu/\theta$ -rule कहा जाता है) को लगातार मात देती है। लेखक यह सिद्ध करते हैं कि उनका नया फॉर्मूला समस्या के एक सरलीकृत संस्करण के लिए गणितीय रूप से सटीक है और फिर वे सिमुलेशन के माध्यम से दिखाते हैं कि यह पुराने सर्वोत्तम तरीकों की तुलना में अधिक पैसा बचाता है और अधिक ग्राहकों को खुश रखता है।

अधीर कतार की कहानी

एक अराजक हवाई अड्डे की सुरक्षा कतार की कल्पना करें। आपके पास सुरक्षा अधिकारियों (सर्वर) की एक टीम है और यात्रियों (ग्राहकों) की एक धारा है। प्रत्येक यात्री के पास दो अदृश्य घड़ियाँ चल रही हैं। एक घड़ी उनके सेवा समय (service time) को गिनती है—उनका बैग स्कैन करने और उनकी आईडी जांचने में कितना समय लगता है। दूसरी घड़ी उनके धैर्य के समय (patience time) को गिनती है—वे उड़ान छोड़ने और घर जाने का निर्णय लेने से पहले कितनी देर वहां खड़े रहने के लिए तैयार हैं।

पुराने दिनों में, इस लाइन का मॉडल बनाने वाले गणितज्ञों ने माना था कि दोनों घड़ियाँ एक बहुत ही विशिष्ट, "मेमोरीलेस" (memoryless) तरीके से कम होती हैं। यह यह कहने जैसा था कि चाहे आप कितनी भी देर से खड़े हों, अगले मिनट में आपके जाने की संभावना उतनी ही है जितनी कि आपके आगमन के समय थी। यह "एक्सपोनेंशियल" (exponential) धारणा है। यह गणित के लिए एक अच्छी ट्रिक है, लेकिन यह वास्तविक लोगों के व्यवहार को नहीं दर्शाती है। वास्तव में, यदि आप 20 मिनट से प्रतीक्षा कर रहे हैं, तो अगले मिनट में आपके जाने की संभावना उस व्यक्ति की तुलना में बहुत अधिक है जो अभी-अभी आया है। यह वही है जिसे शोध पत्र IHR (Increasing Hazard Rate) कहता है: आप जितना अधिक प्रतीक्षा करते हैं, आपके छोड़ने का जोखिम उतना ही बढ़ जाता है।

लेखक ने यह भी महसूस किया कि वास्तविक सेवा समय हमेशा सरल नहीं होता है। कभी-कभी बैग स्कैन तुरंत हो जाता है; अन्य बार इसमें बहुत समय लगता है क्योंकि सूटकेस का लॉक अजीब होता है। यह शोध पत्र सामान्य सेवा समय (general service times) की अनुमति देता है, जिसका अर्थ है कि गणित प्रतीक्षा समय के किसी भी आकार को संभाल सकता है, चाहे वह त्वरित और आसान हो या लंबा और जटिल।

जादुई फॉर्मूला: व्हिटल इंडेक्स

तो, आप यह कैसे तय करते हैं कि किसे सेवा देनी है? शोध पत्र प्रत्येक व्यक्ति के लिए एक स्कोरकार्ड के रूप में "व्हिटल इंडेक्स" (Whittle index) पेश करता है। यह स्कोर केवल इस बारे में नहीं है कि कोई व्यक्ति कितने समय से प्रतीक्षा कर रहा है। यह एक जटिल गणना है जो निम्नलिखित को देखती है:

उन्होंने पहले से कितना इंतज़ार किया है (x)।
उन्हें पहले से कितनी सेवा मिल चुकी है (y)।
उन्हें प्रतीक्षा कराने की लागत कितनी है (holding cost)।
उनके जाने से कितनी लागत आती है (abandonment penalty)।

लेखक सिद्ध करते हैं कि इस समस्या के एक सरलीकृत संस्करण (एक "बंद" प्रणाली जहाँ नए लोग नहीं आते) के लिए, यह स्कोरकार्ड गणितीय रूप से पूर्ण है। यह "इंडेक्सेबल" (indexable) है, जो एक फैंसी तरीका है यह कहने का कि आप सभी को "अभी मेरी सेवा करो!" से लेकर "मैं थोड़ा इंतजार करूँगा" तक रैंक कर सकते हैं।

शोध पत्र फिर इस स्कोरकार्ड को वास्तविक, निरंतर दुनिया के लिए अनुकूलित करता है जहाँ लोग लगातार आ रहे हैं। परिणामी फॉर्मूला, $W_k(x, y)$ , देखने में थोड़ा डरावना लग सकता है, लेकिन यह मूल रूप से पूछता है: "यदि मैं इस व्यक्ति को थोड़े से समय के लिए सेवा देता हूँ, तो मैं उनके जाने के जोखिम की तुलना में कितना पैसा बचाऊंगा?"

मुकाबला: नया बनाम पुराना

यह देखने के लिए कि क्या यह नया "व्हिटल इंडेक्स पॉलिसी" (WHI) वास्तव में काम करता है, लेखक ने हजारों कंप्यूटर सिमुलेशन चलाए। उन्होंने दो प्रकार के यात्रियों के साथ एक वर्चुअल एयरपोर्ट बनाया:

क्लास 1: छोटे कार्य (त्वरित स्कैन) लेकिन अलग-अलग स्तर का धैर्य।
क्लास 2: लंबे कार्य (जटिल स्कैन) अलग-अलग धैर्य स्तरों के साथ।

उन्होंने सेवा समय के प्रकारों (कुछ यूनिफॉर्म थे, कुछ "पारेटो" (Pareto) थे जिसका अर्थ है कि कुछ लोग बहुत लंबे समय तक लेते हैं) और त्याग की लागत (कभी ग्राहकों को खोना सस्ता होता है, कभी यह एक बहुत बड़ा नुकसान होता है) को मिलाते हुए चार अलग-अलग परिदृश्यों का परीक्षण किया।

परिणाम स्पष्ट थे। नई व्हिटल इंडेक्स नीति ने पुराने मानक, जिसे $c\mu/\theta$ -rule कहा जाता है, को व्यवस्थित रूप से पछाड़ दिया।

"यूनिफॉर्म-यूनिफॉर्म" परिदृश्य में (जहाँ सभी कुछ हद तक अनुमानित हैं), नई नीति ने पुराने नियम की तुलना में लागत में लगभग 12% से 19% अधिक बचत की।
"यूनिफॉर्म-पारेटो" परिदृश्य में (जहाँ कुछ लोगों के सेवा समय बहुत लंबे और अप्रत्याशित होते हैं), अंतर और बढ़ गया। नई नीति ने पुराने नियम की तुलना में 33% से 42% अधिक बचत की।
सबसे कठिन परिदृश्यों में भी, नई नीति लगातार बेहतर थी, कभी-कभी 52% तक अधिक।

शोध पत्र ने अन्य सामान्य रणनीतियों जैसे "फर्स्ट-कम-फर्स्ट-सर्व्ड" (सबसे पुराने व्यक्ति को पहले सेवा देना) और "प्रोसेसर-शेयरिंग" (सभी के बीच सर्वर का समय समान रूप से बांटना) के साथ भी इसकी तुलना की। नया व्हिटल इंडेक्स उन सभी को हरा देता है।

यह क्यों मायने रखता है

मुख्य बात यह है कि "परफेक्टली रैंडम" धारणाओं को छोड़कर और यह स्वीकार करके कि लोग वास्तव में कैसे अधीर होते हैं, हम बहुत बेहतर सिस्टम बना सकते हैं। चाहे वह कॉफी शॉप हो, कॉल सेंटर हो, या डेटा प्रोसेस करने वाला कंप्यूटर नेटवर्क, इस नए फॉर्मूले का उपयोग करने का अर्थ है—कम नाराज ग्राहक, कम बर्बाद समय और अधिक पैसा बचाना। लेखक ने केवल अनुमान नहीं लगाया; उन्होंने सिद्ध किया कि गणित सरलीकृत संस्करण के लिए काम करता है और सिमुलेशन के माध्यम प्रकार से दिखाया कि यह जटिल, वास्तविक दुनिया के संस्करण में चमत्कार करता है। यह एक याद दिलाता है कि कभी-कभी, समस्या को हल करने का सबसे अच्छा तरीका यह है कि दुनिया को वास्तव में सरल होने का नाटक करना बंद कर दिया जाए।

तकनीकी सारांश: सामान्य सेवा समय और IHR परित्याग समय के साथ निकट-इष्टतम शेड्यूलिंग

समस्या विवरण
यह शोध पत्र एक बहु-वर्ग $M/G/N$ कतार प्रणाली (queueing system) के भीतर गतिशील शेड्यूलिंग समस्या को संबोधित करता है जिसमें अधीमी ग्राहक (impatient customers) शामिल हैं। इस प्रणाली में $N$ समरूप समानांतर सर्वर और कई ग्राहक वर्ग होते हैं। प्रत्येक ग्राहक का एक यादृच्छिक (random) सेवा समय और एक यादृच्छिक परित्याग (abandonment) समय होता है; यदि कोई ग्राहक अपने परित्याग समय से अधिक समय तक प्रणाली (प्रतीक्षा या सेवा के दौरान) में रहता है, तो वह सेवा पूर्ण होने से पहले ही सिस्टम छोड़ देता है।

इसका उद्देश्य एक गैर-पूर्वानुमानित (non-anticipating) शेड्यूलिंग नीति (प्रीएम्प्शन की अनुमति के साथ) निर्धारित करना है जो कुल अपेक्षित लागत को कम करती है। इस लागत फलन (cost function) में दो घटक शामिल हैं:

होल्डिंग लागत (Holding costs): जब तक वर्ग- $k$ के ग्राहक प्रणाली में रहते हैं, तब तक $h_k$ की दर से अर्जित होती है।
परित्याग दंड (Abandonment penalties): एक एकमुश्त दंड $d_k$ जो तब लगता है जब वर्ग- $k$ का कोई ग्राहक सेवा पूर्ण होने से पहले प्रणाली छोड़ देता है।

मौजूदा साहित्य अक्सर सेवा और परित्याग दोनों के लिए घातांकीय (exponential) वितरणों को मानता है, लेकिन विशेष मामलों को छोड़कर सटीक समाधान मिलना कठिन है। पिछले निकट-इष्टतम दृष्टिकोण, जैसे कि $c\mu/\theta$ -नियम प्रदान करने वाले फ्लुइड-स्केलिंग तरीके, अत्यधिक प्रतिबंधात्मक घातांकीय धारणाओं पर बहुत अधिक निर्भर करते हैं। यह शोध पत्र समस्या को सामान्य बनाने का लक्ष्य रखता है, जिससे सामान्य सेवा समय वितरण और बढ़ते खतरा दर (Increasing Hazard Rate - IHR) वाले परित्याग समय को शामिल किया जा सके, जो कि एक स्वाभाविक धारणा है जहाँ प्रणाली में बिताए गए समय के साथ परित्याग की संभावना बढ़ जाती है।

कार्यप्रणाली (Methodology)
लेखक व्हिटल इंडेक्स (Whittle index) दृष्टिकोण का उपयोग करते हैं, जो मूल रूप से रेस्टलेस बैंडिट समस्याओं (restless bandit problems) के लिए डिज़ाइन किया गया एक ह्यूरिस्टिक तरीका है, जो आम तौर पर गणितीय रूप से जटिल होती हैं। कार्यप्रणाली निम्नलिखित चरणों में आगे बढ़ती है:

वि диск्रीट-टाइम फॉर्मूलेशन (Discrete-Time Formulation): समस्या को पहले डिस्काउंटेड लागतों के साथ डिस्क्रीट-टाइम में मॉडल किया जाता है। विश्लेषण को सुगम बनाने के लिए सिस्टम को एक बंद संस्करण (सीमित संख्या में ग्राहक, कोई नए आगमन नहीं) के रूप में माना जाता है। एक ग्राहक की स्थिति को एक द्वि-आयामी युग्म $(x, y)$ द्वारा परिभाषित किया जाता है, जहाँ $x$ प्रणाली में बिताया गया कुल समय है और $y$ प्राप्त की गई सेवा है।
रिलैक्सेशन और इंडेक्सेबिलिटी (Relaxation and Indexability): सख्त क्षमता बाधा (अधिकतम $N$ ग्राहकों को सेवा देना) को एक समय-औसत बाधा में बदल दिया जाता है। यह समस्या को पृथक उप-समस्याओं (प्रत्येक ग्राहक के लिए एक) में परिवर्तित कर देता है। लेखक सिद्ध करते हैं कि यह शिथिल (relaxed) समस्या इंडेक्सेबल (indexable) है, जिसका अर्थ है कि "कार्य की कीमत" $\nu$ के लिए एक थ्रेशोल्ड (व्हिटल इंडेक्स) मौजूद है, जिससे यह इष्टतम होता है कि किसी ग्राहक को तब तक सेवा दी जाए जब तक उनका इंडेक्स $\nu$ से अधिक हो।
इंडेक्स का व्युत्पन्न (Derivation of the Index): एक महत्वपूर्ण सैद्धांतिक चुनौती द्वि-आयामी अवस्था स्थान (state space) है, जिसमें एक-आयामी समस्याओं की तरह स्वाभाविक क्रम का अभाव होता है। लेखक डिस्क्रीट-टाइम सेटिंग में व्हिटल इंडेक्स का एक स्पष्ट व्यंजक व्युत्पन्न करते हैं, जिसे $W_{k,\beta}(x, y)$ के रूप में दर्शाया गया है, जिसमें $\Delta$ के समय क्षितिज (time horizon) पर मैक्सिमाइजेशन शामिल है।
निरंतर-समय सीमा (Continuous-Time Limit): डिस्क्रीट-टाइम परिणामों को मूल निरंतर-समय ओपन सिस्टम के लिए विस्तारित किया जाता है। जैसे-जैसे टाइम स्लॉट शून्य की ओर बढ़ता है और प्रायिकताएं स्केल होती हैं, लेखक निरंतर-समय व्हिटल इंडेक्स $W_k(x, y)$ व्युत्पन्न करते हैं।

प्रमुख योगदान

धारणाओं का सामान्यीकरण: यह शोध पत्र प्रतिबंधात्मक घातांकीय सेवा समय की धारणा को हटा देता है, जिससे सामान्य वितरणों को शामिल किया जा सके, जबकि परित्याग समय के लिए IHR का उपयोग किया गया है।
इंडेक्सेबिलिटी का सैद्धांतिक प्रमाण: लेखक सिद्ध करते हैं कि बंद डिस्क्रीट-टाइम संस्करण इंडेक्सेबल है। द्वि-आयामी अवस्था स्थान $(x, y)$ के कारण यह एक गैर-तुच्छ परिणाम है, क्योंकि यह मानक प्रमाणों को जटिल बनाता है जो अवस्था क्रम (state ordering) पर निर्भर करते हैं।
स्पष्ट इंडेक्स फॉर्मूला: सामान्य मामले के लिए एक स्पष्ट व्यंजक व्युत्पन्न किया गया है:
$W_k(x, y) = \sup_{\Delta>0} \frac{E\left[ (h_k((D_k - x) - (S_k - y)) + d_k) \mathbb{1}_{\{S_k - y < \min\{D_k - x, \Delta\}\}} \mid D_k > x, S_k > y \right]}{E[\min\{D_k - x, S_k - y, \Delta\} \mid D_k > x, S_k > y]}$
शोध पत्र यह भी पहचानता है कि किन विशिष्ट स्थितियों में यह इंडेक्स ज्ञात रूपों में सरल हो जाता है (जैसे, जब सेवा समय घटती खतरा दर (DHR) हो या जब परित्याग समय घातांकीय हो)।
नीति परिभाषा (Policy Definition): निरंतर-समय सेटिंग के लिए एक व्हिटल इंडेक्स नीति (WHI) को परिभाषित किया गया है: किसी भी समय $t$ पर, शेड्यूलर उन $N$ ग्राहकों को सेवा देता है जिनके व्हिटल इंडेक्स सबसे अधिक होते हैं।

परिणाम
प्रस्तावित व्हिटल इंडेक्स नीति (WHI) के प्रदर्शन का मूल्यांकन एक दो-वर्ग $M/G/1$ कतार में प्रसिद्ध $c\mu/\theta$ -नियम (CMTH) और अन्य मानक नीतियों (FCFS, प्रोसेसर-शेयरिंग, फॉरवर्ड-बैकवर्ड) के विरुद्ध संख्यात्मक सिमुलेशन के माध्यम से किया गया है।

व्यवस्थित श्रेष्ठता: विभिन्न प्रयोगिक सेटअपों में, जिनमें सेवा समय वितरण (यूनिफॉर्म/IHR और पारेटो/DHR) और लागत संरचनाओं के विभिन्न संयोजन शामिल हैं, WHI नीति व्यवस्थित रूप से $c\mu/\theta$ -नियम और अन्य बेसलाइन नीतियों से बेहतर प्रदर्शन करती है।
वितरण के आकार के प्रति संवेदनशीलता: सिमुलेशन दर्शाते हैं कि जब सेवा समय हेवी-टेल्ड (DHR) वितरण (जैसे पारेटो) का पालन करता है, तो WHI और CMTH के बीच प्रदर्शन का अंतर काफी बढ़ जाता है। इन परिदृश्यों में, $c\mu/\theta$ -नियम, जो घातांकीय सेवा समय मानता है, काफी खराब प्रदर्शन कर सकता है (उदाहरण के लिए, कुछ भारी-लोड परिदृश्यों में सापेक्ष लागत अंतर 40-50% से अधिक हो सकता है)।
मजबूती (Robustness): WHI नीति चाहे परित्याग लागत पर जोर दिया गया हो या होल्डिंग लागत पर, और विभिन्न सिस्टम लोड ( $\rho \in [1.0, 2.0]$ ) के तहत, श्रेष्ठ प्रदर्शन बनाए रखती है।

महत्व
यह शोध पत्र दावा करता है कि इसका प्राथमिक महत्व एक अधिक यथार्थवादी और जटिल शेड्यूलिंग वातावरण में व्हिटल इंडेक्स दृष्टिकोण की प्रयोज्यता को विस्तारित करना है। सामान्य सेवा समय और IHR परित्याग के लिए इंडेक्सेबिलिटी को सिद्ध करके और इंडेक्स व्युत्पन्न करके, यह कार्य उन समस्याओं के लिए एक सैद्धांतिक रूप से सुदृढ़ ह्यूरिस्टिक प्रदान करता है जहाँ सटीक समाधान उपलब्ध नहीं हैं। संख्यात्मक परिणाम बताते हैं कि घातांकीय धारणाओं (जैसा कि $c\mu/\theta$ -नियम में है) पर भरोसा करना, विशेष रूप से जब सेवा समय गैर-घातांकीय हो, उप-इष्टतम शेड्यूलिंग निर्णयों की ओर ले जा सकता है, और व्युत्पन्न व्हिटल इंडेक्स नीति एक मजबूत, निकट-इष्टतम विकल्प प्रदान करती है।

अधीर कतार की कहानी

जादुई फॉर्मूला: व्हिटल इंडेक्स

मुकाबला: नया बनाम पुराना

यह क्यों मायने रखता है

इसी तरह के और पेपर