Longest-processing-time-first scheduling
நீண்ட-செயலாக்க-நேர-முதல் (எல்பிடி) என்பது வேலை திட்டமிடலுக்கான பேராசை வழிமுறை ஆகும். வழிமுறையின் உள்ளீடு என்பது வேலைகளின் தொகுப்பாகும், அவை ஒவ்வொன்றும் ஒரு குறிப்பிட்ட செயலாக்க நேரத்தைக் கொண்டுள்ளன. வேலைகளைச் செயலாக்கக்கூடிய இயந்திரங்களின் எண்ணிக்கையைக் குறிப்பிடும் எண்ணும் m உள்ளது. எல். பி. டி வழிமுறை பின்வருமாறு செயல்படுகிறதுஃ வேலைகளை அவற்றின் செயலாக்க நேரத்தின் இறங்கு வரிசையில் வரிசைப்படுத்துங்கள், அதாவது மிக நீண்ட செயலாக்க நேரத்துடன் கூடிய வேலை முதலில் இருக்கும். இந்த வரிசையில் உள்ள ஒவ்வொரு வேலையையும் தற்போதைய சுமை (= திட்டமிடப்பட்ட வேலைகளின் மொத்த செயலாக்க நேரம்) மிகச்சிறியதாக இருக்கும் ஒரு இயந்திரமாக திட்டமிடுங்கள். வழிமுறையின் படி 2 அடிப்படையில் பட்டியல்-திட்டமிடல் (எல்எஸ்) வழிமுறையாகும். வித்தியாசம் என்னவென்றால், எல்எஸ் ஒரு தன்னிச்சையான வரிசையில் வேலைகளை சுழற்றுகிறது, அதே நேரத்தில் எல்பிடி செயலாக்க நேரத்தை குறைப்பதன் மூலம் அவற்றை முன்கூட்டியே ஆர்டர் செய்கிறது. எல். பி. டி முதன்முதலில் 1960 களில் ரொனால்ட் கிரஹாமால் ஒரே மாதிரியான இயந்திரங்கள் திட்டமிடல் சிக்கலின் பின்னணியில் பகுப்பாய்வு செய்யப்பட்டது. பின்னர், இது பிரச்சினையின் பல வகைகளுக்கு பயன்படுத்தப்பட்டது. பல்வழி எண் பகிர்வுக்கான ஒரு வழிமுறையாக LPT ஐ இன்னும் சுருக்கமான முறையில் விவரிக்கலாம். உள்ளீடு என்பது எண்களின் தொகுப்பு 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 க்கு சமமாக இருக்கும். இருப்பினும், அதன் துணை உகந்த தன்மை மோசமான நிலையில் மற்றும் சராசரி விஷயத்தில் வரையறுக்கப்பட்டுள்ளது; கீழே உள்ள செயல்திறன் உத்தரவாதங்களைப் பார்க்கவும். LPT இன் இயங்கும் நேரம் வரிசைப்படுத்தலால் ஆதிக்கம் செலுத்துகிறது, இது O (n log n) நேரத்தை எடுக்கும், இதில் n என்பது உள்ளீடுகளின் எண்ணிக்கை. செயல்திறன் உத்தரவாதங்கள்ஃ ஒரே மாதிரியான இயந்திரங்கள் ஒரே மாதிரியான இயந்திரங்களின் திட்டமிடலுக்கு பயன்படுத்தப்படும்போது, LPT பின்வரும் தோராய விகிதங்களை அடைகிறது. மோசமான நிலையில் அதிகபட்ச தொகை மிக மோசமான நிலையில், பேராசை பகிர்வில் மிகப்பெரிய தொகை பெரும்பாலான நேரங்களில் உகந்த (குறைந்தபட்ச) மிகப்பெரிய தொகையாகும். மேலும் விரிவான பகுப்பாய்வு உகந்த (குறைந்தபட்ச) மிகப்பெரிய தொகையின் மடங்குகளின் காரணியை வழங்குகிறது. (எடுத்துக்காட்டாக, m = 2 ஆக இருக்கும்போது இந்த விகிதம்). காரணி இறுக்கமாக உள்ளது. உள்ளீடுகள் உள்ளன என்று வைத்துக்கொள்வோம் (m சமமாக இருக்கும் இடத்தில்): பின்னர் பேராசை வழிமுறை திரும்புகிறதுஃ,. அதிகபட்சத்துடன், ஆனால் உகந்த பகிர்வுஃ. அதிகபட்சத்துடன். உள்ளீடு பரிசீலனை இன்னும் விரிவான பகுப்பாய்வு அதிகபட்ச தொகை பகுதியில் உள்ளீடுகளின் எண்ணிக்கையை கணக்கில் எடுத்துக்கொள்கிறது. பேராசை பகிர்வின் ஒவ்வொரு பகுதியிலும், ஜே-வது மிக உயர்ந்த எண் அதிகபட்சமாக உள்ளது. அதிகபட்ச தொகையுடன் பேராசை கொண்ட பகுதி P இல், L உள்ளீடுகள் உள்ளன என்று வைத்துக்கொள்வோம். பின்னர், பேராசை வழிமுறையின் தோராய விகிதம். இது L ≤ 3 க்கு இறுக்கமாக உள்ளது (L = 3 க்கு, பொதுவான காரணியைப் பெறுகிறோம்). சான்று. P இல் உள்ள எண்களை x1,., xL ஆல் குறிக்கவும். P இல் xL சேர்க்கப்படுவதற்கு முன்பு, அதன் கூட்டுத்தொகை மிகச்சிறியதாக இருந்தது. எனவே, ஒரு பகுதிக்கான சராசரி தொகை குறைந்தபட்சம் x1 +. + xL-1 + xL/m ஆகும். உகந்த அதிகபட்ச தொகை குறைந்தபட்சம் சராசரி தொகையாக இருக்க வேண்டும். இதற்கு மாறாக, பேராசை தொகை x1 +. + xL-1 + xL ஆகும். எனவே வித்தியாசம் அதிகபட்சமாக (1-1/மீ) xL ஆகும், இது (1) ஆல் அதிகபட்சமாக (1-1/மீ) * ஓபிடி/எல் ஆகும். எனவே விகிதம் அதிகபட்சமாக (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 க்கும் குறைவான தொகை கொண்ட ஒரு மூட்டை இருப்பதால், பேராசை வழிமுறை முந்தைய லெம்மாவுக்கு முரணாக பை இல் வேறு எந்த உள்ளீட்டையும் வைக்காது. ஒவ்வொரு பேராசை கொண்ட தொட்டி பை-யிலும் மூன்றில் ஒரு பங்கை விட பலவீனமாக-பெரியதாக ஒரு உள்ளீடு இருக்கும். ஆதாரம்ஃ அத்தகைய இரண்டு உள்ளீடுகள் ஒதுக்கப்பட்ட முதல் பேராசை தொட்டியாக பை இருக்கட்டும். உள்ளீடுகள் இறங்கு வரிசையில் ஒதுக்கப்படுவதால், பை என்பது இரண்டு உள்ளீடுகளுக்கு ஒதுக்கப்பட்ட முதல் பேராசை தொட்டி ஆகும். இதன் பொருள் என்னவென்றால், இது மிகப்பெரிய m + 1 உள்ளீடுகளில் இருந்து மிகச்சிறிய இரண்டு உள்ளீடுகளைக் கொண்டிருக்க வேண்டும். மேலும், இந்த இரண்டு உருப்படிகளின் கூட்டுத்தொகை குறைந்தபட்சம் 3/2+3 2 = 3 என்பதால், Pi க்கு வேறு எந்த உள்ளீடும் ஒதுக்கப்படவில்லை. மறுபுறம், புறா துளை கொள்கையின்படி, சில உகந்த பின் கியூஜே இருக்க வேண்டும், அதில் மிகப்பெரிய எம் + 1 உள்ளீடுகளில் இருந்து இரண்டு உள்ளீடுகள் உள்ளன; எனவே பை கியூஜே ஆல் ஆதிக்கம் செலுத்துகிறது. பேராசை வழிமுறையின் ஓட்டத்தின் போது, ஒவ்வொரு தொட்டி பையிலும் உள்ள தொகை குறைந்தபட்சம் 8/3 ஆக மாறும், எந்தவொரு தொட்டி கூட்டுத்தொகையும் 4 ஐ விட அதிகமாக இருக்கும். ஆதாரம்ஃ சில பின் பையில் சேர்க்கப்பட்ட முதல் உள்ளீடாக y இருக்கட்டும், இது அதன் கூட்டுத்தொகையை 4 ஐ விட பெரியதாக மாற்றியது. y சேர்க்கப்படுவதற்கு முன்பு, பை மிகச்சிறிய கூட்டுத்தொகையைக் கொண்டிருந்தது, இது அனுமானத்தால் 8/3 ஐ விட சிறியதாக இருந்தது; இதன் பொருள் y> 4/3. முதல் உள்ளீடு முதல் y வரை உள்ள அனைத்து உள்ளீடுகளின் தொகுப்பையும் T குறிக்கட்டும்; இந்த உள்ளீடுகள் அனைத்தும் 4/3 ஐ விட பெரியவை. பை 8/3 ஐ விட சிறியதாக இருந்ததால், அதில் டி இலிருந்து சரியாக ஒரு உருப்படி x இருந்தது. எனவே இப்போது பை சரியாக 2 உருப்படிகளைக் கொண்டுள்ளது, மேலும் வழிமுறை முடிவடையும் வரை இந்த 2 உருப்படிகளுடன் உள்ளது. m என்பது முதல் உருப்படியிலிருந்து x வரை உள்ள உருப்படிகளின் எண்ணிக்கையாக இருக்கட்டும். இப்போது T இல் உள்ள உருப்படிகளை இரண்டு வழிகளில் எண்ணுவதன் மூலம் ஒரு முரண்பாட்டைக் காட்டுகிறோம். முதலில், n உகந்த தொட்டிகளைக் கவனியுங்கள். அத்தகைய தொட்டியில் குறைந்தபட்சம் x போன்ற பெரிய உருப்படி இருந்தால், அது T இன் வேறு எந்த உருப்படியையும் கொண்டிருக்க முடியாது, இல்லையெனில் அது {x, y} ஐ ஆதிக்கம் செலுத்துகிறது. மேலும், அத்தகைய தொட்டி T இலிருந்து மூன்று உருப்படிகளைக் கொண்டிருக்க முடியாது, ஏனெனில் அவற்றில் ஏதேனும் இரண்டின் கூட்டுத்தொகை 8/3 ஐ விட பெரியது, இது x ஐ விட பெரியது; மூன்றாவது ஒன்று குறைந்தபட்சம் y ஆகும், எனவே அது {x, y} ஐ ஆதிக்கம் செலுத்துகிறது. எனவே, T இல் உள்ள பொருட்களின் எண்ணிக்கை அதிகபட்சமாக 1 * m + 2 * (n-m) = 2n-m ஆகும். x ஐக் கொண்ட மூட்டையில் y சேர்க்கும்போது, அது மிகச்சிறிய தொகையைக் கொண்ட மூட்டை ஆகும். எனவே, x ஐ விட சிறியதாக இருக்கும் T இன் அனைத்து உறுப்புகளும், குறைந்தபட்சம் T இன் மற்றொரு உருப்படியுடன் ஒரு பேராசை தொட்டியில் இருக்க வேண்டும். எனவே, T இல் உள்ள உருப்படிகளின் எண்ணிக்கை குறைந்தபட்சம் (m-1) + 2 * (n-m + 1) = 2n-m + 1-முரண்பாடு. பொதுவான தன்மையை இழக்காமல், அனைத்து உள்ளீடுகளும் மூன்றில் ஒரு பங்கை விட சிறியவை அல்லது குறைந்தபட்சம் மூன்றில் ஒரு பங்கை விட சிறியவை என்று நாம் கருதலாம். ஆதாரம்ஃ சில உள்ளீடு x (1/3,1) இல் உள்ளது என்று வைத்துக்கொள்வோம். நாம் x ஐ 1 உடன் மாற்றுகிறோம். இது வெளிப்படையாக உகந்த குறைந்தபட்ச தொகையை குறைக்காது. இது பேராசை கொண்ட குறைந்தபட்ச தொகையை மாற்றாது என்பதை நாங்கள் காட்டுகிறோம். சில பேராசை மூட்டை பை 4 ஐ விட பெரிய இறுதி தொகையை கொண்டுள்ளது என்பது எங்களுக்குத் தெரியும். கடைசி உள்ளீடு பை இல் சேர்க்கப்படுவதற்கு முன்பு, அதன் தொகை 3 ஐ விட சிறியதாக இருந்தது, எனவே 1 ஐ விட பெரிய உள்ளீடு சேர்க்கப்படும்போது பை 4 ஐ விட பெரியதாக மாறியது. முந்தைய லெம்மாவில், அந்த நேரத்தில் மற்ற அனைத்து பேராசை மூட்டைகளின் கூட்டுத்தொகையும் குறைந்தது 8/3 ஆக இருந்தது. அல்காரிதம் பின்னர் x க்கு வருகிறது. வழிமுறை x ஐ சில பின் Pj உடன் சேர்த்தவுடன், Pj இன் கூட்டுத்தொகை குறைந்தது 8/3+1 3 = 3 ஆக மாறும், எனவே மேலும் உருப்படிகள் Pj இல் சேர்க்கப்படாது. எனவே Pj இல் [1/3,1] அளவுடன் ஒரே ஒரு உள்ளீடு மட்டுமே உள்ளது. x ஆனது 1 ஆல் மாற்றப்பட்டவுடன், அது இன்னும் Pj இல் செருகப்படுகிறது, மேலும் அதன் கூட்டுத்தொகை இன்னும் 3 க்கு மேல் உள்ளது. எனவே பேராசை கொண்ட குறைந்தபட்ச தொகை மாறாது. இப்போது நாம் உள்ளீடுகளை சிறியதாகவும் (மூன்றில் ஒரு பங்கிற்கு குறைவாக) பெரியதாகவும் (குறைந்தபட்சம் 1) பிரிக்கலாம். பை இல் உள்ள சிறிய பொருட்களின் தொகுப்பு சி ஆல் குறிக்கப்படுகிறது. அல்காரிதம் சிறிய உருப்படிகளை செயலாக்கத் தொடங்கும் போது, அனைத்து மூட்டைகளிலும் உள்ள தொகை குறைந்தது 8/3 ஆகும் என்பதை நினைவில் கொள்க. ஒரு குறைந்தபட்ச எதிர் உதாரணம் இல்லை என்பதற்கான சான்று ஒரு எடை திட்டத்தை பயன்படுத்துகிறது. ஒவ்வொரு உள்ளீடு x க்கும் அதன் அளவு மற்றும் பேராசை மூட்டைக்கு ஏற்ப ஒரு எடை w (x) ஒதுக்கப்பட்டுள்ளது பைஃ x ஒரு பெரிய உருப்படி என்றால்ஃ x என்பது பை இல் உள்ள ஒற்றை பெரிய உருப்படி என்றால், பின்னர் w (x) = 8/3. பை இல் சரியாக இரண்டு உருப்படிகள் {x, y} இருந்தால், அவை இரண்டும் பெரியவை, மற்றும் x> y, மற்றும் கூட்டுத்தொகை (பை) ≤3, பின்னர் w (x) = 8/3. இல்லையெனில், w (x) = 4/3. x ஒரு சிறிய உருப்படி என்றால்ஃ கூட்டுத்தொகை (Pi) ≤3 என்றால், பின்னர் w (x) = 4x/(3 கூட்டுத்தொகை (Si)); எனவே w (Si) = 4/3. கூட்டுத்தொகை (Pi) <3 என்றால், பின்னர் w (x) = 2x/(3 கூட்டுத்தொகை (Si)); எனவே w (Si) = 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 சிறியது. இது பை இல் உள்ளது என்று வைத்துக்கொள்வோம். கூட்டுத்தொகை (Pi) 3 என்றால், x சேர்க்கப்படுவதற்கு முன்பு கூட்டுத்தொகை (Pi) 3 ஐ விட சிறியதாக இருந்ததால், அது இப்போது 10/3 ஐ விட சிறியதாக உள்ளது. ஆனால் அல்காரிதம் சிறிய உருப்படிகளை செயலாக்கத் தொடங்கியபோது, கூட்டுத்தொகை (பை) குறைந்தது 8/3 ஆக இருந்தது. இதன் பொருள் கூட்டுத்தொகை (Si) <2/3, எனவே w (x) = 4x/(3 கூட்டுத்தொகை (Si))> 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 எடையுடன் மூன்று உள்ளீடுகள் உள்ளன. பை இல் உள்ள சில உள்ளீடுகள் சிறியதாக இருந்தால், அவற்றின் மொத்த எடை அதிகபட்சம் 3/4 ஆகும். அதிகபட்சம் இரண்டு பெரிய உள்ளீடுகள் உள்ளன, அவற்றின் எடைகள் 8/3 அல்லது 4/3+4 3 ஆகும். இறுதியாக, 3 க்கும் குறைவான தொகை கொண்ட பேராசை தொட்டியின் எடை அதிகபட்சம் 8/3 (அதில் பெரிய உள்ளீடுகள் மட்டுமே இருந்தால்) அல்லது 10/3 (அதில் சில சிறிய உள்ளீடுகள் இருந்தால்). ஒவ்வொரு உகந்த பின் கியூஜேவின் எடையும் குறைந்தது 4 ஆகும். ஆதாரம்ஃ க்யூஜே சிறிய உருப்படிகளை மட்டுமே கொண்டிருந்தால், அவை ஒவ்வொன்றும் டபிள்யூ (எக்ஸ்)> 2x ஐ திருப்திப்படுத்துகின்றன, எனவே டபிள்யூ (க்யூஜே)> 2 தொகை (க்யூஜே) ≤8. Qj இல் சரியாக ஒரு பெரிய உருப்படி 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. இப்போது Qj இல் உள்ள எந்த சிறிய உருப்படியையும் கருத்தில் கொள்ளுங்கள், அது ஏதோ பேராசை கொண்ட பின் பையில் உள்ளது என்று வைத்துக்கொள்வோம். கூட்டுத்தொகை (பை) <3 என்றால், வி பை இல் வைக்கப்படவில்லை என்ற உண்மை v> 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 மற்றும் நாம் முடித்துவிட்டோம். t சேர்க்கப்படுவதற்கு முன்பு கூட்டுத்தொகை (Pi) 3 க்கும் குறைவாக இருந்ததால், கூட்டுத்தொகை (Pi) <3 + கூட்டுத்தொகை (Si)/2. வி பை இல் வைக்கப்படவில்லை என்ற உண்மை v> 4-தொகை (பெரிய-உருப்படிகள்-இன்-பை)> 1 + தொகை (சிறிய-உருப்படிகள்-இன்-பை)/2 என்பதைக் குறிக்கிறது. முந்தைய பத்திக்கு ஒத்த, w (t)> 4t/(3sum (சிறிய-உருப்படிகள்-இன்-கியூஜே)). எனவே, Qj இல் உள்ள அனைத்து சிறிய பொருட்களின் மொத்த எடை குறைந்தது 4/3 ஆகும், எனவே Qj இன் மொத்த எடை குறைந்தது 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,., மீ, மீ. கடைசி மீ-1 உள்ளீடுகள் அனைத்தும் மீ. பின்னர் பேராசை வழிமுறை திரும்புகிறதுஃ 2 மீ-1, மீ, மீ 2 மீ-1, மீ, மீ 2 மீ-2, மீ + 1, மீ 2 மீ-2, மீ + 1, மீ. 3 மீ/2,3 மீ/2-1, மீ 3 மீ/2,3 மீ/2-2 குறைந்தபட்சம் 3 மீ-1 உடன். ஆனால் உகந்த பகிர்வுஃ 2 மீ-1,2 மீ-2, மீ, மீ 2 மீ-2, மீ, மீ 2 மீ-3, மீ + 1, மீ 2 மீ-3, மீ + 1, மீ. 3 மீ/2,3 மீ/2-2, மீ 3 மீ/2,3 மீ/2-2, மீ 3 மீ/2-2, மீ 3 மீ/2-2,3 மீ/2-2, மீ குறைந்தபட்சம் 4 மீ-2. கட்டுப்படுத்தப்பட்ட LPT LPT இன் ஒரு மாறுபாடு உள்ளது, இது கட்டுப்படுத்தப்பட்ட-LPT அல்லது RLPT என்று அழைக்கப்படுகிறது, இதில் உள்ளீடுகள் தரவரிசைகள் எனப்படும் அளவு m இன் துணைக்குழுக்களாக பிரிக்கப்படுகின்றன (தரவரிசை 1 மிகப்பெரிய m உள்ளீடுகளைக் கொண்டுள்ளது, தரவரிசை 2 அடுத்த பெரிய m உள்ளீடுகள் போன்றவை). ஒவ்வொரு தரவரிசையிலும் உள்ளீடுகள் m வெவ்வேறு தொட்டிகளுக்கு ஒதுக்கப்பட வேண்டும்ஃ தரவரிசை 1 முதலில், பின்னர் தரவரிசை 2, போன்றவை. ஆர். எல். பி. டி. யில் குறைந்தபட்ச தொகை அதிகபட்சமாக எல். பி. டி. யில் குறைந்தபட்ச தொகையாகும். குறைந்தபட்ச தொகையை அதிகரிப்பதற்கான RLPT இன் தோராய விகிதம் அதிகபட்சம் m ஆகும். சராசரி-வழக்கு அதிகபட்ச தொகை சராசரி விஷயத்தில், உள்ளீட்டு எண்கள் ஒரே மாதிரியாக [0,1] விநியோகிக்கப்பட்டால், ஒரு LPT அட்டவணையில் உள்ள மிகப்பெரிய தொகை பின்வரும் பண்புகளை திருப்திப்படுத்துகிறதுஃ m = 2 இயந்திரங்களுக்கு எதிர்பார்க்கப்படும் மிகப்பெரிய தொகை குறைந்தபட்சம் மற்றும் அதிகபட்சமாக, n என்பது உள்ளீடுகளின் எண்ணிக்கை. மிகப் பெரிய தொகை பெரும்பாலான நேரங்களில் கிட்டத்தட்ட நிச்சயமாக உகந்ததாக இருக்கும், மேலும் எதிர்பார்ப்பில், உள்ளீடுகளின் எண்ணிக்கை எங்கே? எல். பி. டி மிகப்பெரிய தொகைக்கும் உகந்த மிகப்பெரிய தொகைக்கும் இடையிலான வேறுபாடு கிட்டத்தட்ட நிச்சயமாக (சீரான அல்லது எதிர்மறை அதிவேக விநியோகங்களுக்கு), மற்றும் அதிகபட்சமாக எதிர்பார்ப்பில் (சீரான விநியோகத்திற்கு) உள்ளது. இந்த முடிவுகள் வெவ்வேறு வேகங்களைக் கொண்ட இயந்திரங்களுக்கும் பொருந்தும். பொதுவான குறிக்கோள்கள் Ci (i க்கு 1 மற்றும் m க்கு இடையில்) கொடுக்கப்பட்ட பகிர்வில் உள்ள துணைக்குழு i இன் கூட்டுத்தொகையாக இருக்கட்டும். அப்ஜெக்டிவ் ஃபங்ஷன் அதிகபட்சம் (சிஐ) ஐக் குறைப்பதற்குப் பதிலாக, அப்ஜெக்டிவ் ஃபங்ஷன் அதிகபட்சம் (எஃப் (சிஐ)) ஐக் குறைக்கலாம், இதில் எஃப் என்பது எந்த நிலையான செயல்பாடும் ஆகும். இதேபோல், ஒருவர் புறநிலை செயல்பாட்டு கூட்டுத்தொகையை (f (Ci)) குறைக்கலாம். அலோன், அஸார், வோயிஞ்சர் மற்றும் யாடிட் ஆகியோர் பின்வரும் இரண்டு நிபந்தனைகளை பூர்த்தி செய்தால்ஃ நிபந்தனை F * என்று அழைக்கப்படும் ஒரு வலுவான தொடர்ச்சியான நிபந்தனைஃ ஒவ்வொரு ε> 0 க்கும் δ> 0 உள்ளது, அதாவது |y-x | <δx என்றால், |f (y)-f (x) | <εf (x). மூச்சுத்திணறல். பின்னர் LPT விதி தொகை (f (Ci)) ஐக் குறைப்பதற்கான ஒரு வரையறுக்கப்பட்ட தோராய விகிதத்தைக் கொண்டுள்ளது. மற்ற அமைப்புகளுக்கான தழுவல்கள் ஒரே மாதிரியான இயந்திரங்களின் திட்டமிடலின் எளிய வழக்கைத் தவிர, LPT மிகவும் பொதுவான அமைப்புகளுக்கு ஏற்றவாறு மாற்றியமைக்கப்பட்டுள்ளது. சீரான இயந்திரங்கள் சீரான இயந்திரங்கள் திட்டமிடுதலில், வெவ்வேறு இயந்திரங்கள் வெவ்வேறு வேகங்களைக் கொண்டிருக்கலாம். எல். பி. டி விதி ஒவ்வொரு வேலையையும் இயந்திரத்திற்கு ஒதுக்குகிறது, அதில் அதன் நிறைவு நேரம் விரைவாக இருக்கும் (அதாவது, எல். பி. டி ஒரு பெரிய மின்னோட்ட சுமை கொண்ட ஒரு இயந்திரத்திற்கு ஒரு வேலையை ஒதுக்கலாம், இந்த இயந்திரம் மற்ற எல்லா இயந்திரங்களையும் விட முன்னதாக அந்த வேலையை முடிக்கும் அளவுக்கு வேகமாக இருந்தால்). M சீருடை இயந்திரங்களுடன் LPT இன் தோராயமான விகிதம் அதிகபட்சமாக உள்ளது என்பதை கோன்சலஸ், இபரா மற்றும் சஹானி காட்டுகின்றன. இது இறுக்கமாக இல்லை, ஆனால் மீ முடிவிலியை நெருங்கும் போது 1.5 என்ற அறிகுறியற்ற கீழ் வரம்பு உள்ளது. m = 2 இயந்திரங்களின் சிறப்பு வழக்கில், தோராய விகிதம் அதிகபட்சமாக உள்ளது மற்றும் அது இறுக்கமாக உள்ளது. மிரால்ட், ஓர்லின் மற்றும் வோஹ்ரா ஆகியோர் இரண்டு இயந்திரங்களுடன் ஒரு அமைப்பை ஆய்வு செய்கிறார்கள், இதில் ஒரு இயந்திரம் மற்றொன்றை விட q மடங்கு வேகமாக இருக்கும். அவர்கள் LPT இன் தோராய விகிதத்தை q இன் செயல்பாடாக கணக்கிடுகிறார்கள். q = 1 ஆக இருக்கும்போது, அவற்றின் முடிவு ஒரே மாதிரியான இயந்திரங்களுக்கு அறியப்பட்ட 7/6 காரணியுடன் ஒத்துப்போகிறது. கௌலாமாஸ் மற்றும் கிபாரிசிஸ் ஆகியோர் எல். பி. டி. யின் மாற்றத்தை முன்வைக்கின்றனர், இதில் மூன்று மிக நீண்ட வேலைகள் உகந்த முறையில் திட்டமிடப்பட்டுள்ளன, மீதமுள்ள வேலைகள் எல். பி. டி விதியின் அடிப்படையில் திட்டமிடப்பட்டுள்ளன. இரண்டு இயந்திரங்களுக்கான தோராய விகிதம் மற்றும் அது இறுக்கமாக உள்ளது. கார்டினலிட்டி கட்டுப்பாடுகள் சமநிலையான பகிர்வு சிக்கலில், ஒவ்வொரு இயந்திரத்திற்கும் ஒதுக்கக்கூடிய வேலைகளின் எண்ணிக்கையில் கட்டுப்பாடுகள் உள்ளன. ஒரு எளிய தடை என்னவென்றால், ஒவ்வொரு இயந்திரமும் அதிகபட்சம் சி வேலைகளை செயலாக்க முடியும். எல். பி. டி விதி ஒவ்வொரு வேலையையும் சி வேலைகளை விட குறைவான சுமைகளைக் கொண்ட இயந்திரத்திற்கு ஒதுக்குகிறது. இந்த விதி மாற்றியமைக்கப்பட்ட எல்பிடி அல்லது எம்எல்பிடி என்று அழைக்கப்படுகிறது. கெல்லர் மற்றும் வோயிஞ்சர் ஒரு மாறுபாட்டை ஆய்வு செய்கிறார்கள், அதில் அதிகபட்சம் 3 * மீ வேலைகள் உள்ளன, மேலும் ஒவ்வொரு இயந்திரத்திலும் அதிகபட்சம் 3 வேலைகள் இருக்க வேண்டும் (இது 3-பகிர்வு சிக்கலின் பொதுமைப்படுத்தலாகக் காணலாம்). எம்எல்பிடி குறைந்தபட்ச மிகப்பெரிய தொகையை அடைகிறது என்பதை அவை காட்டுகின்றன, இது கட்டுப்பாடற்ற சிக்கலுக்கு எல்பிடி அடையும் அதே தோராய விகிதமாகும். எம்எல்பிடிக்கு எல்லை இறுக்கமாக உள்ளது. எம்எல்பிடி மிகவும் பொதுவான கார்டினாலிட்டி கட்டுப்பாடுகளுக்கு (சி> 3) அதே தோராய விகிதத்தைக் கொண்டுள்ளது என்று ஊகிக்கப்படுகிறது. தற்போது, பொதுவான சி> 3 க்கான எம். எல். பி. டி. யின் தோராய விகிதம் அதிகபட்சம் 2 என்று அறியப்படுகிறது. சென், ஹீ மற்றும் லின், அதே சிக்கலுக்கு, எம். எல். பி. டி குறைந்தபட்சம் அதிகபட்ச மிகச்சிறிய தொகையை அடைகிறது என்பதைக் காட்டுகிறது, இது மீண்டும் கட்டுப்பாடற்ற சிக்கலுக்கு எல். பி. டி அடையும் அதே விகிதமாகும். மற்றொரு தடை என்னவென்றால், அனைத்து இயந்திரங்களிலும் உள்ள வேலைகளின் எண்ணிக்கை மேலே அல்லது கீழே வட்டமிடப்பட வேண்டும். கட்டுப்படுத்தப்பட்ட LPT அல்லது RLPT எனப்படும் LPT இன் தழுவலில், உள்ளீடுகள் ஜோடிகளாக ஒதுக்கப்படுகின்றன-ஒவ்வொரு இயந்திரத்திற்கும் ஒன்று (m = 2 இயந்திரங்களுக்கு). இதன் விளைவாக வரும் பகிர்வு வடிவமைப்பால் சமநிலைப்படுத்தப்படுகிறது. காஃப்மேன், ஃப்ரெடெரிக்சன் மற்றும் லுக்கர் ஆகியோர் உள்ளீடுகள் ஒரே சீராக விநியோகிக்கப்படும் போது RLPT இன் எதிர்பார்க்கப்படும் மிகப்பெரிய தொகை சரியாக இருக்கும் என்பதைக் காட்டுகிறார்கள். மிகப்பெரிய மற்றும் மிகச்சிறிய தொகைக்கு இடையே எதிர்பார்க்கப்படும் வேறுபாடு. கர்னல் கட்டுப்பாடுகள்-ஒரே நேரத்தில் கிடைக்காதது கர்னல் பகிர்வு சிக்கலில், கர்னல்கள் எனப்படும் சில முன்-குறிப்பிடப்பட்ட வேலைகள் உள்ளன, மேலும் ஒவ்வொரு கர்னலும் ஒரு தனித்துவமான இயந்திரத்திற்கு திட்டமிடப்பட வேண்டும். வெவ்வேறு நேரங்களில் இயந்திரங்கள் கிடைக்கும்போது திட்டமிடுவது ஒரு சமமான சிக்கலாகும்ஃ ஒவ்வொரு இயந்திரமும் i ஒரு நேரத்தில் ti ≤ 0 இல் கிடைக்கிறது (நேரம் ti கர்னல் வேலையின் நீளம் என்று கருதலாம்). எஸ்எல்பிடி என்று அழைக்கப்படும் ஒரு எளிய ஹூரிஸ்டிக் அல்காரிதம், ஒவ்வொரு கர்னலையும் வெவ்வேறு துணைக்குழுவிற்கு ஒதுக்கி, பின்னர் எல்பிடி அல்காரிதத்தை இயக்குகிறது. இந்த ஹூரிஸ்டிக் குறைந்தபட்ச மிகப்பெரிய தொகைக்கு இறுக்கமான தோராய விகிதத்தைக் கொண்டுள்ளது என்பதை லீ நிரூபிக்கிறார். இரண்டாவது கட்டத்தில், எல். பி. டி. யின் மாற்றியமைக்கப்பட்ட பதிப்பை இயக்க அவர் பரிந்துரைக்கிறார், மேலும் இது ஒரு தோராயமான விகிதத்தை அடைகிறது என்பதை நிரூபிக்கிறது. லின், யாவோ மற்றும் அவர் இந்த ஹூரிஸ்டிக் அதிகபட்ச மிகச்சிறிய தொகைக்கு இறுக்கமான தோராய விகிதத்தைக் கொண்டுள்ளது என்பதை நிரூபிக்கின்றனர். ஷென், வாங் மற்றும் வாங் ஆகியோர் இந்த அமைப்பிற்கான வெவ்வேறு புறநிலை செயல்பாடுகளை ஆய்வு செய்கிறார்கள், மேலும் பல்லுறுப்புக்கோவை-நேர வழிமுறைகளை வழங்குகிறார்கள். ஆன்லைன் அமைப்புகள் பெரும்பாலும், உள்ளீடுகள் ஆன்லைனில் வருகின்றன, அவற்றின் அளவுகள் அவை வரும்போது மட்டுமே அறியப்படுகின்றன. இந்த விஷயத்தில், அவற்றை முன்கூட்டியே வரிசைப்படுத்த முடியாது. பட்டியல் திட்டமிடல் என்பது ஒரு ஒத்த வழிமுறையாகும், இது ஒரு பட்டியலை எந்த வரிசையிலும் எடுக்கிறது, அது வரிசைப்படுத்தப்பட வேண்டிய அவசியமில்லை. அதன் தோராய விகிதம். ஒரு ஆன்லைன் அமைப்புக்கு LPT இன் மிகவும் அதிநவீன தழுவல் 3/2 என்ற தோராயமான விகிதத்தை அடைகிறது. செயல்பாடுகள் பைதான்ஃ எண் பகிர்வு தொகுப்பிலும், அதே போல் ப்ராடிபி தொகுப்பிலும் எல்பிடி ("பேராசை") செயல்படுத்தப்படுகிறது. மேலும் காண்க பேராசை எண் பகிர்வு-பல்வழி எண் பகிர்வு சிக்கலுக்கான LPT இன் பொதுமைப்படுத்தல்கள் மற்றும் நீட்டிப்புகள். குறிப்புகள் குறிப்புகள் திட்டமிடல் வழிமுறைகள் எண் பகிர்வு