Longest-processing-time-first scheduling
लॉंगेस्ट-प्रोसेसिंग-टाइम-फर्स्ट (एल. पी. टी.) नौकरी के समय निर्धारण के लिए एक लालची एल्गोरिदम है। एल्गोरिदम के लिए इनपुट नौकरियों का एक समूह है, जिनमें से प्रत्येक का एक विशिष्ट प्रसंस्करण-समय होता है। एक संख्या एम भी है जो मशीनों की संख्या को निर्दिष्ट करती है जो कार्यों को संसाधित कर सकती हैं। एल. पी. टी. एल्गोरिदम इस प्रकार काम करता हैः कार्यों को उनके प्रसंस्करण-समय के अवरोही क्रम से क्रमबद्ध करें, जैसे कि सबसे लंबे प्रसंस्करण समय वाला कार्य पहला हो। इस क्रम में प्रत्येक कार्य को एक मशीन में निर्धारित करें जिसमें वर्तमान भार (= अनुसूचित कार्यों का कुल प्रसंस्करण-समय) सबसे छोटा हो। एल्गोरिथम का चरण 2 अनिवार्य रूप से सूची-निर्धारण (एल. एस.) एल्गोरिथम है। अंतर यह है कि एल. एस. एक मनमाने क्रम में नौकरियों पर लूप करता है, जबकि एल. पी. टी. उन्हें घटते प्रसंस्करण समय द्वारा पूर्व-आदेश देता है। एल. पी. टी. का पहली बार 1960 के दशक में रोनाल्ड ग्राहम द्वारा समान-मशीन समय निर्धारण समस्या के संदर्भ में विश्लेषण किया गया था। बाद में, इसे समस्या के कई अन्य रूपों पर लागू किया गया। एल. पी. टी. को बहु-मार्ग संख्या विभाजन के लिए एक एल्गोरिथ्म के रूप में अधिक अमूर्त तरीके से भी वर्णित किया जा सकता है। इनपुट संख्याओं का एक सेट S है, और एक सकारात्मक पूर्णांक m है; आउटपुट S का m सबसेट में विभाजन है। एल. पी. टी. इनपुट को सबसे बड़े से लेकर सबसे छोटे तक का ऑर्डर देता है, और प्रत्येक इनपुट को अब तक की सबसे छोटी राशि वाले हिस्से में डालता है। उदाहरण यदि इनपुट समुच्चय S = {4,5,6,7,8} और m = 2 है, तो परिणामी विभाजन {8,5,4}, {7,6} है। यदि m = 3 है, तो परिणामी 3-तरफा विभाजन {8}, {7,4}, {6,5} है। गुण एल. पी. टी. को इष्टतम विभाजन नहीं मिल सकता है। उदाहरण के लिए, उपरोक्त उदाहरण में इष्टतम विभाजन {8,7}, {6,5,4}, जहां दोनों योग 15 के बराबर हैं। हालाँकि, इसकी उप-अनुकूलता सबसे खराब स्थिति और औसत स्थिति दोनों में सीमित है; नीचे प्रदर्शन की गारंटी देखें। एल. पी. टी. के चलने के समय में छँटाई का प्रभुत्व होता है, जिसमें ओ (एन लॉग एन) समय लगता है, जहाँ एन निवेशों की संख्या है। प्रदर्शन की गारंटीः समान मशीनें जब समान-मशीनों के समय निर्धारण के लिए उपयोग किया जाता है, तो एल. पी. टी. निम्नलिखित सन्निकटन अनुपात प्राप्त करता है। सबसे खराब स्थिति में अधिकतम राशि सबसे खराब स्थिति में, लालची विभाजन में सबसे बड़ी राशि ज्यादातर समय इष्टतम (न्यूनतम) सबसे बड़ी राशि होती है। एक अधिक विस्तृत विश्लेषण इष्टतम (न्यूनतम) सबसे बड़ी राशि के गुना का एक कारक देता है। (उदाहरण के लिए, जब m = 2 यह अनुपात है)। कारक कड़ा है। मान लीजिए कि कुछ निवेश हैं (जहाँ m सम है): फिर लालची एल्गोरिथ्म लौटता हैः,. अधिकतम के साथ, लेकिन इष्टतम विभाजन हैः. अधिकतम के साथ है। निवेश पर विचार एक और अधिक विस्तृत विश्लेषण अधिकतम-राशि भाग में निवेश की संख्या को ध्यान में रखता है। लालची विभाजन के प्रत्येक भाग में, जे-th सबसे अधिक संख्या है। मान लीजिए कि लालची भाग पी में अधिकतम राशि के साथ एल निवेश हैं। फिर, लालची एल्गोरिथ्म का सन्निकटन अनुपात है। यह L ≤ 3 के लिए तंग है (L = 3 के लिए, हमें सामान्य कारक मिलता है)। सबूत। पी में संख्याओं को x1,., xL से निरूपित करें। पी में एक्सएल डालने से पहले, इसका योग सबसे छोटा था। इसलिए, प्रति भाग औसत योग कम से कम x1 +. + xL-1 + xL/m है। इष्टतम अधिकतम राशि कम से कम औसत राशि होनी चाहिए। इसके विपरीत, लालची राशि x1 +. + xL-1 + xL है। इसलिए अंतर अधिक से अधिक (1-1/मीटर) xL है, जो (1) से अधिक से अधिक (1-1/मीटर) * ऑप्ट/एल है। अतः अनुपात अधिक से अधिक (1 + 1/L-1/Lm) है। सबसे खराब स्थिति न्यूनतम राशि सबसे खराब स्थिति में, वापस किए गए विभाजन में सबसे छोटी राशि कम से कम इष्टतम (अधिकतम) सबसे छोटी राशि होती है। सबूत विरोधाभास से होता है। हम एक न्यूनतम प्रति-उदाहरण पर विचार करते हैं, जो कि सबसे छोटी m और सबसे कम इनपुट संख्या के साथ एक प्रति-उदाहरण है। लालची विभाजन को पी1,., पी. एम. द्वारा और इष्टतम विभाजन को क्यू1,., क्यू. एम. द्वारा दर्शाएँ। न्यूनतम प्रति-उदाहरण के कुछ गुण हैंः इष्टतम विभाजन में न्यूनतम राशि 4 है, और लालची विभाजन में न्यूनतम राशि 3 से कम है (यह केवल सामान्यीकरण है-यह सामान्यता के नुकसान के बिना है)। लालची विभाजन में अधिकतम राशि 4 से अधिक है (क्योंकि दोनों विभाजनों में कुल राशि समान है, और यह कम से कम 4 मीटर है)। यदि किसी लालची बिन पाई के लिए योग (पी. आई.) 3 है, तो पी. आई. पर किसी भी इष्टतम बिन क्यू. जे. का प्रभुत्व नहीं है। प्रमाणः यदि पाई में क्यूजे का प्रभुत्व है, तो हम एम को एम-1 तक घटाकर और पाई में वस्तुओं को हटाकर एक छोटे से प्रति-उदाहरण का निर्माण कर सकते हैं। लालची विभाजन में न्यूनतम राशि 3 से कम रहती है। इष्टतम विभाजन में, पाई में वस्तुओं को क्यूजे में उनकी प्रमुख वस्तुओं द्वारा प्रतिस्थापित किया जा सकता है, इसलिए न्यूनतम राशि कम से कम 4 बनी रहती है। यदि किसी लालची बिन पाई के लिए योग (पी. आई.) 3 है, तो पी. आई. में कम से कम दो संख्याएँ होती हैं। प्रमाणः यदि पाई में केवल एक संख्या x है, तो इसमें इष्टतम बिन क्यूजे का प्रभुत्व है जिसमें x.givese कुछ इनपुट एक्स कम से कम 3 है, और लालची एल्गोरिथ्म इसे किसी पाई में रखता है। फिर, चूंकि 3 से कम राशि वाला एक बंडल है, लालची एल्गोरिथ्म पिछले लेम्मा के विपरीत पाई में कोई अन्य इनपुट नहीं देगा। प्रत्येक लालची बिन पाई में अधिकतम एक इनपुट होता है जो 3/2 से कमजोर रूप से बड़ा होता है। प्रमाणः माना कि पाई पहला लालची बिन है जिसे इस तरह के दो इनपुट दिए गए हैं। चूंकि इनपुट को अवरोही क्रम में सौंपा जाता है, इसलिए पाई पहला लालची बिन है जिसे दो इनपुट दिए जाते हैं। इसका मतलब है कि इसमें सबसे बड़े m + 1 निवेशों में से सबसे छोटे दो निवेश होने चाहिए। इसके अलावा, चूंकि इन दो वस्तुओं का योग कम से कम 3/2+3 2 = 3 है, इसलिए पाई को कोई अन्य इनपुट नहीं दिया जाता है। दूसरी ओर, कबूतर छेद सिद्धांत के अनुसार, कुछ इष्टतम बिन क्यूजे होना चाहिए जिसमें सबसे बड़े एम + 1 निवेशों में से कुछ दो निवेश शामिल हों; इसलिए पाई पर क्यूजे का प्रभुत्व है। लालची एल्गोरिदम के संचालन के दौरान, किसी भी बिन का योग 4 से अधिक होने से पहले प्रत्येक बिन पाई में योग कम से कम 8/3 हो जाता है। प्रमाणः मान लीजिए कि y किसी बिन पाई में जोड़ा गया पहला इनपुट है, जिसने इसका योग 4 से बड़ा कर दिया। y को जोड़ने से पहले, पाई में सबसे छोटा योग था, जो धारणा के अनुसार 8/3 से छोटा था; इसका मतलब है कि y> 4/3। मान लीजिए कि T पहले से नीचे y तक सभी निवेशों के समूह को दर्शाता है; ये सभी निवेश 4/3 से भी बड़े हैं। चूँकि पाई 8/3 से छोटा था, इसमें टी से बिल्कुल एक आइटम x था। तो अब पाई में ठीक 2 आइटम {x, y} हैं, और एल्गोरिथ्म समाप्त होने तक इन 2 वस्तुओं के साथ रहता है। मान लीजिए कि m पहले वाले से x तक वस्तुओं की संख्या है। अब हम दो तरीकों से टी में वस्तुओं की गिनती करके एक विरोधाभास दिखाते हैं। सबसे पहले, एन इष्टतम डिब्बे पर विचार करें। यदि ऐसे किसी बिन में कम से कम x जितनी बड़ी वस्तु है, तो इसमें T की कोई अन्य वस्तु नहीं हो सकती है, क्योंकि अन्यथा यह {x, y} पर हावी है। इसके अलावा, ऐसे किसी भी बिन में T से तीन आइटम नहीं हो सकते हैं, क्योंकि उनमें से किसी भी दो का योग 8/3 से बड़ा है, जो x से बड़ा है; और तीसरा कम से कम y है, इसलिए यह {x, y} पर हावी है। इसलिए, T में वस्तुओं की संख्या अधिकतम 1 * m + 2 * (n-m) = 2n-m है। अब, लालची डिब्बे पर विचार करें। जब x युक्त बंडल में y जोड़ा जाता है, तो यह सबसे छोटी राशि वाला बंडल होता है। इसलिए, टी के सभी तत्व जो एक्स से छोटे हैं, कम से कम एक अन्य वस्तु टी के साथ एक लालची बिन में होने चाहिए। यही बात एक्स और वाई के लिए भी सही है। इसलिए, टी में वस्तुओं की संख्या कम से कम (एम-1) + 2 * (एन-एम + 1) = 2एन-एम + 1-विरोधाभास है। हम सामान्यता को खोए बिना यह मान सकते हैं कि सभी निवेश या तो 1/3 या कम से कम 1 से कम हैं। प्रमाणः मान लीजिए कि कुछ इनपुट x (1/3,1) में है। हम x को 1 से प्रतिस्थापित करते हैं। यह स्पष्ट रूप से इष्टतम न्यूनतम राशि को कम नहीं करता है। हम दिखाते हैं कि यह लालची न्यूनतम राशि को नहीं बदलता है। हम जानते हैं कि कुछ लालची बंडल पाई की अंतिम राशि 4 से बड़ी होती है। पाई में अंतिम इनपुट को जोड़ने से पहले, इसका योग 3 से छोटा था; इसलिए पाई 4 से बड़ा हो गया जब इसमें 1 से बड़ा कुछ इनपुट जोड़ा गया। पिछली परिकल्पना तक, उस समय अन्य सभी लालची बंडलों का योग कम से कम 8/3 था। एल्गोरिथ्म बाद में x पर आता है। एक बार जब एल्गोरिथ्म कुछ बिन पीजे में एक्स जोड़ता है, तो पीजे का योग कम से कम 8/3+1 3 = 3 हो जाता है, इसलिए पीजे में कोई और आइटम नहीं जोड़े जाते हैं। इसलिए Pj में [1/3,1) में आकार के साथ केवल एक इनपुट होता है। एक बार जब x को 1 से बदल दिया जाता है, तब भी इसे Pj में डाला जाता है, और इसका योग अभी भी 3 से ऊपर है। इसलिए लालची न्यूनतम राशि नहीं बदलती है। अब हम निवेश को छोटे (1/3 से कम) और बड़े (कम से कम 1) में विभाजित कर सकते हैं। पाई में छोटी वस्तुओं के समूह को सी द्वारा दर्शाया जाता है। ध्यान दें कि, जब एल्गोरिथ्म छोटी वस्तुओं को संसाधित करना शुरू करता है, तो सभी बंडलों में योग कम से कम 8/3 होता है। यह प्रमाण कि एक न्यूनतम प्रति-उदाहरण मौजूद नहीं है, एक भार योजना का उपयोग करता है। प्रत्येक इनपुट x को उसके आकार और लालची बंडल पाई के अनुसार एक वजन डब्ल्यू (एक्स) सौंपा जाता हैः यदि एक्स एक बड़ी वस्तु हैः यदि एक्स पाई में एकल बड़ी वस्तु है, तो डब्ल्यू (एक्स) = 8/3। यदि पाई में ठीक दो आइटम {x, y} हैं और वे दोनों बड़े हैं, और x> y, और योग (Pi) ≤ 3, तो डब्ल्यू (x) = 8/3 है। अन्यथा, डब्ल्यू (एक्स) = 4/3। यदि x एक छोटी वस्तु हैः यदि योग (पी. आई.) 3, तो डब्ल्यू (एक्स) = 4x/(3 योग (सी)); तो डब्ल्यू (सी) = 4/3। यदि योग (पाई) <3 है, तो डब्ल्यू (एक्स) = 2x/(3 योग (सी)); तो डब्ल्यू (सी) = 2/3। इस भार योजना में निम्नलिखित गुण हैंः यदि x ≤ 2 है, तो w (x) = 8/3 है। प्रमाणः x बड़ा है। मान लीजिए कि यह पाई में है। यदि पाई में एक और बड़ी वस्तु y है, तो x + y ≤ 3 इसलिए पाई में कोई अन्य वस्तु नहीं है। इसके अलावा, x> y क्योंकि अधिकतम एक वस्तु 3/2 से बड़ी होती है। अतः डब्ल्यू (एक्स) = 8/3। यदि x <1/3 है, तो w (x)> 2x। प्रमाणः x छोटा है। मान लीजिए कि यह पाई में है। यदि योग (पी. आई.) 3 है तो, चूँकि योग (पी. आई.) में x जोड़ने से पहले 3 से छोटा था, यह अब 10/3 से छोटा है। लेकिन जब एल्गोरिथ्म ने छोटी वस्तुओं को संसाधित करना शुरू किया, तो योग (पी. आई.) कम से कम 8/3 था। इसका अर्थ है कि योग (सी) <2/3, तो डब्ल्यू (एक्स) = 4x/(3 योग (सी))> 2x। यदि योग (पाई) <3 है तो योग (सी) <3-8/3 = 1/3, तो डब्ल्यू (एक्स) = 2x/(3 योग (सी))> 2x। प्रत्येक लालची बिन पाई का वजन अधिक से अधिक 4 है, और कम से कम एक लालची बिन का वजन अधिक से अधिक 10/3 है। प्रमाणः यदि पाई में सभी इनपुट बड़े हैं, तो इसमें या तो 8/3 भार के साथ एक इनपुट, 8/3+4 3 भार के साथ दो इनपुट, या 4/3+4 3 + 4/3 भार के साथ तीन इनपुट होते हैं। यदि पाई में कुछ निवेश छोटे हैं, तो उनका कुल वजन अधिकतम 4/3 है। अधिक से अधिक दो बड़े निवेश होते हैं, और उनका भार या तो 8/3 या 4/3+4 3 होता है। अंत में, 3 से कम राशि वाले लालची बिन का वजन अधिकतम 8/3 (यदि इसमें केवल बड़े निवेश हैं) या 10/3 (यदि इसमें कुछ छोटे निवेश हैं) है। प्रत्येक इष्टतम बिन क्यूजे का वजन कम से कम 4 होता है। प्रमाणः यदि क्यूजे में केवल छोटी वस्तुएँ हैं, तो उनमें से प्रत्येक डब्ल्यू (एक्स)> 2x को संतुष्ट करता है, इसलिए डब्ल्यू (क्यूजे)> 2 योग (क्यूजे) ≤ 8। यदि क्यूजे में ठीक एक बड़ी वस्तु x है, तो इसमें कुछ छोटी वस्तुएँ होनी चाहिए जिनका योग कम से कम 4-x और वजन कम से कम 8-2x हो। फिर, या तो x <2 और छोटी वस्तुओं का वजन कम से कम 8-4 = 4, या x में (2,3) और w (x) = 8/3 और छोटी वस्तुओं का वजन कम से कम 8-6 = 2 है। दोनों ही मामलों में कुल वजन कम से कम 4 है। यदि क्यूजे में ठीक दो बड़ी वस्तुएँ x> y और x ≤ 2 हैं, तो कम से कम 8/3+4 3 = 4 है। यदि x + y ≤ 10/3 है, तो छोटी वस्तुओं का योग कम से कम 2/3 होना चाहिए, इसलिए कुल वजन कम से कम 4/3+4 3 + 2 * 2/3 = 4 है। अन्यथा, x> 5/3। तो x किसी लालची बिन पी. एम. में पहला इनपुट था। मान लीजिए कि z, Pm में जोड़ा गया दूसरा इनपुट है। यदि x + z ≤ 3 है, तो Pm में कोई और इनपुट नहीं हैं, इसलिए w (x) = 8/3 और हम कर चुके हैं। अन्यथा, x + z <3। मान लीजिए कि v किसी लालची बिन में सबसे छोटा निवेश है जिसका योग 4 से अधिक है। चूँकि x <8/3, z को v से पहले संसाधित किया गया होगा, इसलिए z ≤ v। अब क्यूजे में किसी भी छोटी वस्तु पर विचार करें, और मान लीजिए कि यह किसी लालची बिन पाई में है। यदि योग (पाई) <3 है, तो यह तथ्य कि वी को पाई में नहीं रखा गया था, इसका तात्पर्य है कि वी> 4-योग (बड़ी-आइटम-इन-पाई)> 1 + योग (छोटी-आइटम-इन-पाई)। इसलिए, 1 + योग (Si) + x <v + x ≤ z + x <3 और योग (Si) <2-x। इसका मतलब है कि 2 * योग (सी) <4-4x ≤ 4-x-y ≤ योग (क्यूजे में छोटी-वस्तुएं)। अतः डब्ल्यू (टी) = 2टी/(3सम (सी))> 4टी/(3सम (क्यूजे में छोटी-वस्तुएं))। यदि योग (पाई) ≤ 3, और योग (सी) ≤ 1, तो डब्ल्यू (टी) = 4/3 और हम कर रहे हैं। चूँकि योग (पाई) में टी जोड़ने से पहले 3 से कम था, इसलिए योग (पाई) <3 + योग (सी)/2। यह तथ्य कि वी को पाई में नहीं रखा गया था, इसका तात्पर्य है कि वी> 4-योग (बड़ी-आइटम-इन-पाई)> 1 + योग (छोटी-आइटम-इन-पाई)/2। पिछले पैराग्राफ के समान, डब्ल्यू (टी)> 4 टी/(3सम (क्यूजे में छोटी-वस्तुएं))। इसलिए, क्यूजे में सभी छोटी वस्तुओं का कुल वजन कम से कम 3/4 है, इसलिए क्यूजे का कुल वजन कम से कम 4/3+10 3> 4 है। यदि क्यूजे में ठीक तीन या अधिक बड़ी वस्तुएँ हैं, तो इसका कुल वजन कम से कम 4/3+4 3 + 4/3 = 4 है। अंतिम दो दावे विरोधाभासी हैं, क्योंकि पहले का तात्पर्य है कि सभी निवेशों का वजन अधिकतम 4 मीटर-2/3 है, और बाद वाले का तात्पर्य है कि सभी निवेशों का वजन कम से कम 4 मीटर है। इसलिए, एक विपरीत उदाहरण मौजूद नहीं है। अनुपात पर ऊपरी सीमा एक अधिक परिष्कृत विश्लेषण से पता चलता है कि अनुपात अधिक से अधिक है (उदाहरण के लिए, जब m = 2 अनुपात 5/6 है)। कठोरता और उदाहरण उपरोक्त अनुपात तंग है। मान लीजिए कि 3m-1 निवेश हैं (जहाँ m सम है)। पहले 2 मीटर इनपुट हैंः 2 मीटर-1,2 मीटर-1,2 मीटर-2,2 मीटर-2,3 मीटर। अंतिम एम-1 इनपुट सभी एम हैं। फिर लालची एल्गोरिथ्म लौटता हैः 2 मीटर-1, एम, एम 2 मीटर-1, एम, एम 2 मीटर-2, एम + 1, एम 2 मीटर-2, एम + 1, एम। 3 मीटर/2,3 मीटर/2-1, एम 3 मीटर/2-2, एम 3 मीटर/2,3 मीटर/2-2 न्यूनतम 3 मीटर-1 के साथ। लेकिन इष्टतम विभाजन हैः 2m-1,2m-2, m, m 2m-2, m, m 2m-3, m + 1, m 2m-3, m + 1, m. 3m/2,3m/2-2, m 3m/2,3m/2-2, m 3m/2-2, m 3m/2-2, m 3m/2-2,3m/2-2, m न्यूनतम 4m-2 के साथ। प्रतिबंधित एल. पी. टी. एल. पी. टी. का एक प्रकार है, जिसे प्रतिबंधित-एल. पी. टी. या आर. एल. पी. टी. कहा जाता है, जिसमें निवेश को एम आकार के उपसमुच्चय में विभाजित किया जाता है जिसे रैंक कहा जाता है (रैंक 1 में सबसे बड़ा एम निवेश होता है, रैंक 2 में अगले सबसे बड़े एम निवेश होते हैं, आदि)। प्रत्येक श्रेणी में निवेश अलग-अलग डिब्बों को सौंपा जाना चाहिएः पहले श्रेणी 1, फिर श्रेणी 2, आदि। आरएलपीटी में न्यूनतम राशि एलपीटी में अधिकतम न्यूनतम राशि होती है। न्यूनतम राशि को अधिकतम करने के लिए आरएलपीटी का अनुमानित अनुपात अधिकतम एम है। औसत मामले में अधिकतम राशि औसत मामले में, यदि इनपुट संख्याएँ समान रूप से [0,1] में वितरित की जाती हैं, तो एलपीटी अनुसूची में सबसे बड़ा योग निम्नलिखित गुणों को संतुष्ट करता हैः एम = 2 मशीनों के लिए अपेक्षित सबसे बड़ा योग कम से कम और अधिक से अधिक है, जहाँ एन इनपुट की संख्या है। सबसे बड़ी राशि ज्यादातर समय लगभग निश्चित रूप से इष्टतम होती है, और उम्मीद में, निवेश की संख्या कहाँ है। एल. पी. टी. की सबसे बड़ी राशि और इष्टतम सबसे बड़ी राशि के बीच का अंतर लगभग निश्चित रूप से (समान या नकारात्मक घातीय वितरण के लिए) और अधिक से अधिक अपेक्षा में (समान वितरण के लिए) होता है। ये परिणाम अलग-अलग गति वाली मशीनों के लिए भी होते हैं। मान लीजिए कि Ci (i के लिए 1 और m के बीच) किसी दिए गए विभाजन में सबसेट i का योग है। वस्तुनिष्ठ फलन अधिकतम (Ci) को न्यूनतम करने के बजाय, कोई भी वस्तुनिष्ठ फलन अधिकतम (f (Ci)) को न्यूनतम कर सकता है, जहाँ f कोई निश्चित फलन है। इसी तरह, कोई भी वस्तुनिष्ठ फलन योग (f (Ci)) को कम कर सकता है। एलोन, अज़र, वोजिंगर और यादिद यह साबित करते हैं कि, यदि f निम्नलिखित दो शर्तों को संतुष्ट करता हैः एक मजबूत निरंतरता शर्त जिसे शर्त F * कहा जाता हैः प्रत्येक ε> 0 के लिए δ> 0 इस तरह मौजूद है कि, यदि |y-x। <δx, तो |f (y)-f (x)। <εf (x)। कन्वेक्सिटी। फिर एल. पी. टी. नियम में योग (एफ (सी. आई.)) को न्यूनतम करने के लिए एक सीमित सन्निकटन अनुपात है। समान-मशीन समय-निर्धारण के सरल मामले के अलावा, एल. पी. टी. को अधिक सामान्य सेटिंग्स के लिए अनुकूलित किया गया है। समान मशीनें समान-मशीनों के समय निर्धारण में, विभिन्न मशीनों की गति अलग-अलग हो सकती है। एल. पी. टी. नियम प्रत्येक कार्य को उस मशीन को सौंपता है जिस पर इसका पूरा होने का समय सबसे पहले होगा (यानी, एल. पी. टी. एक बड़ी धारा भार वाली मशीन को कार्य सौंप सकता है, यदि यह मशीन इतनी तेज है कि वह उस कार्य को अन्य सभी मशीनों की तुलना में पहले पूरा कर लेगी)। गोंजालेज, इबारा और साहनी दर्शाते हैं कि एम वर्दी मशीनों के साथ एल. पी. टी. का अनुमानित अनुपात अधिक से अधिक है। यह तंग नहीं है, लेकिन जब m अनंत के करीब आता है तो 1.5 की एक एसिम्प्टोटिक निचली सीमा होती है। एम = 2 मशीनों के विशेष मामले के लिए, सन्निकटन अनुपात अधिक से अधिक है और यह तंग है। मिरेल्ट, ऑर्लिन और वोहरा दो मशीनों के साथ एक सेटिंग का अध्ययन करते हैं, जिसमें एक मशीन दूसरी की तुलना में क्यू गुना तेज होती है। वे एल. पी. टी. के सन्निकटन अनुपात की गणना क्यू के फलन के रूप में करते हैं। जब q = 1 होता है, तो उनका परिणाम समान मशीनों के लिए ज्ञात 7/6 कारक के साथ मेल खाता है। कौलामास और किपरिसिस एल. पी. टी. का एक संशोधन प्रस्तुत करते हैं जिसमें तीन सबसे लंबे कार्य इष्टतम रूप से निर्धारित किए जाते हैं, और शेष कार्य एल. पी. टी. नियम के आधार पर निर्धारित किए जाते हैं। दो मशीनों के लिए अनुमानित अनुपात है और यह तंग है। कार्डिनलिटी की बाधाएं संतुलित विभाजन समस्या में, प्रत्येक मशीन को सौंपे जा सकने वाले कार्यों की संख्या पर बाधाएं हैं। एक सरल बाधा यह है कि प्रत्येक मशीन अधिकतम सी कार्यों को संसाधित कर सकती है। एल. पी. टी. नियम सी. नौकरियों से कम वाले लोगों में से सबसे कम भार वाली मशीन को प्रत्येक काम सौंपता है। इस नियम को संशोधित एल. पी. टी. या एम. एल. पी. टी. कहा जाता है। केलर और वोजिंगर एक प्रकार का अध्ययन करते हैं जिसमें अधिकतम 3 * मीटर कार्य होते हैं, और प्रत्येक मशीन में अधिकतम 3 कार्य होने चाहिए (इसे 3-विभाजन समस्या के सामान्यीकरण के रूप में देखा जा सकता है)। वे बताते हैं कि एम. एल. पी. टी. अधिकतम न्यूनतम सबसे बड़ी राशि प्राप्त करता है, जो कि वही अनुमानित अनुपात है जो एल. पी. टी. अनियंत्रित समस्या के लिए प्राप्त करता है। एम. एल. पी. टी. के लिए सीमा कड़ी है। यह अनुमान लगाया जाता है कि एम. एल. पी. टी. में अधिक सामान्य कार्डिनलिटी बाधाओं (सी> 3) के लिए समान सन्निकटन अनुपात है। वर्तमान में, यह ज्ञात है कि सामान्य सी> 3 के लिए एम. एल. पी. टी. का अनुमानित अनुपात अधिकतम 2 है। चेन, हे और लिन दिखाते हैं कि, एक ही समस्या के लिए, एम. एल. पी. टी. कम से कम अधिकतम सबसे छोटी राशि प्राप्त करता है, जो फिर से वही अनुपात है जो एल. पी. टी. अनियंत्रित समस्या के लिए प्राप्त करता है। एक अन्य बाधा यह है कि सभी मशीनों पर काम की संख्या को ऊपर या नीचे किया जाना चाहिए। एल. पी. टी. के एक अनुकूलन में जिसे प्रतिबंधित एल. पी. टी. या आर. एल. पी. टी. कहा जाता है, इनपुट को जोड़े में सौंपा जाता है-प्रत्येक मशीन को एक (एम = 2 मशीनों के लिए)। परिणामी विभाजन डिजाइन द्वारा संतुलित है। कॉफ़मैन, फ्रेडरिकसन और ल्यूकर बताते हैं कि आरएलपीटी का अपेक्षित सबसे बड़ा योग जब इनपुट समान रूप से वितरित यादृच्छिक चर होते हैं तो ठीक होता है। सबसे बड़ी और सबसे छोटी राशि के बीच अपेक्षित अंतर है। कर्नेल की बाधाएं-गैर-एक साथ उपलब्धता कर्नेल विभाजन समस्या में, कुछ एम पूर्व-निर्दिष्ट कार्य हैं जिन्हें कर्नेल कहा जाता है, और प्रत्येक कर्नेल को एक अद्वितीय मशीन के लिए निर्धारित किया जाना चाहिए। एक समतुल्य समस्या समय निर्धारण है जब मशीनें अलग-अलग समय में उपलब्ध होती हैंः प्रत्येक मशीन i किसी समय ti ≤ 0 पर उपलब्ध हो जाती है (समय ti को कर्नेल कार्य की लंबाई के रूप में माना जा सकता है)। एक सरल ह्यूरिस्टिक एल्गोरिथ्म, जिसे एसएलपीटी कहा जाता है, प्रत्येक कर्नेल को एक अलग उपसमुच्चय को असाइन करता है, और फिर एलपीटी एल्गोरिथ्म चलाता है। ली साबित करते हैं कि इस शोध में न्यूनतम सबसे बड़ी राशि के लिए एक तंग सन्निकटन अनुपात है। फिर वह दूसरे चरण में, एल. पी. टी. का एक संशोधित संस्करण चलाने का सुझाव देता है, और साबित करता है कि यह एक अनुमानित अनुपात प्राप्त करता है। लिन, याओ और हे साबित करते हैं कि इस शोध में अधिकतम सबसे छोटी राशि के लिए एक तंग सन्निकटन अनुपात है। शेन, वांग और वांग इस सेटिंग के लिए विभिन्न वस्तुनिष्ठ कार्यों का अध्ययन करते हैं, और बहुपद-समय एल्गोरिदम प्रस्तुत करते हैं। ऑनलाइन सेटिंग अक्सर, इनपुट ऑनलाइन आते हैं, और उनके आकार केवल तभी ज्ञात होते हैं जब वे आते हैं। इस मामले में, उन्हें पहले से छांटना संभव नहीं है। लिस्ट शेड्यूलिंग एक समान एल्गोरिथ्म है जो किसी भी क्रम में एक सूची लेता है, जरूरी नहीं कि क्रमबद्ध हो। इसका अनुमानित अनुपात है। ऑनलाइन सेटिंग के लिए एल. पी. टी. का एक अधिक परिष्कृत अनुकूलन 3/2 का अनुमानित अनुपात प्राप्त करता है। कार्यान्वयन पायथनः संख्या विभाजन पैकेज के साथ-साथ पी. आर. टी. पी. पैकेज में एल. पी. टी. ("लालची") का कार्यान्वयन होता है। लालची संख्या विभाजन-बहुपथ संख्या विभाजन की समस्या के लिए एल. पी. टी. के सामान्यीकरण और विस्तार भी देखें। नोट्स संदर्भ अनुसूची एल्गोरिदम संख्या विभाजन