समानांतर मशीन शेड्यूलिंग

समानांतर मशीन शेड्यूलिंग क्या है?

समांतर मशीन शेड्यूलिंग में जॉब (कार्य) के एक समुच्चय को कई एक-समान मशीनों पर इस प्रकार आवंटित किया जाता है कि मेकस्पैन (कुल पूर्णता समय) या कुल विलंबता जैसे उद्देश्य न्यूनतम हो जाएँ। यह एकल-मशीन शेड्यूलिंग का विस्तार है और विनिर्माण, कंप्यूटिंग तथा लॉजिस्टिक्स में सामान्य बहु-मशीन परिवेशों पर लागू होता है।

LPT (सबसे लंबा प्रसंस्करण समय) नियम समांतर मशीनों पर मेकस्पैन न्यूनतम करने की एक सुविख्यात ह्यूरिस्टिक है: जॉब को घटते प्रसंस्करण समय के क्रम में छाँटें और प्रत्येक जॉब उस मशीन को सौंपें जो सबसे पहले उपलब्ध होती है। एक-समान मशीनों के लिए LPT इष्टतम के 4/3 गुने के भीतर मेकस्पैन की गारंटी देता है। अन्य नियम (SPT, EDD, WSPT) भिन्न उद्देश्यों का अनुकूलन करते हैं।

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

Formula: Makespan = max(Completion Time of all machines) Utilization = Σ Processing Time / (Makespan x m) Tardiness = max(0, Completion - Due Date) LPT: Assign longest job to earliest available machine SPT: Assign shortest job to earliest available machine

गणना उदाहरण

2 मशीनों पर LPT से 4 जॉब (p=8,6,5,3)। आवंटन: Job1(8)→M1, Job2(6)→M2, Job3(5)→M2 (भार 6→11), Job4(3)→M1 (भार 8→11)। मेकस्पैन = 11। उपयोग दर: M1=11/11=100%, M2=11/11=100%। पूर्णतः संतुलित। LPT के बिना (FCFS) मेकस्पैन=14 तक जा सकता था, वह भी खराब संतुलन के साथ।

इस कैलकुलेटर का उपयोग कब करें

• कई identical machines पर jobs का batch scheduling करते समय और makespan या total tardiness न्यूनतम करने की आवश्यकता हो
• क्षमता योजना के दौरान यह मूल्यांकन करने के लिए कि machine जोड़ने से वर्तमान workload के लिए makespan में सार्थक कमी आएगी
• अपने विशिष्ट job mix के लिए dispatching नियमों की तुलना करते समय
• machine खराब होने के बाद शेष jobs को उपलब्ध machines पर शीघ्र पुनः schedule करने और delivery प्रभाव का आकलन करने के लिए
• machines पर load संतुलित करने और idle time न्यूनतम करने के लिए

बचने योग्य सामान्य गलतियाँ

• makespan न्यूनतम करने के लिए SPT का उपयोग — SPT average flow time न्यूनतम करता है, makespan नहीं; parallel machines पर makespan के लिए LPT का उपयोग करें
• यह मानना कि अधिक machines हमेशा makespan को आनुपातिक रूप से कम करती हैं — सुधार diminishing returns के नियम का पालन करता है
• jobs अलग-अलग समय पर आने पर release times पर विचार न करना — static dispatching नियम सभी jobs समय शून्य पर उपलब्ध मानते हैं
• machine utilization balance की अनदेखी — न्यूनतम makespan वाला schedule कुछ machines को लंबे समय तक idle छोड़ सकता है

परिणामों की व्याख्या कैसे करें

• सभी machines पर समान utilization (>90% प्रत्येक) — load अच्छी तरह संतुलित है; dispatching नियम कुशलता से काम कर रहा है
• एक machine 100% utilization पर जबकि अन्य काफी कम — वह machine bottleneck है; सबसे लंबा job संभवतः makespan निर्धारित करता है
• Total tardiness = 0 — सभी jobs अपनी due dates से पहले समाप्त होते हैं
• कई tardy jobs के साथ उच्च total tardiness — workload due date window के भीतर capacity से अधिक है
• LPT और SPT बहुत समान makespan देते हैं — job processing times अपेक्षाकृत समान हैं

संबंधित मानक और संदर्भ

• APICS CPIM Body of Knowledge — उत्पादन गतिविधि नियंत्रण module के भीतर parallel machine scheduling concepts को कवर करता है
• ISA-95 (IEC 62264) — विस्तृत machine-level scheduling सहित scheduling levels परिभाषित करने वाला enterprise-control system एकीकरण मानक

अक्सर पूछे जाने वाले प्रश्न

समांतर मशीनों पर मेकस्पैन किस डिस्पैचिंग नियम से न्यूनतम होता है?

मेकस्पैन न्यूनतम करने के लिए LPT (सबसे लंबा प्रसंस्करण समय पहले) सर्वोत्तम ह्यूरिस्टिक है। सबसे लंबे जॉब पहले आवंटित करने से यह सुनिश्चित होता है कि बड़े जॉब अंत में अड़चन न बनें। LPT इष्टतम के 4/3 - 1/(3m) गुने के भीतर समाधान की गारंटी देता है, जहाँ m मशीनों की संख्या है। 2 मशीनों के लिए यह इष्टतम के 7/6 (≈17%) के भीतर रहता है।

भिन्न रिलीज़ समय या नियत तिथियों वाले जॉब को कैसे संभालें?

रिलीज़ समय होने पर जॉब अपने रिलीज़ समय के बाद ही शुरू हो सकते हैं — ऐसी गतिशील डिस्पैचिंग अपनाएँ जो प्रत्येक मशीन के उपलब्ध होते ही प्राथमिकताओं का पुनर्मूल्यांकन करे। नियत तिथियाँ होने पर EDD या CR नियम विलंबता घटाने में सहायक होते हैं। दोनों बाध्यताओं वाली जटिल समस्याओं के लिए कई नियमों का अनुकरण करके निष्पादन मापदंडों की तुलना करें। सर्वोत्तम नियम विशिष्ट जॉब-मिश्रण और उद्देश्य पर निर्भर करता है।