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

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