Longest-processing-time-first scheduling
લોંગેસ્ટ-પ્રોસેસિંગ-ટાઇમ-ફર્સ્ટ (એલ. પી. ટી.) એ નોકરીના સમયપત્રક માટે લોભી અલ્ગોરિધમ છે. અલ્ગોરિધમનો ઇનપુટ એ નોકરીઓનો સમૂહ છે, જેમાંના દરેકનો ચોક્કસ પ્રક્રિયા-સમય હોય છે. નોકરીઓ પર પ્રક્રિયા કરી શકે તેવા મશીનોની સંખ્યાને સ્પષ્ટ કરતી સંખ્યા એમ પણ છે. એલ. પી. ટી. અલ્ગોરિધમ નીચે પ્રમાણે કામ કરે છેઃ નોકરીઓને તેમના પ્રક્રિયા-સમયના ઉતરતા ક્રમમાં ક્રમ આપો, જેમ કે સૌથી લાંબા પ્રક્રિયા સમય સાથેનું કામ પ્રથમ હોય. આ ક્રમમાં દરેક કાર્યને એક મશીનમાં સુનિશ્ચિત કરો જેમાં વર્તમાન ભાર (= અનુસૂચિત કાર્યોનો કુલ પ્રક્રિયા-સમય) સૌથી નાનો હોય. અલ્ગોરિધમનો બીજો તબક્કો અનિવાર્યપણે સૂચિ-સુનિશ્ચિત (એલ. એસ.) અલ્ગોરિધમ છે. તફાવત એ છે કે એલ. એસ. મનસ્વી ક્રમમાં નોકરીઓ પર લૂપ કરે છે, જ્યારે એલ. પી. ટી. પ્રક્રિયાના સમયને ઘટાડીને તેમને પ્રી-ઓર્ડર કરે છે. એલ. પી. ટી. નું પ્રથમ વિશ્લેષણ રોનાલ્ડ ગ્રેહામ દ્વારા 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} છે. ગુણધર્મો LPT શ્રેષ્ઠ પાર્ટીશન શોધી શકશે નહીં. ઉદાહરણ તરીકે, ઉપરોક્ત ઉદાહરણમાં શ્રેષ્ઠ પાર્ટીશન {8,7}, {6,5,4}, જ્યાં બંને રકમ 15 ની બરાબર છે. જો કે, તેની સબઓપ્ટિમાલિટી સૌથી ખરાબ કિસ્સામાં અને સરેરાશ કિસ્સામાં બંનેમાં બંધાયેલ છે; નીચે પ્રદર્શન બાંયધરી જુઓ. એલ. પી. ટી. નો ચાલતો સમય સૉર્ટિંગ દ્વારા પ્રભુત્વ ધરાવે છે, જે ઓ (એન લોગ એન) સમય લે છે, જ્યાં એન એ ઇનપુટ્સની સંખ્યા છે. કામગીરીની બાંયધરીઃ સમાન મશીનો જ્યારે સમાન-મશીનોના સમયપત્રક માટે વપરાય છે, ત્યારે એલ. પી. ટી. નીચેના અંદાજ ગુણોત્તર પ્રાપ્ત કરે છે. સૌથી ખરાબ કિસ્સામાં મહત્તમ રકમ સૌથી ખરાબ કિસ્સામાં, લોભી પાર્ટીશનમાં સૌથી મોટી રકમ મોટાભાગે શ્રેષ્ઠ (લઘુત્તમ) સૌથી મોટી રકમ હોય છે. વધુ વિગતવાર વિશ્લેષણ શ્રેષ્ઠ (લઘુત્તમ) સૌથી મોટી રકમના ગુણાંકનું પરિબળ આપે છે. (ઉદાહરણ તરીકે, જ્યારે m = 2 હોય ત્યારે આ ગુણોત્તર છે). પરિબળ ચુસ્ત છે. ધારો કે ત્યાં ઇનપુટ્સ છે (જ્યાં m સમ છે): પછી લોભી અલ્ગોરિધમ પરત કરે છેઃ,. મહત્તમ સાથે, પરંતુ શ્રેષ્ઠ પાર્ટીશન છેઃ. મહત્તમ સાથે. ઇનપુટ વિચારણા એક વધુ વિગતવાર વિશ્લેષણ મહત્તમ-રકમ ભાગમાં ઇનપુટ્સની સંખ્યાને ધ્યાનમાં લે છે. લોભી વિભાજનના દરેક ભાગમાં, જે-th સૌથી વધુ સંખ્યા છે. ધારો કે, લોભી ભાગ P માં મહત્તમ રકમ સાથે, L ઇનપુટ્સ છે. પછી, લોભી અલ્ગોરિધમનો અંદાજ ગુણોત્તર છે. તે L ≤ 3 માટે ચુસ્ત છે (L = 3 માટે, આપણને સામાન્ય પરિબળ મળે છે). પુરાવો. P માં સંખ્યાઓને x1,., xL દ્વારા દર્શાવો. P માં xL દાખલ કરવામાં આવે તે પહેલાં, તેનો સરવાળો સૌથી નાનો હતો. તેથી, ભાગ દીઠ સરેરાશ સરવાળો ઓછામાં ઓછો x1 +. + xL-1 + xL/m નો સરવાળો છે. મહત્તમ મહત્તમ રકમ ઓછામાં ઓછી સરેરાશ રકમ હોવી જોઈએ. તેનાથી વિપરીત, લોભી રકમ x1 +. + xL-1 + xL છે. તેથી તફાવત વધુમાં વધુ (1-1/m) xL છે, જે (1) દ્વારા વધુમાં વધુ (1-1/m) * ઓ. પી. ટી./એલ. છે. તેથી ગુણોત્તર મહત્તમ (1 + 1/L-1/Lm) છે. સૌથી ખરાબ કિસ્સામાં લઘુતમ રકમ સૌથી ખરાબ કિસ્સામાં, પરત કરેલા પાર્ટીશનમાં સૌથી નાની રકમ ઓછામાં ઓછી મહત્તમ (મહત્તમ) સૌથી નાની રકમ હોય છે. પુરાવો પુરાવો વિરોધાભાસ દ્વારા છે. આપણે ન્યૂનતમ પ્રતિ-ઉદાહરણને ધ્યાનમાં લઈએ છીએ, એટલે કે, સૌથી નાના m અને સૌથી ઓછા ઇનપુટ નંબરો સાથેનું પ્રતિ-ઉદાહરણ. લોભી પાર્ટીશનને P1,., Pm દ્વારા અને શ્રેષ્ઠ પાર્ટીશનને Q1,., Qm દ્વારા દર્શાવો. ન્યૂનતમ પ્રતિકૂળ ઉદાહરણના કેટલાક ગુણધર્મો આ પ્રમાણે છેઃ શ્રેષ્ઠ પાર્ટીશનમાં લઘુતમ સરવાળો 4 છે, અને લોભી પાર્ટીશનમાં લઘુતમ સરવાળો 3 કરતા ઓછો છે (આ માત્ર સામાન્યીકરણ છે-તે સામાન્યતાની ખોટ વિના છે). લોભી પાર્ટીશનમાં મહત્તમ રકમ 4 થી વધુ છે (કારણ કે બંને પાર્ટીશનમાં કુલ રકમ સમાન છે, અને તે ઓછામાં ઓછી 4 મી છે). જો અમુક લોભી બિન પી માટે સરવાળો (પી. આઈ.) 3 હોય, તો પી. આઈ. પર કોઈ શ્રેષ્ઠ બિન ક્યૂ. જે. નું વર્ચસ્વ નથી. પુરાવોઃ જો પી. આઈ. માં ક્યુ. જે. નું વર્ચસ્વ હોય, તો આપણે એમ. થી એમ.-1 ઘટાડીને અને પી. આઈ. માં વસ્તુઓને દૂર કરીને એક નાનું પ્રતિકૂળ ઉદાહરણ બનાવી શકીએ છીએ. લોભી પાર્ટીશનમાં લઘુતમ રકમ 3 કરતા ઓછી રહે છે. શ્રેષ્ઠ પાર્ટીશનમાં, પીઆઇમાંની વસ્તુઓને ક્યુજેમાં તેમની પ્રબળ વસ્તુઓ દ્વારા બદલી શકાય છે, તેથી લઘુતમ રકમ ઓછામાં ઓછી 4 રહે છે. જો કોઈ લોભી બિન પી માટે સરવાળો (પી. આઈ.) 3 હોય, તો પી. આઈ. માં ઓછામાં ઓછી બે સંખ્યાઓ હોય છે. પુરાવોઃ જો પી. આઈ. માં માત્ર એક જ સંખ્યા x હોય, તો તેમાં શ્રેષ્ઠ બિન ક્યૂ. જે. નું પ્રભુત્વ હોય છે, જેમાં x.givese હોય છે, કેટલાક ઇનપુટ x ઓછામાં ઓછા 3 હોય છે, અને લોભી અલ્ગોરિધમ તેને અમુક પી. આઈ. માં મૂકે છે. પછી, 3 કરતા ઓછી રકમ સાથેનું બંડલ હોવાથી, લોભી અલ્ગોરિધમ અગાઉના લેમ્માને વિરોધાભાસી પાઇમાં અન્ય કોઈ ઇનપુટ મૂકશે નહીં. દરેક લોભી બિન પાઈમાં મહત્તમ એક ઇનપુટ હોય છે જે 3/2 કરતા નબળું-મોટું હોય છે. પુરાવોઃ ચાલો પાઇ એ પ્રથમ લોભી ડબ્બો છે જેને આવા બે ઇનપુટ્સ સોંપવામાં આવ્યા છે. ઇનપુટ્સ ઉતરતા ક્રમમાં સોંપવામાં આવતા હોવાથી, પી. આઈ. એ પ્રથમ લોભી બિન છે જેને બે ઇનપુટ્સ સોંપવામાં આવ્યા છે. આનો અર્થ એ છે કે તેમાં સૌથી મોટા m + 1 ઇનપુટ્સમાંથી સૌથી નાના બે ઇનપુટ્સ હોવા જોઈએ. વધુમાં, આ બે વસ્તુઓનો સરવાળો ઓછામાં ઓછો 3/2+3 2 = 3 હોવાથી, પીઆઇને અન્ય કોઈ ઇનપુટ સોંપવામાં આવ્યું નથી. બીજી બાજુ, કબૂતર છિદ્ર સિદ્ધાંત દ્વારા, કેટલાક શ્રેષ્ઠ બિન ક્યૂજે હોવા જોઈએ જેમાં સૌથી મોટા એમ + 1 ઇનપુટ્સમાંથી કેટલાક બે ઇનપુટ્સ હોય; તેથી પીઆઇ પર ક્યૂજેનું પ્રભુત્વ છે. લોભી અલ્ગોરિધમ ચલાવતી વખતે, કોઈપણ બિનનો સરવાળો 4 કરતાં વધી જાય તે પહેલાં દરેક બિન પાઇમાં સરવાળો ઓછામાં ઓછો 8/3 થઈ જાય છે. પુરાવોઃ ધારો કે y એ કોઈ બિન પાઇમાં ઉમેરાયેલું પ્રથમ ઇનપુટ છે, જેણે તેનો સરવાળો 4 કરતા મોટો કર્યો હતો. વાય ઉમેરવામાં આવે તે પહેલાં, પી. આઈ. નો સરવાળો સૌથી નાનો હતો, જે ધારણા પ્રમાણે 8/3 કરતા નાનો હતો; આનો અર્થ એ કે વાય> 4/3. ચાલો T એ પ્રથમમાંથી નીચે y સુધીના તમામ ઇનપુટ્સના સમૂહને સૂચવે છે; આ બધા ઇનપુટ્સ પણ 4/3 કરતા મોટા છે. પીઆઇ 8/3 કરતા નાનો હોવાથી, તેમાં ટીમાંથી બરાબર એક વસ્તુ x છે. તેથી હવે પીઆઇ બરાબર 2 વસ્તુઓ {x, y} ધરાવે છે, અને અલ્ગોરિધમ સમાપ્ત થાય ત્યાં સુધી આ 2 વસ્તુઓ સાથે રહે છે. ધારો કે m એ પ્રથમમાંથી x સુધીની વસ્તુઓની સંખ્યા છે. હવે આપણે વસ્તુઓને બે રીતે ટીમાં ગણીને વિરોધાભાસ બતાવીએ છીએ. પ્રથમ, n શ્રેષ્ઠ ડબ્બાને ધ્યાનમાં લો. જો આવા કોઈપણ ડબ્બામાં ઓછામાં ઓછી x જેટલી મોટી વસ્તુ હોય, તો તેમાં T ની અન્ય કોઈ વસ્તુ ન હોઈ શકે, કારણ કે અન્યથા તે {x, y} પર પ્રભુત્વ ધરાવે છે. વધુમાં, આવા કોઈપણ ડબ્બામાં T માંથી ત્રણ વસ્તુઓ ન હોઈ શકે, કારણ કે તેમાંથી કોઈપણ બેનો સરવાળો 8/3 કરતા મોટો છે, જે x કરતા મોટો છે; અને ત્રીજો ઓછામાં ઓછો y છે, તેથી તે {x, y} પર પ્રભુત્વ ધરાવે છે. તેથી, T માં વસ્તુઓની સંખ્યા વધુમાં વધુ 1 * m + 2 * (n-m) = 2n-m છે. જ્યારે x ધરાવતા બંડલમાં y ઉમેરવામાં આવે છે, ત્યારે તે સૌથી નાની રકમ સાથેનું બંડલ છે. તેથી, T ના તમામ ઘટકો કે જે x કરતા નાના હોય, તે લોભી ડબ્બામાં ઓછામાં ઓછી એક T ની અન્ય વસ્તુ સાથે હોવા જોઈએ. તેથી, T માં વસ્તુઓની સંખ્યા ઓછામાં ઓછી (m-1) + 2 * (n-m + 1) = 2n-m + 1-વિરોધાભાસ છે. આપણે સામાન્યતા ગુમાવ્યા વિના ધારી શકીએ કે તમામ ઇનપુટ્સ 1/3 અથવા ઓછામાં ઓછા 1 કરતા નાના છે. પુરાવોઃ ધારો કે કેટલાક ઇનપુટ x (1/3,1) માં છે. આપણે x ને 1 થી બદલીએ છીએ. આ દેખીતી રીતે શ્રેષ્ઠ લઘુતમ રકમમાં ઘટાડો કરતું નથી. અમે બતાવીએ છીએ કે તે લોભી લઘુતમ રકમમાં ફેરફાર કરતું નથી. આપણે જાણીએ છીએ કે કેટલાક લોભી બંડલ પાઈની અંતિમ રકમ 4 કરતા મોટી હોય છે. પાઇમાં છેલ્લું ઇનપુટ ઉમેરવામાં આવ્યું તે પહેલાં, તેનો સરવાળો 3 કરતા નાનો હતો; તેથી જ્યારે તેમાં 1 કરતા મોટા કેટલાક ઇનપુટ ઉમેરવામાં આવ્યા ત્યારે પાઇ 4 કરતા મોટો થઈ ગયો. અગાઉના લેમ્મા સુધીમાં, તે સમયે અન્ય તમામ લોભી બંડલનો સરવાળો ઓછામાં ઓછો 8/3 હતો. અલ્ગોરિધમ પછીથી x પર આવે છે. એકવાર અલ્ગોરિધમ અમુક બિન Pj માં x ઉમેરે છે, Pj નો સરવાળો ઓછામાં ઓછો 8/3+1 3 = 3 બને છે, તેથી વધુ વસ્તુઓ Pj માં ઉમેરવામાં આવતી નથી. તેથી Pj એ [1/3,1) માં કદ સાથે માત્ર એક જ ઇનપુટ ધરાવે છે. એકવાર x ને 1 સાથે બદલવામાં આવે, તે હજુ પણ Pj માં દાખલ કરવામાં આવે છે, અને તેનો સરવાળો હજુ પણ 3 થી ઉપર છે. તેથી લોભી લઘુતમ રકમ બદલાતી નથી. હવે આપણે ઇનપુટ્સને નાના (1/3 કરતા ઓછા) અને મોટા (ઓછામાં ઓછા 1) માં વિભાજિત કરી શકીએ છીએ. પી. આઈ. માં નાની વસ્તુઓનો સમૂહ સી દ્વારા સૂચવવામાં આવે છે. નોંધ લો કે, જ્યારે અલ્ગોરિધમ નાની વસ્તુઓની પ્રક્રિયા કરવાનું શરૂ કરે છે, ત્યારે તમામ બંડલ્સમાં સરવાળો ઓછામાં ઓછો 8/3 હોય છે. ન્યૂનતમ પ્રતિકૂળ ઉદાહરણ અસ્તિત્વમાં નથી તેનો પુરાવો વજન યોજનાનો ઉપયોગ કરે છે. દરેક ઇનપુટ x ને તેના કદ અને લોભી બંડલ અનુસાર વજન w (x) સોંપવામાં આવે છેઃ જો x મોટી વસ્તુ હોય તોઃ જો x એ Pi માં એક મોટી વસ્તુ હોય, તો w (x) = 8/3. જો પી. આઈ. બરાબર બે વસ્તુઓ {x, y} ધરાવે છે અને તે બંને મોટી છે, અને x> y, અને સરવાળો (પી. આઈ.) ≤3, તો ડબલ્યુ (x) = 8/3. નહિંતર, w (x) = 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 કરતા મોટી હોય છે. તેથી w (x) = 8/3. જો x <1/3 હોય, તો પછી w (x)> 2x. પુરાવોઃ x નાનો છે. ધારો કે તે પી. આઈ. માં છે. જો સરવાળો (પી. આઈ.) 3 હોય તો, તેમાં x ઉમેરવામાં આવ્યો તે પહેલાં સરવાળો (પી. આઈ.) 3 કરતા નાનો હતો, તે હવે 10/3 કરતા નાનો છે. પરંતુ જ્યારે અલ્ગોરિધમે નાની વસ્તુઓની પ્રક્રિયા કરવાનું શરૂ કર્યું, ત્યારે સરવાળો (પી. આઈ.) ઓછામાં ઓછો 8/3 હતો. આનો અર્થ એ છે કે સરવાળો (સી) <2/3, તેથી ડબલ્યુ (એક્સ) = 4x/(3 સરવાળો (સી))> 2x. જો સરવાળો (Pi) <3 હોય તો સરવાળો (Si) <3-8/3 = 1/3, તેથી w (x) = 2x/(3 સરવાળો (Si))> 2x. દરેક લોભી બિન પાઇનું વજન વધુમાં વધુ 4 હોય છે, અને ઓછામાં ઓછું એક લોભી બિનનું વજન મહત્તમ 10/3 હોય છે. પુરાવોઃ જો પી. આઈ. માં તમામ ઇનપુટ્સ મોટા હોય, તો તેમાં 8/3 વજન સાથે એક ઇનપુટ, 8/3+4 3 વજન સાથે બે ઇનપુટ્સ અથવા 4/3+4 3 + 4/3 વજન સાથે ત્રણ ઇનપુટ્સ હોય છે. જો પી. આઈ. માં કેટલાક ઇનપુટ્સ નાના હોય, તો તેમનું કુલ વજન વધુમાં વધુ 3/4 છે. વધુમાં વધુ બે મોટા ઇનપુટ્સ હોય છે, અને તેમનું વજન 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 છે. જો Qj બરાબર બે મોટી વસ્તુઓ 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 ≤ સરવાળો (નાની-વસ્તુઓ-ઇન-ક્યૂજે). તેથી w (t) = 2t/(3sum (Si))> 4t/(3sum (સ્મોલ-આઇટમ-ઇન-Qj)). જો સરવાળો (પી. આઈ.) 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 સમ છે). પ્રથમ 2m ઇનપુટ્સ છેઃ 2m-1,2m-1,2m-2,2m-2,., m, m. છેલ્લા m-1 ઇનપુટ્સ બધા m છે. પછી લોભી અલ્ગોરિધમ વળતર આપે છેઃ 2m-1, m, m 2m-1, m, m 2m-2, m + 1, m 2m-2, m + 1, m. 3m/2,3m/2-1, m3m/2, m3m/2,3m/2-1 ઓછામાં ઓછા 3m-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, વગેરે. આરએલપીટીમાં લઘુતમ રકમ એલપીટીમાં મહત્તમ લઘુતમ રકમ છે. લઘુત્તમ રકમને મહત્તમ કરવા માટે RLPT નો અંદાજ ગુણોત્તર મહત્તમ m છે. સરેરાશ-કેસ મહત્તમ રકમ સરેરાશ કિસ્સામાં, જો ઇનપુટ સંખ્યાઓ [0,1] માં સમાનરૂપે વહેંચવામાં આવે, તો LPT અનુસૂચિમાં સૌથી મોટો સરવાળો નીચેના ગુણધર્મોને સંતોષે છેઃ m = 2 મશીનો માટે અપેક્ષિત સૌથી મોટો સરવાળો ઓછામાં ઓછો અને મહત્તમ છે, જ્યાં n એ ઇનપુટ્સની સંખ્યા છે. સૌથી મોટો સરવાળો મોટાભાગે લગભગ ચોક્કસપણે મહત્તમ હોય છે, અને અપેક્ષા મુજબ, ઇનપુટ્સની સંખ્યા ક્યાં છે. એલ. પી. ટી. ની સૌથી મોટી રકમ અને શ્રેષ્ઠ સૌથી મોટી રકમ વચ્ચેનો તફાવત લગભગ ચોક્કસપણે (સમાન અથવા નકારાત્મક ઘાતાંકીય વિતરણ માટે) અને સૌથી વધુ અપેક્ષા (સમાન વિતરણ માટે) માં હોય છે. આ પરિણામો વિવિધ ઝડપે ચાલતા મશીનો માટે પણ લાગુ પડે છે. સામાન્ય ઉદ્દેશો 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 ની એસિમ્પ્ટોટિક નીચલી સીમા હોય છે. m = 2 મશીનોના વિશેષ કિસ્સામાં, અંદાજ ગુણોત્તર મહત્તમ હોય છે અને તે ચુસ્ત હોય છે. મિરોલ્ટ, ઓરલિન અને વોહરા બે મશીનો સાથે સેટિંગનો અભ્યાસ કરે છે, જેમાં એક મશીન બીજા કરતા q ગણું ઝડપી હોય છે. તેઓ એલ. પી. ટી. ના અંદાજ ગુણોત્તરની ગણતરી q ના વિધેય તરીકે કરે છે. જ્યારે q = 1 હોય, ત્યારે તેમનું પરિણામ સમાન મશીનો માટે જાણીતા 7/6 પરિબળ સાથે મેળ ખાય છે. કૌલામાસ અને કિપરિસી એલ. પી. ટી. માં ફેરફાર રજૂ કરે છે જેમાં ત્રણ સૌથી લાંબી નોકરીઓ શ્રેષ્ઠ રીતે સુનિશ્ચિત કરવામાં આવે છે, અને બાકીની નોકરીઓ એલ. પી. ટી. નિયમના આધારે નિર્ધારિત કરવામાં આવે છે. બે મશીનો માટેનો અંદાજ ગુણોત્તર છે અને તે ચુસ્ત છે. કાર્ડિનાલિટી અવરોધો સંતુલિત પાર્ટીશન સમસ્યામાં, દરેક મશીનને સોંપી શકાય તેવી નોકરીઓની સંખ્યા પર અવરોધો છે. એક સરળ અવરોધ એ છે કે દરેક મશીન મહત્તમ સી જોબ્સ પર પ્રક્રિયા કરી શકે છે. એલ. પી. ટી. નો નિયમ સી. થી ઓછી નોકરીઓ ધરાવતા લોકોમાંથી સૌથી નાના ભાર સાથે મશીનને દરેક નોકરી સોંપે છે. આ નિયમને સંશોધિત એલ. પી. ટી. અથવા એમ. એલ. પી. ટી. કહેવામાં આવે છે. કેલર અને વોઇજિંગર એક પ્રકારનો અભ્યાસ કરે છે જેમાં મહત્તમ 3 * મીટર નોકરીઓ હોય છે, અને દરેક મશીનમાં મહત્તમ 3 નોકરીઓ હોવી આવશ્યક છે (આને 3-પાર્ટીશન સમસ્યાના સામાન્યીકરણ તરીકે જોઈ શકાય છે). તેઓ દર્શાવે છે કે એમ. એલ. પી. ટી. મોટાભાગની લઘુતમ સૌથી મોટી રકમ પ્રાપ્ત કરે છે, જે અનિયંત્રિત સમસ્યા માટે એલ. પી. ટી. સમાન અંદાજ ગુણોત્તર પ્રાપ્ત કરે છે. એમ. એલ. પી. ટી. માટે બાઉન્ડ ચુસ્ત છે. એવું અનુમાન કરવામાં આવે છે કે એમ. એલ. પી. ટી. વધુ સામાન્ય કાર્ડિનાલિટી અવરોધો (સી> 3) માટે સમાન અંદાજ ગુણોત્તર ધરાવે છે. હાલમાં, તે જાણીતું છે કે સામાન્ય સી> 3 માટે એમ. એલ. પી. ટી. નો અંદાજ ગુણોત્તર મહત્તમ 2 છે. ચેન, હી અને લિન દર્શાવે છે કે, સમાન સમસ્યા માટે, એમ. એલ. પી. ટી. ઓછામાં ઓછી મહત્તમ સૌથી નાની રકમ પ્રાપ્ત કરે છે, જે ફરીથી તે જ ગુણોત્તર છે જે એલ. પી. ટી. અનિયંત્રિત સમસ્યા માટે પ્રાપ્ત કરે છે. અન્ય અવરોધ એ છે કે તમામ મશીનો પરની નોકરીઓની સંખ્યા ઉપર અથવા નીચે ગોળાકાર હોવી જોઈએ. પ્રતિબંધિત એલ. પી. ટી. અથવા આર. એલ. પી. ટી. તરીકે ઓળખાતા એલ. પી. ટી. ના અનુકૂલનમાં, ઇનપુટ્સ જોડીમાં સોંપવામાં આવે છે-દરેક મશીનને એક (એમ = 2 મશીનો માટે). પરિણામી પાર્ટીશન ડિઝાઇન દ્વારા સંતુલિત છે. કોફમેન, ફ્રેડરિકસન અને લ્યુકર દર્શાવે છે કે જ્યારે ઇનપુટ્સ સમાનરૂપે વહેંચાયેલા હોય ત્યારે આરએલપીટીનો અપેક્ષિત સૌથી મોટો સરવાળો બરાબર છે. સૌથી મોટી અને સૌથી નાની રકમ વચ્ચેનો અપેક્ષિત તફાવત છે. કર્નલની મર્યાદાઓ-બિન-એક સાથે ઉપલબ્ધતા કર્નલ પાર્ટીશનિંગ સમસ્યામાં, કર્નલ તરીકે ઓળખાતી કેટલીક m પૂર્વ-નિર્દિષ્ટ નોકરીઓ છે, અને દરેક કર્નલને એક અનન્ય મશીનમાં સુનિશ્ચિત કરવું આવશ્યક છે. એક સમકક્ષ સમસ્યા એ છે કે જ્યારે મશીનો જુદા જુદા સમયે ઉપલબ્ધ હોય ત્યારે સમયપત્રક તૈયાર કરવુંઃ દરેક મશીન i અમુક સમયે ઉપલબ્ધ થાય છે (સમય ti ને કર્નલ જોબની લંબાઈ તરીકે વિચારી શકાય છે). એક સરળ હ્યુરિસ્ટિક અલ્ગોરિધમ, જેને એસ. એલ. પી. ટી. કહેવાય છે, તે દરેક કર્નલને અલગ ઉપગણમાં સોંપે છે, અને પછી એલ. પી. ટી. અલ્ગોરિધમ ચલાવે છે. લી સાબિત કરે છે કે આ સંશોધનાત્મક લઘુત્તમ સૌથી મોટી રકમ માટે ચુસ્ત અંદાજ ગુણોત્તર ધરાવે છે. તે પછી તે બીજા તબક્કામાં, એલ. પી. ટી. નું સુધારેલું સંસ્કરણ ચલાવવા માટે સૂચવે છે, અને સાબિત કરે છે કે તે અંદાજ ગુણોત્તર પ્રાપ્ત કરે છે. લિન, યાઓ અને તે સાબિત કરે છે કે આ સંશોધનાત્મક મહત્તમ સૌથી નાની રકમ માટે ચુસ્ત અંદાજ ગુણોત્તર ધરાવે છે. શેન, વાંગ અને વાંગ આ સેટિંગ માટે વિવિધ ઉદ્દેશ્ય કાર્યોનો અભ્યાસ કરે છે અને બહુપદી-સમયના અલ્ગોરિધમ્સ રજૂ કરે છે. ઓનલાઇન સેટિંગ્સ ઘણીવાર, ઇનપુટ્સ ઓનલાઇન આવે છે, અને જ્યારે તેઓ આવે ત્યારે જ તેમના કદની જાણ થાય છે. આ કિસ્સામાં, તેમને અગાઉથી સૉર્ટ કરવું શક્ય નથી. લિસ્ટ શેડ્યુલિંગ એ એક સમાન અલ્ગોરિધમ છે જે સૂચિને કોઈપણ ક્રમમાં લે છે, જરૂરી નથી કે તેને સૉર્ટ કરવામાં આવે. તેનો અંદાજ ગુણોત્તર છે. ઓનલાઇન સેટિંગમાં એલ. પી. ટી. નું વધુ વ્યવહારદક્ષ અનુકૂલન 3/2 નો અંદાજ ગુણોત્તર પ્રાપ્ત કરે છે. અમલીકરણ પાયથોનઃ નંબર પાર્ટીશનિંગ પેકેજમાં તેમજ પીઆરટીપી પેકેજમાં એલપીટી ("લોભી") નું અમલીકરણ છે. મલ્ટીવે નંબર પાર્ટીશનિંગની સમસ્યા માટે લોભી નંબર પાર્ટીશનિંગ-સામાન્યીકરણ અને એલ. પી. ટી. ના વિસ્તરણ પણ જુઓ. નોંધો સંદર્ભો સમયપત્રક અલ્ગોરિધમ્સ સંખ્યા પાર્ટીશનિંગ