بهینه سازی فعالیت ها در زمان بندی کارگاهی بعنوان مساله ارضای محدودیت توسط الگوریتم های ژنتیک

مساله زمانبند ی کارگاه ی از دید تئور ی و عم لی یک مساله مهارنشدن ی به شمار می آید. با وجود اینکه تاکنون شگرده ای گوناگونی از س وی متخصصان صنعت و دانشگاه جهت حل این مساله ارائه شده است، اما متاسفانه این روش ها در رسیدن به یک راه حل بهینه ناکام مانده اند . در این مقاله روشی مبتنی بر الگوریتم های ژنتیکی پیشنهاد شده است. این روش مبتنی بر یک خصوصیت محوری است و آن اینکه همواره در تمام ی مراحل شبیه ساز ی، از نسل اول تا آخر، کلیه کروموزوم ها معتبر هستند، یعن ی قوانین پیش نیاز ی در آنها رعایت شده اس ت. حفظ این خصوصیت از دو جن به قابل توجه است . اول اینکه الگوریتم پیشنهاد ی نباید فضا ی حالت (فضای جستجو) را محدود سازد چرا که این امر می تواند موجب حذف و از دست دادن جواب بهینه مساله شود. دیگر آنکه در صورت حفظ اعتبار کروموزوم ها، دیگر نیا زی به بررسی این مساله در طول اجرای شبیه سازی نیست و این به معنای کم شدن سربار اصلی برنامه و کمک در جهت سرعت بخشیدن به اجر ای آن می باشد. الگوریتم پیشنهادی در محیطMATLAB پیاده سازی شده و نتایج آن در مقاله آمده است.

کلیدواژه ها:

زمان بندی کارگاهی ، ارضای محدودیت ، ایستگاه ، کار ، الگوریتم ژنتیک ، نسل ، کروموزوم