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

کلمات کلیدی