Longest-processing-time-first scheduling
لانگسٹ پروسیسنگ ٹائم فرسٹ (ایل پی ٹی) نوکری کے شیڈولنگ کے لیے ایک لالچی الگورتھم ہے۔ الگورتھم میں ان پٹ ملازمتوں کا ایک مجموعہ ہے، جن میں سے ہر ایک کا ایک مخصوص پروسیسنگ ٹائم ہوتا ہے۔ ایک نمبر m بھی ہے جو ان مشینوں کی تعداد کی وضاحت کرتا ہے جو ملازمتوں پر کارروائی کر سکتی ہیں۔ ایل پی ٹی الگورتھم مندرجہ ذیل کام کرتا ہے: نوکریوں کو ان کے پروسیسنگ ٹائم کے نزولی ترتیب سے آرڈر کریں، جیسے کہ سب سے طویل پروسیسنگ ٹائم والا کام پہلا ہو۔ اس ترتیب میں ہر کام کو ایک ایسی مشین میں شیڈول کریں جس میں موجودہ بوجھ (= شیڈول شدہ کاموں کی کل پروسیسنگ کا وقت) سب سے چھوٹا ہو۔ الگورتھم کا مرحلہ 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 یکساں ہے): پھر لالچی الگورتھم واپس آتا ہے:,. زیادہ سے زیادہ کے ساتھ، لیکن زیادہ سے زیادہ پارٹیشن ہے:. زیادہ سے زیادہ کے ساتھ۔ ان پٹ پر غور ایک اور بھی تفصیلی تجزیہ زیادہ سے زیادہ رقم والے حصے میں ان پٹ کی تعداد کو مدنظر رکھتا ہے۔ لالچی تقسیم کے ہر حصے میں، جے-تھ سب سے زیادہ نمبر زیادہ سے زیادہ ہوتا ہے۔ فرض کریں کہ لالچی حصہ P میں زیادہ سے زیادہ رقم کے ساتھ، L ان پٹ ہیں۔ پھر، لالچی الگورتھم کا تخمینہ تناسب ہے۔ یہ L ≤ 3 کے لیے تنگ ہے (L = 3 کے لیے، ہمیں عمومی عنصر ملتا ہے)۔ ثبوت۔ P میں اعداد کو x1،.، xL سے ظاہر کریں۔ XL کو P میں داخل کرنے سے پہلے، اس کا مجموعہ سب سے چھوٹا تھا۔ لہذا، فی حصہ اوسط رقم کم از کم رقم x1 +. + xL-1 + xL/m ہے۔ بہترین زیادہ سے زیادہ رقم کم از کم اوسط رقم ہونی چاہیے۔ اس کے برعکس لالچی رقم x1 +. + xL-1 + xL ہے۔ لہذا فرق زیادہ سے زیادہ (1-1/m) xL ہے، جو (1) سے زیادہ سے زیادہ (1-1/m) * OPT/L ہے۔ تو تناسب زیادہ سے زیادہ (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 ان پٹ میں سے کچھ دو ان پٹ شامل ہوں ؛ لہذا پائی پر کیو جے کا غلبہ ہے۔ لالچی الگورتھم کے چلنے کے دوران، ہر بن پائی میں رقم کم از کم 8/3 ہو جاتی ہے اس سے پہلے کہ کسی بھی بن کا مجموعہ 4 سے تجاوز کر جائے۔ ثبوت: فرض کریں کہ y کسی بن پائی میں شامل کیا گیا پہلا ان پٹ ہے، جس نے اس کی رقم کو 4 سے بڑا بنا دیا۔ y کے شامل ہونے سے پہلے، پائی کا سب سے چھوٹا مجموعہ تھا، جو فرض کے مطابق 8/3 سے چھوٹا تھا ؛ اس کا مطلب ہے کہ y> 4/3۔ آئیے T پہلے سے نیچے y تک تمام ان پٹ کے سیٹ کو ظاہر کرتا ہے۔ یہ تمام ان پٹ 4/3 سے بھی بڑے ہیں۔ چونکہ پائی 8/3 سے چھوٹا تھا، اس میں ٹی سے بالکل ایک آئٹم x موجود تھا۔ لہذا اب پائی بالکل 2 آئٹمز {x, y} پر مشتمل ہے، اور الگورتھم ختم ہونے تک ان 2 آئٹمز کے ساتھ رہتا ہے۔ فرض کریں کہ m پہلے سے نیچے x تک آئٹمز کی تعداد ہے۔ اب ہم T میں آئٹمز کو دو طریقوں سے گن کر ایک تضاد ظاہر کرتے ہیں۔ سب سے پہلے، بہترین ڈبوں پر غور کریں۔ اگر اس طرح کے کسی ڈبے میں کم از کم x جتنی بڑی چیز ہو، تو اس میں T کی کوئی دوسری چیز نہیں ہو سکتی، کیونکہ بصورت دیگر یہ {x, y} پر حاوی ہے۔ مزید برآں، اس طرح کے کسی بھی ڈبے میں T سے تین آئٹمز نہیں ہو سکتے، کیونکہ ان میں سے کسی بھی دو کا مجموعہ 8/3 سے بڑا ہے، جو x سے بڑا ہے ؛ اور تیسرا کم از کم y ہے، لہذا یہ {x, y} پر حاوی ہے۔ لہذا، T میں اشیاء کی تعداد زیادہ سے زیادہ 1 * m + 2 * (n-m) = 2n-m ہے۔ اب، لالچی ڈبوں پر غور کریں۔ جب x پر مشتمل بنڈل میں y شامل کیا جاتا ہے، تو یہ سب سے چھوٹی رقم والا بنڈل ہوتا ہے۔ لہذا، T کے تمام عناصر جو x سے چھوٹے ہیں، کم از کم T کی ایک دوسری شے کے ساتھ لالچی ڈبے میں ہونے چاہئیں۔ یہی بات x اور y کے لیے بھی درست ہے۔ لہذا، 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 پر پہنچتا ہے۔ ایک بار جب الگورتھم کسی بن پی جے میں ایکس کا اضافہ کرتا ہے، تو پی جے کا مجموعہ کم از کم 8/3+1 3 = 3 ہو جاتا ہے، لہذا پی جے میں مزید آئٹمز شامل نہیں کیے جاتے ہیں۔ لہذا پی جے میں [1/3,1) میں سائز کے ساتھ صرف ایک ان پٹ ہوتا ہے۔ ایک بار جب x کو 1 سے تبدیل کر دیا جاتا ہے، تب بھی اسے Pj میں داخل کیا جاتا ہے، اور اس کا مجموعہ اب بھی 3 سے اوپر ہوتا ہے۔ اس لیے لالچی کم رقم تبدیل نہیں ہوتی۔ اب ہم ان پٹ کو چھوٹے (1/3 سے کم) اور بڑے (کم از کم 1) میں تقسیم کر سکتے ہیں۔ پائی میں چھوٹی آئٹمز کے سیٹ کو سی سے ظاہر کیا جاتا ہے۔ نوٹ کریں کہ، جب الگورتھم چھوٹی آئٹمز پر کارروائی کرنا شروع کرتا ہے، تو تمام بنڈلوں میں رقم کم از کم 8/3 ہوتی ہے۔ اس بات کا ثبوت کہ کم سے کم جوابی مثال موجود نہیں ہے، ویٹنگ اسکیم کا استعمال کرتا ہے۔ ہر ان پٹ x کو اس کے سائز اور لالچی بنڈل کے مطابق وزن ڈبلیو (ایکس) تفویض کیا جاتا ہے۔ پائی: اگر ایکس ایک بڑی آئٹم ہے: اگر ایکس پائی میں واحد بڑی آئٹم ہے، تو ڈبلیو (ایکس) = 8/3۔ اگر پائی بالکل دو آئٹمز {x, y} پر مشتمل ہے اور وہ دونوں بڑے ہیں، اور x> y، اور مجموعہ (Pi) ≤ 3، تو w (x) = 8/3۔ ورنہ، ڈبلیو (ایکس) = 4/3۔ اگر x ایک چھوٹی آئٹم ہے: اگر مجموعہ (Pi) 3، تو w (x) = 4x/(3 مجموعہ (Si)) ؛ تو w (Si) = 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 چھوٹا ہے۔ فرض کریں کہ یہ پائی میں ہے۔ اگر sum (Pi) ≤ 3 تو، چونکہ sum (Pi) اس میں x شامل کرنے سے پہلے 3 سے چھوٹا تھا، اب یہ 10/3 سے چھوٹا ہے۔ لیکن جب الگورتھم نے چھوٹی آئٹمز پر کارروائی شروع کی تو sum (Pi) کم از کم 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 ہے۔ ثبوت: اگر کیو جے میں صرف چھوٹی اشیاء ہیں، تو ان میں سے ہر ایک ڈبلیو (ایکس)> 2 ایکس کو مطمئن کرتا ہے، لہذا ڈبلیو (کیو جے)> 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۔ تو ایکس کسی لالچی بن پی ایم میں پہلا ان پٹ تھا۔ فرض کریں کہ 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 + sum (Si) + x <v + x ≤ z + x <3 اور sum (Si) <2-x۔ اس کا مطلب یہ ہے کہ 2 * sum (Si) <4-4x ≤ 4-x-y ≤ sum (چھوٹے آئٹمز-ان-Qj)۔ تو w (t) = 2t/(3sum (Si))> 4t/(3sum (چھوٹے آئٹمز-ان-Qj))۔ اگر مجموعہ (پائی) ≤ 3، اور مجموعہ (سی) ≤ 1، تو ڈبلیو (ٹی) = 4/3 اور ہم کر چکے ہیں۔ چونکہ اس میں t کو شامل کرنے سے پہلے sum (Pi) 3 سے کم تھا، اس لیے sum (Pi) <3 + sum (Si)/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 یکساں ہے)۔ پہلے 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, m 3m/2, m 3m/2,3m/2-1 کم از کم 3m-1 کے ساتھ۔ لیکن زیادہ سے زیادہ تقسیم یہ ہے: 2m-1,2m-1 2m-2, m, m 2m-2, m, 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-1,3m/2-1, m کم از کم 4m-2 کے ساتھ۔ محدود ایل پی ٹی ایل پی ٹی کی ایک قسم ہے، جسے محدود-ایل پی ٹی یا آر ایل پی ٹی کہا جاتا ہے، جس میں ان پٹ کو سائز ایم کے ذیلی سیٹوں میں تقسیم کیا جاتا ہے جسے رینک کہا جاتا ہے (رینک 1 میں سب سے بڑا ایم ان پٹ ہوتا ہے، رینک 2 اگلے سب سے بڑے ایم ان پٹ وغیرہ)۔ ہر رینک میں ان پٹ m مختلف ڈبوں کو تفویض کیے جانے چاہئیں: پہلے رینک 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)۔ کنویکسٹی۔ پھر ایل پی ٹی اصول میں رقم (f (Ci)) کو کم سے کم کرنے کے لیے ایک محدود تخمینہ تناسب ہوتا ہے۔ دیگر ترتیبات میں موافقت یکساں مشینوں کے شیڈولنگ کے سادہ معاملے کے علاوہ، ایل پی ٹی کو زیادہ عام ترتیبات میں ڈھال لیا گیا ہے۔ یکساں مشینیں یکساں مشینوں کے شیڈولنگ میں، مختلف مشینوں کی رفتار مختلف ہو سکتی ہے۔ ایل پی ٹی کا قاعدہ ہر کام مشین کو تفویض کرتا ہے جس پر اس کی تکمیل کا وقت جلد ہوگا (یعنی، ایل پی ٹی زیادہ موجودہ بوجھ والی مشین کو کام تفویض کر سکتا ہے، اگر یہ مشین اتنی تیز ہے کہ وہ اس کام کو دوسری تمام مشینوں سے پہلے ختم کر دے گی)۔ گونزالیز، ابررا اور ساہنی ظاہر کرتے ہیں کہ ایم وردی مشینوں کے ساتھ ایل پی ٹی کا تخمینہ تناسب زیادہ سے زیادہ ہے۔ یہ تنگ نہیں ہے، لیکن جب m لامحدود کے قریب پہنچتا ہے تو 1.5 کی ایک غیر علامتی نچلی حد ہوتی ہے۔ m = 2 مشینوں کے خاص معاملے کے لیے، تخمینہ تناسب زیادہ سے زیادہ ہوتا ہے اور یہ سخت ہوتا ہے۔ میرالٹ، اورلن اور ووہرا دو مشینوں کے ساتھ ایک ترتیب کا مطالعہ کرتے ہیں، جس میں ایک مشین دوسرے سے ق گنا تیز ہوتی ہے۔ وہ ایل پی ٹی کے تخمینہ تناسب کو q کے فعل کے طور پر شمار کرتے ہیں۔ جب q = 1 ہوتا ہے، تو ان کا نتیجہ 7/6 عنصر کے ساتھ موافق ہوتا ہے جو ایک جیسی مشینوں کے لیے جانا جاتا ہے۔ کولاماس اور کیپیریسس ایل پی ٹی کی ایک ترمیم پیش کرتے ہیں جس میں تین طویل ترین ملازمتیں بہتر طور پر شیڈول کی جاتی ہیں، اور باقی ملازمتیں ایل پی ٹی کے اصول کی بنیاد پر شیڈول کی جاتی ہیں۔ دو مشینوں کے لیے تخمینہ تناسب ہے اور یہ تنگ ہے۔ کارڈینیلیٹی کی رکاوٹیں متوازن تقسیم کے مسئلے میں، ان ملازمتوں کی تعداد پر رکاوٹیں ہیں جو ہر مشین کو تفویض کی جا سکتی ہیں۔ ایک سادہ سی رکاوٹ یہ ہے کہ ہر مشین زیادہ سے زیادہ سی جابز پر کارروائی کر سکتی ہے۔ ایل پی ٹی کا قاعدہ ہر کام کو مشین کو تفویض کرتا ہے جس میں سی سے کم ملازمتوں والے لوگوں میں سے سب سے چھوٹا بوجھ ہوتا ہے۔ اس اصول کو ترمیم شدہ ایل پی ٹی یا ایم ایل پی ٹی کہا جاتا ہے۔ کیلر اور ووینجر ایک ایسی قسم کا مطالعہ کرتے ہیں جس میں زیادہ سے زیادہ 3 * m نوکریاں ہوتی ہیں، اور ہر مشین میں زیادہ سے زیادہ 3 نوکریاں ہونی چاہئیں (اسے 3-پارٹیشن کے مسئلے کی عمومی شکل کے طور پر دیکھا جا سکتا ہے)۔ وہ ظاہر کرتے ہیں کہ ایم ایل پی ٹی زیادہ تر کم از کم سب سے بڑی رقم حاصل کرتا ہے، جو کہ ایل پی ٹی غیر محدود مسئلے کے لیے حاصل کرتا ہے۔ ایم ایل پی ٹی کے لیے باؤنڈ سخت ہے۔ یہ قیاس کیا جاتا ہے کہ ایم ایل پی ٹی میں زیادہ عام کارڈینالیٹی رکاوٹوں (سی> 3) کے لیے ایک ہی تخمینہ تناسب ہے۔ فی الحال، یہ معلوم ہے کہ عام سی> 3 کے لیے ایم ایل پی ٹی کا تخمینہ تناسب زیادہ سے زیادہ 2 ہے۔ چن، ہی اور لن دکھاتے ہیں کہ، اسی مسئلے کے لیے، ایم ایل پی ٹی کم از کم سب سے چھوٹی رقم حاصل کرتا ہے، جو دوبارہ وہی تناسب ہے جو ایل پی ٹی غیر محدود مسئلے کے لیے حاصل کرتا ہے۔ ایک اور رکاوٹ یہ ہے کہ تمام مشینوں پر ملازمتوں کی تعداد کو اوپر یا نیچے ہونا چاہیے۔ ایل پی ٹی کی موافقت میں جسے محدود ایل پی ٹی یا آر ایل پی ٹی کہا جاتا ہے، ان پٹ جوڑوں میں تفویض کیے جاتے ہیں-ہر مشین کے لیے ایک (ایم = 2 مشینوں کے لیے)۔ نتیجے میں تقسیم ڈیزائن کی طرف سے متوازن ہے. کوفمین، فریڈرکسن اور لیوکر ظاہر کرتے ہیں کہ جب ان پٹ یکساں طور پر تقسیم شدہ بے ترتیب متغیر ہوتے ہیں تو آر ایل پی ٹی کی متوقع سب سے بڑی رقم بالکل درست ہوتی ہے۔ سب سے بڑی اور سب سے چھوٹی رقم کے درمیان متوقع فرق ہے۔ دانا کی رکاوٹیں-غیر بیک وقت دستیابی دانا کی تقسیم کے مسئلے میں، کچھ m پہلے سے طے شدہ کام ہوتے ہیں جنہیں دانا کہا جاتا ہے، اور ہر دانا کو ایک منفرد مشین پر شیڈول کیا جانا چاہیے۔ ایک مساوی مسئلہ شیڈولنگ ہے جب مشینیں مختلف اوقات میں دستیاب ہوتی ہیں: ہر مشین i کسی وقت ti ≤ 0 پر دستیاب ہو جاتی ہے (وقت ti کو دانا کے کام کی لمبائی سمجھا جا سکتا ہے)۔ ایک سادہ ہیورسٹک الگورتھم، جسے ایس ایل پی ٹی کہا جاتا ہے، ہر دانے کو ایک مختلف ذیلی سیٹ پر تفویض کرتا ہے، اور پھر ایل پی ٹی الگورتھم چلاتا ہے۔ لی ثابت کرتا ہے کہ اس تحقیق میں کم از کم سب سے بڑی رقم کے لیے ایک سخت تخمینہ تناسب ہے۔ اس کے بعد وہ دوسرے مرحلے میں ایل پی ٹی کا ایک ترمیم شدہ ورژن چلانے کا مشورہ دیتا ہے، اور ثابت کرتا ہے کہ یہ ایک تخمینہ تناسب حاصل کرتا ہے۔ لن، یاؤ اور وہ ثابت کرتے ہیں کہ اس تحقیق میں زیادہ سے زیادہ سب سے چھوٹی رقم کے لیے ایک تنگ تخمینہ تناسب ہے۔ شین، وانگ اور وانگ اس ترتیب کے لیے مختلف معروضی افعال کا مطالعہ کرتے ہیں، اور کثیر الجہتی وقت کے الگورتھم پیش کرتے ہیں۔ آن لائن ترتیبات اکثر، ان پٹ آن لائن آتے ہیں، اور ان کے سائز تب ہی معلوم ہوتے ہیں جب وہ پہنچتے ہیں۔ اس صورت میں انہیں پہلے سے ترتیب دینا ممکن نہیں ہے۔ لسٹ شیڈولنگ ایک ایسا ہی الگورتھم ہے جو کسی بھی ترتیب میں فہرست لیتا ہے، ضروری نہیں کہ اسے ترتیب دیا جائے۔ اس کا تخمینہ تناسب ہے۔ آن لائن ترتیب میں ایل پی ٹی کی ایک زیادہ نفیس موافقت 3/2 کا تخمینہ تناسب حاصل کرتی ہے۔ نفاذ ازگر: نمبر پارٹیشننگ پیکیج کے ساتھ ساتھ پی آر ٹی پی پیکیج میں بھی ایل پی ٹی ("لالچی") کا نفاذ ہوتا ہے۔ گریڈی نمبر پارٹیشننگ-ملٹی وے نمبر پارٹیشننگ کے مسئلے کے لیے ایل پی ٹی کی عمومی اور توسیعات بھی دیکھیں۔ نوٹ حوالہ جات شیڈولنگ الگورتھم نمبر پارٹیشننگ