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

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

کلیدواژه ها:

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