مدل سازی مسئله زمان بندی تک ماشین با تولید دسته ای و خرابی تصادفی و حل آن به وسیله روش شاخه و کران

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