کمینه‌کردن تعداد کارهای تاخیردار در زمان‌بندی جریان کارگاهی با کارهای رو به زوال و ورودی‌های غیر همزمان

در این مقاله، زمان‌بندی کارهای رو به زوال با تابع زوال خطی روی جریان کارگاهی دو ماشین با هدف کمینه‌کردن تعداد کارهای تاخیردار و با فرض ورود غیر همزمان کارها بررسی شده است. برای به دست آوردن جوابی نزدیک به بهینه در زمانی کوتاه، یک روش ابتکاری و برای حل دقیق آن یک الگوریتم شاخه و کران ارائه شده است. نتایج نشان می‌دهد الگوریتم شاخه و کران مسائل را تا 24 کار در رده مسائل بزرگ و 22 کار در رده مسائل کوچک، در زمان منطقی حل می‌کند. همچنین درصد بالایی از گره‌ها در روش شاخه و کران توسط اصول غلبه و حدود پایین قطع می‌شود که نشان‌دهنده‌ی کارایی الگوریتم شاخه و کران است. متوسط نسبت جواب بهینه به جواب الگوریتم ابتکاری حداکثر برابر 1٫15 است که این عدد در مقایسه با سایر تحقیقات مربوط به تعداد کارهای تاخیردار عدد بسیار خوبی است.