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}। বৈশিষ্ট্যাবলী এল. পি. টি সর্বোত্তম বিভাজন খুঁজে নাও পেতে পারে। উদাহরণস্বরূপ, উপরের উদাহরণে সর্বোত্তম পার্টিশন {8,7}, {6,5,4}, যেখানে উভয় যোগফল 15-এর সমান। যাইহোক, এর উপ-অনুকূলতা সবচেয়ে খারাপ ক্ষেত্রে এবং গড় ক্ষেত্রে উভয় ক্ষেত্রেই সীমাবদ্ধ; নীচে পারফরম্যান্স গ্যারান্টি দেখুন। এল. পি. টি-র চলমান সময় বাছাই দ্বারা প্রভাবিত হয়, যা ও (এন লগ এন) সময় নেয়, যেখানে এন হল ইনপুটের সংখ্যা। কর্মক্ষমতার নিশ্চয়তাঃ অভিন্ন যন্ত্র যখন অভিন্ন যন্ত্রের সময় নির্ধারণের জন্য ব্যবহার করা হয়, তখন এল. পি. টি নিম্নলিখিত আনুমানিক অনুপাত অর্জন করে। সবচেয়ে খারাপ ক্ষেত্রে সর্বাধিক যোগফল সবচেয়ে খারাপ ক্ষেত্রে, লোভী বিভাজনের বৃহত্তম যোগফল বেশিরভাগ সময়ই সর্বোত্তম (ন্যূনতম) বৃহত্তম যোগফল হয়। আরও বিশদ বিশ্লেষণ সর্বোত্তম (ন্যূনতম) বৃহত্তম যোগফলের গুণের একটি ফ্যাক্টর প্রদান করে। (উদাহরণস্বরূপ, যখন m = 2 এই অনুপাতটি হয়)। ফ্যাক্টরটি শক্ত। ধরুন কিছু ইনপুট রয়েছে (যেখানে m জোড়): তারপর লোভী অ্যালগরিদম ফিরে আসেঃ,. সর্বাধিক সহ, কিন্তু সর্বোত্তম পার্টিশনটি হলঃ. সর্বাধিক সহ। ইনপুট বিবেচনা একটি আরও বিস্তারিত বিশ্লেষণ সর্বাধিক-সমষ্টি অংশে ইনপুটের সংখ্যা বিবেচনা করে। লোভী বিভাজনের প্রতিটি অংশে, জে-তম সর্বোচ্চ সংখ্যাটি সর্বাধিক। ধরুন, লোভী অংশ পি-তে সর্বোচ্চ-সমষ্টি সহ এল ইনপুট রয়েছে। তারপর, লোভী অ্যালগরিদমের আনুমানিক অনুপাত হল। এটি L ≤ 3-এর জন্য টাইট (L = 3-এর জন্য, আমরা সাধারণ ফ্যাক্টর পাই)। প্রমাণ। পি-তে সংখ্যাগুলিকে x1,., xL দ্বারা চিহ্নিত করুন। পি-তে এক্সএল ঢোকানোর আগে এর যোগফল ছিল সবচেয়ে ছোট। অতএব, প্রতি অংশের গড় যোগফল কমপক্ষে x1 +. + xL-1 + xL/m। সর্বোত্তম সর্বোচ্চ যোগফল কমপক্ষে গড় যোগফল হতে হবে। এর বিপরীতে, লোভী যোগফল হল x1 +. + xL-1 + xL। সুতরাং পার্থক্য সর্বাধিক (1-1/মি) xL, যা (1) দ্বারা সর্বাধিক (1-1/মি) * ওপিটি/এল। সুতরাং অনুপাতটি সর্বাধিক (1 + 1/এল-1/এলএম)। সবচেয়ে খারাপ ক্ষেত্রে সর্বনিম্ন যোগফল সবচেয়ে খারাপ ক্ষেত্রে, ফেরত দেওয়া পার্টিশনের সবচেয়ে ছোট যোগফলটি সর্বোত্তম (সর্বোচ্চ) ক্ষুদ্রতম যোগফলের অন্তত গুণ হয়। প্রমাণ দ্বন্দ্ব দ্বারা প্রমাণিত হয়। আমরা একটি ন্যূনতম পাল্টা উদাহরণ বিবেচনা করি, অর্থাৎ, একটি ক্ষুদ্রতম এম এবং সবচেয়ে কম ইনপুট সংখ্যা সহ একটি পাল্টা উদাহরণ। লোভী বিভাজনকে পি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। ধরা যাক টি প্রথমটি থেকে y পর্যন্ত সমস্ত ইনপুটের সেটকে নির্দেশ করে; এই সমস্ত ইনপুট 4/3 এর চেয়েও বড়। যেহেতু পাই 8/3 এর চেয়ে ছোট ছিল, এতে টি থেকে ঠিক একটি আইটেম x ছিল। সুতরাং এখন পাইতে ঠিক 2 টি আইটেম {x, y} রয়েছে এবং অ্যালগরিদম শেষ না হওয়া পর্যন্ত এই 2 টি আইটেমের সাথে থাকে। ধরা যাক m হল প্রথমটি থেকে x পর্যন্ত আইটেমের সংখ্যা। আমরা এখন দুটি উপায়ে টি-তে আইটেমগুলি গণনা করে একটি দ্বন্দ্ব দেখাই। প্রথমে, সর্বোত্তম বিনগুলি বিবেচনা করুন। যদি এই ধরনের কোনও বিন-এ কমপক্ষে x-এর মতো বড় কোনও বস্তু থাকে, তবে এতে T-এর অন্য কোনও বস্তু থাকতে পারে না, কারণ অন্যথায় এটি {x, y}-এর উপর আধিপত্য বিস্তার করে। অধিকন্তু, এই ধরনের যে কোনও বিন টি থেকে তিনটি আইটেম ধারণ করতে পারে না, কারণ তাদের মধ্যে যে কোনও দুটির যোগফল 8/3 এর চেয়ে বড়, যা x এর চেয়ে বড়; এবং তৃতীয়টি কমপক্ষে y, তাই এটি {x, y} কে প্রাধান্য দেয়। অতএব, টি-তে বস্তুর সংখ্যা সর্বাধিক 1 * মি + 2 * (এন-এম) = 2এন-এম। এখন, লোভী বিনগুলি বিবেচনা করুন। যখন x ধারণকারী বান্ডেলে y যোগ করা হয়, তখন এটি সবচেয়ে ছোট যোগফলের বান্ডিল হয়। অতএব, টি-র যে সমস্ত উপাদান x-এর চেয়ে ছোট, সেগুলি অবশ্যই একটি লোভী বিন-এ কমপক্ষে অন্য একটি টি-র সঙ্গে থাকতে হবে। অতএব, টি-তে বস্তুর সংখ্যা কমপক্ষে (এম-1) + 2 * (এন-এম + 1) = 2এন-এম + 1-দ্বন্দ্ব। সাধারণতা না হারিয়ে আমরা ধরে নিতে পারি যে সমস্ত ইনপুট হয় 1/3 বা কমপক্ষে 1 এর চেয়ে ছোট। প্রমাণঃ ধরুন কিছু ইনপুট x (1/3,1)-এ রয়েছে। আমরা x কে 1 দিয়ে প্রতিস্থাপন করি। এটি স্পষ্টতই সর্বোত্তম ন্যূনতম-সমষ্টি হ্রাস করে না। আমরা দেখাই যে এটি লোভী মিনি-সাম পরিবর্তন করে না। আমরা জানি যে কিছু লোভী বান্ডিল পাই-এর চূড়ান্ত পরিমাণ 4-এর চেয়ে বেশি। পাই-তে শেষ ইনপুট যোগ করার আগে, এর যোগফল 3-এর চেয়ে ছোট ছিল; তাই 1-এর চেয়ে বড় কিছু ইনপুট যোগ করা হলে পাই 4-এর চেয়ে বড় হয়ে যায়। পূর্ববর্তী লেম্মাতে, সেই সময়ে অন্যান্য সমস্ত লোভী বান্ডিলের যোগফল কমপক্ষে 8/3 ছিল। অ্যালগরিদমটি পরে x-এ আসে। একবার অ্যালগরিদমটি কিছু বিন পিজে-তে এক্স যোগ করলে, পিজে-এর যোগফল কমপক্ষে 8/3+1 3 = 3 হয়ে যায়, তাই পিজে-তে আর কোনও আইটেম যোগ করা হয় না। সুতরাং পিজে-তে [1/3,1) আকার সহ শুধুমাত্র একটি ইনপুট রয়েছে। একবার x কে 1 দ্বারা প্রতিস্থাপিত করা হলে, এটি এখনও পিজে-তে ঢোকানো হয় এবং এর যোগফল এখনও 3-এর উপরে থাকে। তাই লোভী মিনি-সাম পরিবর্তন হয় না। আমরা এখন ইনপুটগুলিকে ছোট (এক-তৃতীয়াংশের কম) এবং বড় (কমপক্ষে এক) ভাগে ভাগ করতে পারি। পাই-তে ছোট জিনিসের সেটকে সি দ্বারা চিহ্নিত করা হয়। লক্ষ্য করুন যে, অ্যালগরিদম যখন ছোট আইটেমগুলি প্রক্রিয়াকরণ শুরু করে, তখন সমস্ত বান্ডিলের যোগফল কমপক্ষে 8/3 হয়। একটি ন্যূনতম পাল্টা উদাহরণের অস্তিত্ব নেই তার প্রমাণ একটি ওজন পরিকল্পনা ব্যবহার করে। প্রতিটি ইনপুট x-কে তার আকার এবং লোভী বান্ডিল পাই অনুসারে একটি ওজন ডাব্লু (এক্স) বরাদ্দ করা হয়ঃ যদি এক্স একটি বড় আইটেম হয়ঃ যদি এক্স পাই-তে একক বড় আইটেম হয়, তবে ডাব্লু (এক্স) = 8/3। যদি পাই-তে ঠিক দুটি বস্তু থাকে {x, y} এবং উভয়ই বড় হয়, এবং x> y, এবং যোগফল (পাই) ≤ 3 হয়, তাহলে w (x) = 8/3। অন্যথায়, ডাব্লু (এক্স) = 4/3। যদি x একটি ছোট বস্তু হয়ঃ যদি যোগফল (পাই) ≤3 হয়, তাহলে w (x) = 4x/(3 যোগফল (সি)); সুতরাং w (সি) = 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 in (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 হল পি. এম-এ যোগ করা দ্বিতীয় ইনপুট। যদি x + z ≤ 3 হয়, তাহলে Pm-এ আর কোনও ইনপুট নেই, তাই w (x) = 8/3 এবং আমাদের কাজ শেষ। অন্যথায়, x + z <3। ধরা যাক কোনও লোভী বিন-এর মধ্যে v হল সবচেয়ে ছোট ইনপুট যার যোগফল 4-এর বেশি। যেহেতু x <8/3, তাই z অবশ্যই v এর আগে প্রসেস করা হয়েছে, তাই z ≤ v। এখন কিউজে-তে কোনও ছোট আইটেম টি বিবেচনা করুন এবং ধরুন এটি কোনও লোভী বিন পাই-তে রয়েছে। যদি যোগফল (পাই) <3 হয়, তাহলে যে ভি-কে পাই-তে রাখা হয়নি তা বোঝায় যে ভি> 4-যোগফল (বড়-আইটেম-ইন-পাই)> 1 + যোগফল (ছোট-আইটেম-ইন-পাই)। অতএব, 1 + যোগফল (সি) + x <v + x ≤ z + x <3 এবং যোগফল (সি) <2-x। এর অর্থ হল 2 * যোগফল (সি) <4-4x ≤ 4-x-y ≤ যোগফল (ছোট-আইটেম-ইন-কিউজে)। সুতরাং ডাব্লু (টি) = 2t/(3sum (সি))> 4t/(3sum (ছোট-আইটেম-ইন-কিউজে))। যদি যোগফল (পাই) 3, এবং যোগফল (সি) ≤ 1 হয়, তাহলে ডাব্লু (টি) = 4/3 এবং আমাদের কাজ শেষ। যেহেতু যোগফল (পাই) টি যোগ করার আগে 3 এর চেয়ে কম ছিল, তাই যোগফল (পাই) <3 + যোগফল (সি)/2। যে ভি-কে পাই-তে রাখা হয়নি তা বোঝায় যে ভি> 4-সমষ্টি (বড়-আইটেম-ইন-পাই)> 1 + সমষ্টি (ছোট-আইটেম-ইন-পাই)/2। পূর্ববর্তী অনুচ্ছেদের অনুরূপ, ডাব্লু (টি)> 4 টি/(3 সমষ্টি (ছোট-আইটেম-ইন-কিউজে))। অতএব, কিউজে-তে সমস্ত ছোট জিনিসের মোট ওজন কমপক্ষে 4/3, তাই কিউজে-এর মোট ওজন কমপক্ষে 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,., মি, মি। শেষ এম-1 ইনপুটগুলি সমস্ত মি। তারপর লোভী অ্যালগরিদম ফিরে আসেঃ 2 মি-1, মি, মি 2 মি-1, মি, মি 2 মি-2, মি + 1, মি 2 মি-2, মি + 1, মি। 3 মি/2,3 মি/2-1, মি 3 মি/2,2-2 সহ সর্বনিম্ন 3 মি-1। কিন্তু সর্বোত্তম বিভাজনটি হলঃ 2 মি-1,2 মি-2, মি, 2 মি-2, মি, 2 মি-3, মি + 1, মি 2 মি-3, মি + 1, মি. 3 মি/2,3 মি/2, মি 3 মি/2,3 মি/2, মি 3 মি/2, মি 3 মি/2, মি 3 মি/2, মি 3 মি/2, মি 3 মি/2, মি 3 মি/2, মি 3 মি/2, মি 3 মি/2, মি ন্যূনতম 4 মি-2 সহ। সীমাবদ্ধ এল. পি. টি এল. পি. টি-র একটি রূপ রয়েছে, যাকে সীমাবদ্ধ-এল. পি. টি বা আর. এল. পি. টি বলা হয়, যেখানে ইনপুটগুলি এম আকারের উপসেটে বিভক্ত করা হয় যাকে র্যাঙ্ক বলা হয় (র্যাঙ্ক 1-এ বৃহত্তম এম ইনপুট থাকে, র্যাঙ্ক 2-এ পরবর্তী বৃহত্তম এম ইনপুট ইত্যাদি থাকে)। প্রতিটি র্যাঙ্কের ইনপুটগুলি অবশ্যই বিভিন্ন বিনগুলিতে বরাদ্দ করতে হবেঃ প্রথমে র্যাঙ্ক 1, তারপর র্যাঙ্ক 2, ইত্যাদি। আর. এল. পি. টি-তে ন্যূনতম পরিমাণ হল এল. পি. টি-তে সর্বনিম্ন পরিমাণ। ন্যূনতম যোগফল সর্বাধিক করার জন্য আরএলপিটি-র আনুমানিক অনুপাত সর্বাধিক মি। গড়-ক্ষেত্রে সর্বাধিক যোগফল গড় ক্ষেত্রে, যদি ইনপুট সংখ্যাগুলি সমানভাবে [0,1]-তে বিতরণ করা হয়, তবে একটি এলপিটি সময়সূচিতে বৃহত্তম যোগফল নিম্নলিখিত বৈশিষ্ট্যগুলি সন্তুষ্ট করেঃ এম = 2 মেশিনের জন্য প্রত্যাশিত বৃহত্তম যোগফল কমপক্ষে এবং সর্বাধিক, যেখানে এন হল ইনপুটের সংখ্যা। সবচেয়ে বড় যোগফল বেশিরভাগ সময় প্রায় নিশ্চিতভাবে সর্বোত্তম হয় এবং প্রত্যাশার দিক থেকে, ইনপুটের সংখ্যা কোথায় থাকে। এল. পি. টি-র বৃহত্তম যোগফল এবং সর্বোত্তম বৃহত্তম যোগফলের মধ্যে পার্থক্য প্রায় নিশ্চিতভাবে (অভিন্ন বা ঋণাত্মক সূচকীয় বণ্টনের জন্য), এবং সর্বাধিক প্রত্যাশিত (অভিন্ন বণ্টনের জন্য)। এই ফলাফলগুলি বিভিন্ন গতির মেশিনের ক্ষেত্রেও প্রযোজ্য। সাধারণ উদ্দেশ্যগুলি ধরা যাক সি আই (1 এবং এম এর মধ্যে আই এর জন্য) একটি প্রদত্ত পার্টিশনে উপসেট আই এর যোগফল। অবজেক্টিভ ফাংশন ম্যাক্স (সি আই)-কে ন্যূনতম করার পরিবর্তে, অবজেক্টিভ ফাংশন ম্যাক্স (এফ (সি আই))-কে ন্যূনতম করা যেতে পারে, যেখানে এফ হল কোনও স্থির ফাংশন। একইভাবে, উদ্দেশ্যমূলক ফাংশনের যোগফলকে (f (Ci)) হ্রাস করা যেতে পারে। অ্যালন, আজার, ওয়েইজিঙ্গার এবং ইয়াদিদ প্রমাণ করেন যে, যদি f নিম্নলিখিত দুটি শর্ত পূরণ করেঃ শর্ত F * নামে একটি শক্তিশালী ধারাবাহিকতা শর্তঃ প্রতিটি ε> 0-এর জন্য δ> 0 এমনভাবে বিদ্যমান যে, যদি |y-x। <δx হয়, তাহলে |f (y)-f (x)। <εf (x)। কনভেক্সিটি। তারপর এল. পি. টি নিয়মের যোগফল (এফ (সি. আই)) হ্রাস করার জন্য একটি সীমাবদ্ধ আনুমানিক অনুপাত রয়েছে। অন্যান্য সেটিংসে অভিযোজন অভিন্ন-মেশিনের সময়সূচীর সহজ কেস ছাড়াও, এলপিটি আরও সাধারণ সেটিংসে অভিযোজিত হয়েছে। ইউনিফর্ম মেশিন ইউনিফর্ম-মেশিনের সময়সূচীতে, বিভিন্ন মেশিনের বিভিন্ন গতি থাকতে পারে। এল. পি. টি নিয়মটি প্রতিটি কাজ যন্ত্রকে বরাদ্দ করে যার উপর তার সমাপ্তির সময় শীঘ্রই হবে (অর্থাৎ, এল. পি. টি একটি বৃহত্তর তড়িৎ প্রবাহ সহ একটি যন্ত্রকে একটি কাজ বরাদ্দ করতে পারে, যদি এই যন্ত্রটি এত দ্রুত হয় যে এটি সেই কাজটি অন্য সমস্ত যন্ত্রের চেয়ে আগে শেষ করতে পারে)। গনজালেজ, ইবারা এবং সাহনি দেখান যে এম ইউনিফর্ম মেশিনের সাথে এল. পি. টি-র আনুমানিক অনুপাত সর্বাধিক। এটি আঁটসাঁট নয়, তবে 1.5-এর একটি অ্যাসিম্পটোটিক নিম্ন সীমা থাকে যখন m অসীমের কাছাকাছি পৌঁছায়। এম = 2 মেশিনের বিশেষ ক্ষেত্রে, আনুমানিক অনুপাত সর্বাধিক এবং এটি আঁটসাঁট। মাইরোল্ট, অরলিন এবং ভোহরা দুটি মেশিনের সাথে একটি সেটিং অধ্যয়ন করে, যেখানে একটি মেশিন অন্যটির চেয়ে q গুণ দ্রুত। তারা এল. পি. টি-র আনুমানিক অনুপাতকে q-এর একটি ফাংশন হিসাবে গণনা করে। যখন q = 1 হয়, তখন তাদের ফলাফল অভিন্ন যন্ত্রের জন্য পরিচিত 7/6 ফ্যাক্টরের সাথে মিলে যায়। কৌলামাস এবং কিপারিসিস এল. পি. টি-র একটি পরিবর্তন উপস্থাপন করেছেন যেখানে তিনটি দীর্ঘতম কাজ সর্বোত্তমভাবে নির্ধারিত হয় এবং বাকি কাজগুলি এল. পি. টি নিয়মের ভিত্তিতে নির্ধারিত হয়। দুটি মেশিনের আনুমানিক অনুপাত হল এবং এটি শক্ত। কার্ডিনালিটির সীমাবদ্ধতা ভারসাম্যপূর্ণ বিভাজনের সমস্যায়, প্রতিটি যন্ত্রে বরাদ্দ করা যেতে পারে এমন কাজের সংখ্যার উপর সীমাবদ্ধতা রয়েছে। একটি সহজ সীমাবদ্ধতা হল যে প্রতিটি যন্ত্র সর্বাধিক সি কাজগুলি প্রক্রিয়া করতে পারে। এল. পি. টি-র নিয়ম অনুযায়ী প্রতিটি কাজ সি-এর চেয়ে কম কাজের লোকদের মধ্যে থেকে সবচেয়ে কম লোড সহ মেশিনে বরাদ্দ করা হয়। এই নিয়মটিকে পরিবর্তিত এলপিটি বা এমএলপিটি বলা হয়। কেলারার এবং ওয়েইঞ্জার একটি বৈকল্পিক অধ্যয়ন করেন যেখানে সর্বাধিক 3 * মি কাজ রয়েছে এবং প্রতিটি মেশিনে সর্বাধিক 3 টি কাজ থাকতে হবে (এটি 3-পার্টিশন সমস্যার সাধারণীকরণ হিসাবে দেখা যেতে পারে)। তারা দেখায় যে, এম. এল. পি. টি সর্বাধিক ন্যূনতম বৃহত্তম অঙ্ক অর্জন করে, যা এল. পি. টি অনিয়ন্ত্রিত সমস্যার জন্য একই আনুমানিক অনুপাত অর্জন করে। এম. এল. পি. টি-র জন্য সীমাটি শক্ত। এটি অনুমান করা হয় যে আরও সাধারণ কার্ডিনালিটি সীমাবদ্ধতার (সি> 3) জন্য এম. এল. পি. টি-র একই আনুমানিক অনুপাত রয়েছে। বর্তমানে জানা যায় যে সাধারণ সি> 3-এর জন্য এম. এল. পি. টি-র আনুমানিক অনুপাত সর্বাধিক 2। চেন, হি এবং লিন দেখান যে, একই সমস্যার জন্য, এম. এল. পি. টি কমপক্ষে সর্বোচ্চ ক্ষুদ্রতম যোগফল অর্জন করে, যা আবার একই অনুপাত যা এল. পি. টি অনিয়ন্ত্রিত সমস্যার জন্য অর্জন করে। আরেকটি বাধা হল যে সমস্ত মেশিনে কাজের সংখ্যা উপরে বা নিচে বৃত্তাকার করা উচিত। সীমাবদ্ধ এল. পি. টি বা আর. এল. পি. টি নামে এল. পি. টি-র একটি অভিযোজনে, ইনপুটগুলি জোড়ায় বরাদ্দ করা হয়-প্রতিটি মেশিনে একটি করে (এম = 2 মেশিনের জন্য)। ফলস্বরূপ বিভাজনটি নকশা দ্বারা ভারসাম্যপূর্ণ। কফম্যান, ফ্রেডেরিকসন এবং লুয়েকার দেখান যে আরএলপিটি-র প্রত্যাশিত বৃহত্তম যোগফল যখন ইনপুটগুলি অভিন্নভাবে বিতরণ করা হয়। বৃহত্তম এবং ক্ষুদ্রতম যোগফলের মধ্যে প্রত্যাশিত পার্থক্য হল। কার্নেল সীমাবদ্ধতা-অ-একযোগে প্রাপ্যতা কার্নেল পার্টিশনিং সমস্যায়, কার্নেল নামে কিছু এম পূর্ব-নির্দিষ্ট কাজ রয়েছে এবং প্রতিটি কার্নেলকে অবশ্যই একটি অনন্য মেশিনে নির্ধারিত করতে হবে। একটি সমতুল্য সমস্যা হল সময়সূচী নির্ধারণ করা যখন যন্ত্রগুলি বিভিন্ন সময়ে উপলব্ধ থাকেঃ প্রতিটি যন্ত্র i কিছু সময়ে উপলব্ধ হয় (সময় ti কে কার্নেল কাজের দৈর্ঘ্য হিসাবে বিবেচনা করা যেতে পারে)। একটি সাধারণ হিউরিস্টিক অ্যালগরিদম, যাকে এসএলপিটি বলা হয়, প্রতিটি কার্নেলকে একটি ভিন্ন উপসেটে বরাদ্দ করে এবং তারপর এলপিটি অ্যালগরিদম চালায়। লি প্রমাণ করেছেন যে এই অনুসন্ধানের সর্বনিম্ন বৃহত্তম যোগফলের জন্য একটি আঁটসাঁট আনুমানিক অনুপাত রয়েছে। তারপরে তিনি দ্বিতীয় ধাপে এল. পি. টি-র একটি পরিবর্তিত সংস্করণ চালানোর পরামর্শ দেন এবং প্রমাণ করেন যে এটি একটি আনুমানিক অনুপাত অর্জন করে। লিন, ইয়াও এবং তিনি প্রমাণ করেছেন যে এই অনুসন্ধানমূলক সর্বাধিক ক্ষুদ্রতম যোগফলের জন্য একটি শক্ত আনুমানিক অনুপাত রয়েছে। শেন, ওয়াং এবং ওয়াং এই সেটিং-এর জন্য বিভিন্ন উদ্দেশ্যমূলক ফাংশন অধ্যয়ন করেন এবং পলিনোমিয়াল-টাইম অ্যালগরিদম উপস্থাপন করেন। অনলাইন সেটিংস প্রায়শই, ইনপুটগুলি অনলাইনে আসে এবং তাদের আকার তখনই জানা যায় যখন তারা আসে। এই ক্ষেত্রে, এগুলি আগে থেকে সাজানো সম্ভব নয়। তালিকা নির্ধারণ একটি অনুরূপ অ্যালগরিদম যা কোনও ক্রমে একটি তালিকা নেয়, অগত্যা সাজানো হয় না। এর আনুমানিক অনুপাত হল। একটি অনলাইন সেটিং-এ এল. পি. টি-র আরও পরিশীলিত অভিযোজন আনুমানিক 3/2 অনুপাত অর্জন করে। বাস্তবায়ন পাইথনঃ নম্বর পার্টিশনিং প্যাকেজের পাশাপাশি পিআরটিপি প্যাকেজেও এলপিটি ("লোভী") প্রয়োগ করা হয়। আরও দেখুন লোভী সংখ্যা বিভাজন-মাল্টিওয়ে নম্বর বিভাজনের সমস্যার জন্য এল. পি. টি-র সাধারণীকরণ এবং সম্প্রসারণ। নোট রেফারেন্স সময়সূচী অ্যালগরিদম সংখ্যা বিভাজন