یک الگوریتم شاخه و کران برای مساله زمان بندی استوار کار کارگاهی

مساله زمان بندی کارکارگاهی قطعی یکی ازپیچیده ترین مسائل کلاسیک درزمینه زمانبندی می باشد که درآن مجموعه ای ازکارها باید برروی مجموعه ای ازماشین های پردازش شوند به گونه ای که زمان های پردازش تمامی کارها بصورت قطعی درنظر گرفته می شود دراین مساله هر کار متشکل از تعدادی عملیات است که هرعملیات برروی یک ماشین پردازش شده و توالی عملیات ها برای هرکار مستقل از کارهای دیگر است رایج ترین تابع هدف برای این مساله درادبیات زمان بندی کمینه سازی طول مدت زمان بندی است که برابر است با زمان اتمام آخرین کارپایان یافته از انجا که درعمل اکثر پارامترهای مساله تصادفی می باشد دراین مقاله به بررس یحالتی از مساله زمان بندی کارکارگاهی می پردازیم که درآن زمان اجرای هرعملیات که قسمتی از یک کار است بصورت یک متغیر تصادفی نرمال می باشد و یک زمان تحویل کلی نیز برای اتمام کلی کارها تعیین شده است.

Keywords:

زمان بندی کارکارگاهی , زمان پردازش تصادفی , زمان بندی استوار , الگوریتم شاخه وکران