زمان بندی مغازه کارها

زمان بندی مغازه کارها یا مسئلهٔ زمان بندی کار کارگاهی یا مسئلهٔ مغازۂ کارها (به انگلیسی: Job shop scheduling) یک مسئلهٔ بهینه سازی علوم رایانه و تحقیق در عملیات است که در آن شغل های ایده آل به منابع در زمان های خاصی نسبت داده می شوند. صورت اصلی آن در ادامه آمده است:
ماشین ها می توانند وابسته، مستقل یا یکسان باشند.
ماشین ها می توانند بین شغل ها زمان مشخصی فاصله بیندازند یا اینکه بدون فاصله شغل ها را انجام دهند.
ماشین ها می توانند به صورت وابسته به دنباله (sequence-dependent) برنامه ریزی شوند.
هدف مسئله می تواند عملکردهای مختلفی چون کم کردن زمان کل، نرم Lp، تأخیر ورود، بیشترین تأخیر درانجام کارها و غیره باشد. *همچنین می تواند یک مسئلهٔ بهینه سازی چند هدفه باشد.
شغل ها می توانند محدودیت داشته باشند، برای مثال، شغل i باید قبل از شروع شغل j تمام شود.
شغل ها و ماشین ها محدودیت های مشترک داشته باشند، برای مثال، شغل های مشخصی فقط بتوانند روی برخی ماشین ها اجرا شوند.
مجموعه ای از شغل ها بتوانند به مجموعهٔ متفاوتی از ماشین ها مرتبط باشند.
زمان پردازش قطعی (deterministic) یا احتمالی(probabilistic).
ممکن است محدودیت های دیگری نیز وجود داشته باشد.
در این مسئله n شغل j1, j2, …, jn با اندازه های متفاوت که باید روی m ماشین یکسان زمان بندی شوند در تلاشند تا زمان کل(makespan) را به حداقل برسانند. زمان خالی مجموع زمان لازم برای انجام همهٔ شغل هاست (که همهٔ شغل ها تمام شده اند).
امروزه، این مسئله به عنوان یک مسئلهٔ پویا(dynamic scheduling) مطرح می شود، که با ارائه شدن هر شغل، الگوریتم پویا باید با اطلاعات موجود تصمیم گیری کند قبل از اینکه شغل بعدی مطرح شود.
این مسئله یکی از مشهورترین مسائل پویاست، و اولین مسئله ای بود که برای آن تحلیل رقابتی(competitive analysis) به وسیلهٔ Graham در سال ۱۹۶۶ مطرح شد. بهترین نمونه های مسئله برای مدل پایه با هدف بهینه سازی زمان کل به وسیلهٔ Taillard مطرح شد.