سه الگوريتم ابتكاري براي حداقل سازي ميكسپن در مسئله ماشين هاي موازي

Three heuristics algorithms for makespan minimization in parallel machines scheduling problem

با توجه به NP-hard بودن مسئله ماشينهاي موازي با تابع هدف ميكسپن, امكان ارائه الگوريتمي كه رسيدن به چواب بهينه را در زمان معقول تضمين نمايد وجود ندارد. در ادبيات تلاشهاي زيادي براي ارائه الگوريتمهاي ساده ولي كارا كه بتواند جوابي خوب در زمان خوب ارائه نمايد شده است. در اين تحقيق نيز با اين هدف ما بر ان شديم تا سه الگوريتم جهت نيل به اين هدف را ارائه نماييم. الگوريتم اول براي رفع اشكالات موجود در روشهاي كوچكترين زمان پردازش و بزرگترين زمان پردازش ارائه شده و الگوريتمهاي دوم و سوم با ايده اي نو براي حل اين مسئله ارائه شدهاند. در نهايت نيز مقايسه تحليلي بين الگوريتمهاي ارائه شده صورت گرفته است.