کمینه سازی مجموع زمان ها تکمیل در زمان بندی کارهای تقسیم پذیر

در این تحقیق مسئله زمانبندی کمینه سازی مجموع زمان ها تکمیل در زمان بندی ماشین های موازی با زمانه ا آماده سازی وکارهای تقسیم پذیر مورد بررسی قرار گرفته است. با توجه به مطالعات انجام شده برای مسئله در ابتدا با طراحی اصول غلبه مسئله و استفاده از آنها، مدل های ریاضی و الگوریتم شاخه و کران ارائه میگردد. با توجه به پیچیدگی مسئله، الگوریتمهای شاخه و کران و مدل های ریاضی برای رسیدن به جواب بهینه در مسائل با ابعاد متوسط نیازمند صرف زمان بسیار زیادی هستند. از این رو در ادامه به منظور بهدست آوردن جوابهای خوب برای ابعادی از مسائلی که روش های بهینه قادر به حل آنها در زمان معقول نمیباشند، یک الگوریتم ابتکاری ارائه میگردد که مسئله را در دو مرحله شامل ایجاد جواب اولیه و بهبود آن حل مینماید. نتایج محاسباتی برای مسئله زمان بندی کمینه سازی مجموع زمانها تکمیل در زمانبندی ماشین های موازی با زمانها آماده سازی وکارهای تقسیم پذیر نشان داد که الگوریتم شاخه وکران ارائه شده نسبت به دو مدل ریاضی از کارایی بهتری برخوردار بوده و توانست مسائل با اندازه 27 واحد کاری به ازای 8 ماشین و 9 کار را در محدوده زمانی 3600 ثانیه حل نماید. الگوریتم ابتکاری ارائه شده نیز توانایی حل مسائل تا ابعاد 72 واحد کاری به ازای 9 کار و 8 ماشین را با متوسط درصد خطای 2,5 درصد دارد.

Keywords:

زمانبندی , ماشینهای موازی , تقسیمپذیری , شاخه و کران , مدل ریاضی