مقایسه الگوریتم های تلفیقی ژنتیک و بهینه سازی اجتماع مورچگان در حل مساله زمانبندی چند هدفه

در بسیاری از مسائل زمانبندی در دنیای واقعی مانند زمانبندی کارگاهی ماشین آلات، منابع انسانی و زمانبندی آموزشی، چندین معیار برای ارزیابی کیفیت جواب یا همان برنامه زمانبندی تولید شده در نظر گرفته می شوند که از آن جمله میتوان به طول مدت برنامه زمانبندی، میزان تاخیر، دیرکرد و یا جلو بودن از برنامه و نیز تامین دیگر اولویت های فردی اشاره کرد. لزوم بهینه سازی هم زمان چند تابع هدف (بهینه سازی چند هدفه) که اغلب در تعارض با یکدیگرند افزون بر اینکه مساله زمان بندی دارای ماهیت ترکیبی است و از گروه مسایل NP-hard به شمار می رود، بر ضرورت استفاده از روش های غیر دقیق و ابتکاری برای حل صحه می گذارد. تاکنون الگوریتم های فراابتکاری مختلف اما معدودی با رویکرد چند هدفه به منظور دستیابی به مجموعه جواب های خوب و نزدیک بهینه در یک بار اجرا و بدون نیاز به تبدیل مساله به مدل تک هدفه ارایه شده است. در نوشتار پیش رو دو الگوریتم فرا ابتکاری جمعیت محور از نوع تلفیقی ژنتیک و بهینه سازی به شیوه اجتماع مورچه برای حل مساله زمانبندی چند هدفه با هدف مقایسه قدرت حل و نیز افزایش کارایی آنها نسبت به رویکردهای کلاسیک طراحی و ارایه شده است. در توسعه ی این دو الگوریتم رویکرد مورد استفاده در بهینه سازی چند هدفه، استراتژی تخصیص برازش در روش SPEA2 می باشد. مساله زمانبندی مورد نظر از نوع کارگاهی job-shop در ابعاد مختلف و با دو تابع هدف کمینه سازی زمان تکمیل (makespan) و کمینه سازی میانگین زمان شناوری (Mean flowtime) برای حل انتخاب شده و نتایج مورد بررسی قرار گرفته است.

کلیدواژه ها:

زمانبندی ، بهینه سازی چند هدفه ، الگوریتم های ژنتیک ، بهینه سازی اجتماع مورچگان