Talent scheduling
ٹیلنٹ شیڈولنگ کمپیوٹر سائنس اور آپریشنز ریسرچ میں اصلاح کا ایک مسئلہ ہے، اور یہ مشترکہ اصلاح میں بھی ایک مسئلہ ہے۔ فرض کریں کہ ہمیں فلمیں بنانے کی ضرورت ہے، اور ہر فلم میں کئی مناظر ہوتے ہیں۔ ہر منظر کو ایک یا زیادہ اداکاروں کے ذریعے شوٹ کرنے کی ضرورت ہوتی ہے۔ اور فرض کریں کہ آپ دن میں صرف ایک سین شوٹ کر سکتے ہیں۔ ان اداکاروں کی تنخواہوں کا حساب دن کے حساب سے لگایا جاتا ہے۔ اس مسئلے میں، ہم صرف ہر اداکار کو لگاتار ملازمت پر رکھ سکتے ہیں۔ مثال کے طور پر، ہم پہلے اور تیسرے دن کسی اداکار کی خدمات حاصل نہیں کر سکتے، لیکن دوسرے دن نہیں کر سکتے۔ نوکری کی مدت کے دوران، پروڈیوسروں کو پھر بھی اداکاروں کو ادائیگی کرنے کی ضرورت ہوتی ہے چاہے وہ فلم بندی کی تفویض میں شامل نہ ہوں۔ ٹیلنٹ شیڈولنگ کا مقصد مناظر کی ترتیب کو ایڈجسٹ کرکے اداکاروں کی کل تنخواہ کو کم کرنا ہے۔ ریاضیاتی تشکیل شوٹنگ کے دنوں پر مشتمل اور کل اداکاروں پر مشتمل فلم کی شوٹنگ پر غور کریں۔ پھر ہم شوٹنگ کے مختلف دنوں کی ضروریات کی نمائندگی کرنے کے لیے ڈے آؤٹ آف ڈےز میٹرکس (ڈی او ڈی ایم) کا استعمال کرتے ہیں۔ اندراج کے ساتھ میٹرکس: پھر ہم پے ویکٹر کی وضاحت کرتے ہیں، جس میں th عنصر دیا گیا ہے جس کا مطلب ہے th اداکار کی فی دن تنخواہ کی شرح۔ آئیے v، n کالموں کے کسی بھی ترتیب کو ظاہر کرتا ہے، ہمارے پاس: n شوٹنگ کے دنوں کا ترتیب سیٹ ہے۔ پھر میٹرکس ہونے کی وضاحت کریں جس کے کالموں کو اس کے مطابق ترتیب دیا گیا ہے، ہمارے پاس ہے: اس کے بعد ہم استعمال کرتے ہیں اور نمائندگی کرنے کے لیے شیڈول میں بالترتیب ابتدائی اور تازہ ترین دنوں کی نشاندہی کرتے ہیں جس کا تعین ایکٹر کے ذریعے کیا جاتا ہے۔ لہذا ہم تلاش کر سکتے ہیں کہ اداکار کو کئی دنوں کے لیے رکھا جائے گا۔ لیکن ان دنوں میں، دراصل صرف دنوں کی ضرورت ہوتی ہے، جس کا مطلب ہے کہ دن غیر ضروری ہیں، ہمارے پاس: غیر ضروری دنوں کی کل لاگت یہ ہے: وہی معروضی فنکشن ہوگا جسے ہمیں کم کرنا چاہیے۔ مضبوط این پی سختی کا ثبوت ٹیلنٹ شیڈولنگ کے مسئلے میں، ہم یہ ثابت کر سکتے ہیں کہ زیادہ سے زیادہ لکیری ترتیب (او ایل اے) کے مسئلے سے کمی کرکے این پی سخت ہے۔ اور اس مسئلے میں، یہاں تک کہ ہم ہر اداکار کو صرف دو دن کے لیے محدود کرتے ہیں اور تمام اداکاروں کی تنخواہ 1 ہے، یہ اب بھی او ایل اے کے مسئلے کے لیے کثیر الجہتی طور پر کم ہے۔ اس طرح، اس مسئلے میں فرضی کثیر الجہتی الگورتھم ہونے کا امکان نہیں ہے۔ انٹیجر پروگرامنگ انٹیجر پروگرامنگ ماڈل اس طرح دیا گیا ہے: اس ماڈل میں، ٹیلنٹ کے لیے ابتدائی شوٹنگ کا دن، ٹیلنٹ کے لیے تازہ ترین شوٹنگ کا دن، پروجیکٹ کا شیڈولنگ ہے، یعنی۔ حوالہ جات کا بہترین شیڈولنگ