احسان ملایی

در این مقاله مسئلۀ زمان بندی تک ماشین با تولید دسته ای و خرابی تصادفی ماشین بررسی می شود. در این مسئله هر کار متعلق به یک خانوادۀ کار است و هر خانوادۀ کار زمان آماده سازی معلوم و مستقل از توالی دارد. همچنین فرض می شود یک خرابی ماشین در طول افق برنامه ریزی اتفاق می افتد و زمان شروع و طول تصادفی با توزیع احتمال دلخواه و از قبل مشخص دارد. تابع هدف مسئله حداقل سازی مجموع حداکثر زودکرد و حداکثر دیرکرد موردانتظار کارهاست. تاکنون در پژوهش های گذشته مطالعه ای بر این مسئله مشاهده نشده است. برای این مسئله یک مدل جدید برنامه ریزی عدد صحیح خطی مختلط توسعه داده شده است. با توجه به NP-hard بودن مسئله برای حل بهینۀ آن، یک الگوریتم شاخه و کران جدید با اصول غلبه و یک حد پایین کارا ارائه شده است که از یک الگوریتم ابتکاری جدید برای به دست آوردن حد بالا استفاده می کند. به منظور ارزیابی عملکرد الگوریتم های معرفی شده، تعداد 2520 عدد مسئلۀ نمونه طراحی و با الگوریتم های ارائه شده، حل شده است. نتایج محاسباتی نشان می دهد 98% مسائل نمونه در محدودۀ زمانی مشخص شده با الگوریتم شاخه و کران به صورت بهینه حل شده اند و میانگین درصد انحراف از جواب بهینه در الگوریتم ابتکاری ارا ئه شده کمتر از 30% است. این موارد کارایی الگوریتم های ارائه شده را تأیید می کند.