Heterogeneous earliest finish time
متفرق ابتدائی اختتامی وقت (یا ایچ ای ایف ٹی) مواصلات کے وقت کو مدنظر رکھتے ہوئے متفرق کارکنوں کے نیٹ ورک پر منحصر کاموں کے ایک سیٹ کو شیڈول کرنے کے لیے ایک تحقیق ہے۔ ان پٹ کے لیے ایچ ای ایف ٹی کاموں کا ایک مجموعہ لیتا ہے، جسے ایک ڈائریکٹڈ ایسائکلک گراف کے طور پر پیش کیا جاتا ہے، کارکنوں کا ایک مجموعہ، ہر کارکن پر ہر کام کو انجام دینے کا وقت، اور ہر کام کے نتائج کو اس کے ہر بچے تک پہنچانے کا وقت۔ یہ لسٹ شیڈولنگ الگورتھم سے اترتا ہے۔ الگورتھم HEFT دو مراحل میں انجام دیتا ہے۔ کاموں کو ترجیح دینا پہلے مرحلے میں ہر کام کو ترجیح دی جاتی ہے۔ ہر کام کی ترجیح کو عام طور پر اس کی "اوپر کی درجہ بندی" کے طور پر نامزد کیا جاتا ہے جس کی تعریف بار بار اس طرح کی جاتی ہے جہاں کام کی نمائندگی ہوتی ہے، تمام پروسیسر کے درمیان کام کی اوسط کمپیوٹیشن لاگت ہے، تمام ملازمتوں کا مجموعہ ہے جو فوری طور پر کام پر منحصر ہوتا ہے، اور ملازمتوں کے درمیان اور کارکنوں کے تمام جوڑوں کے درمیان منتقل ہونے والے متغیرات کی اوسط مواصلاتی لاگت ہے۔ نوٹ کریں کہ کی گنتی اس کے تمام بچوں کے درجے کی گنتی پر منحصر ہے۔ اوپر کی درجہ بندی کا مطلب حساب کے اختتام سے کسی بھی کام کے متوقع فاصلے کی نمائندگی کرنا ہے۔ اوسط مقداروں کے لیے جیسے کہ مختلف اوسط مختلف نتائج فراہم کر سکتی ہیں۔ کارکنوں کو کام تفویض کرنا دوسرے مرحلے میں کام کارکنوں کو تفویض کیے جاتے ہیں۔ اب جب کہ تمام کاموں کو ترجیح دی جاتی ہے ہم سب سے زیادہ ترجیح کے ساتھ شروع کرتے ہوئے ہر ایک پر غور کرتے ہیں اور شیڈول کرتے ہیں۔ سب سے زیادہ ترجیح والا کام جس کے لیے تمام منحصر کام مکمل ہو چکے ہیں، کارکن پر شیڈول کیا جاتا ہے جس کے نتیجے میں اس کام کو جلد سے جلد مکمل کیا جائے گا۔ یہ ختم ہونے کا وقت کارکن کو تمام ضروری ان پٹ بھیجنے کے لیے مواصلات کے وقت، کارکن پر کام کے حساب کتاب کے وقت، اور اس وقت پر منحصر ہے جب وہ پروسیسر دستیاب ہو جاتا ہے (یہ کسی دوسرے کام میں مصروف ہو سکتا ہے)۔ ایچ ای ایف ٹی ایک اندراج پر مبنی پالیسی کا استعمال کرتا ہے جو پہلے سے طے شدہ کاموں کے درمیان کافی سائز کے خلا کو پر کرتا ہے۔ اس مسئلے کے لیے ہیورسٹک الگورتھم میں ڈسکشن ایچ ای ایف ٹی کا بہت احترام کیا جاتا ہے۔ لیکن پیچیدہ حالات میں یہ آسانی سے بہترین شیڈولنگ تلاش کرنے میں ناکام ہو سکتا ہے۔ ایچ ای ایف ٹی بنیادی طور پر ایک لالچی الگورتھم ہے اور طویل مدتی فوائد کے لیے قلیل مدتی قربانیاں دینے سے قاصر ہے۔ شیڈولنگ کے فیصلے کے معیار کا بہتر اندازہ لگانے کے لیے ایچ ای ایف ٹی پر مبنی کچھ بہتر الگورتھم کو شیڈولنگ کی کارکردگی کے لیے رن ٹائم کی تجارت کے لیے استعمال کیا جا سکتا ہے۔ کوڈ ایچ ای ایف ٹی کا ازگر کا نفاذ گتھب پر دستیاب ہے اے سی + + ایچ ای ایف ٹی کا نفاذ گتھب حوالہ جات شیڈولنگ الگورتھم پر دستیاب ہے۔