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

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

تاریخچه

این مسئله حداقل هفتاد سال قدمت دارد.

نمایش مسئله

گراف منفصل(disjunctive graph) یکی از بهترین مدل‌های مورد استفاده برای تشریح‌کردن سامانه‌های مختلف این مسئله است.
لیست الگوریتم‌های زمان‌بندی موجود در سال ۱۹۶۶ را گراهام از قبل آماده کرده بود، که تمامی آن‌ها (2-1/m)رقابتی بوده‌اند. منظور از m در این‌جا تعداد ماشین‌ها است. همچنین این امر که زمان‌بندی لیست، راه حل بهینه برای مسئلهٔ آنلاین ۲ یا ۳ ماشین است اثبات شده بود. الگوریتم Coffman-Graham در سال ۹۲ برای مشاغل یکسان طول، برای ۲ ماشین نیز بهینه و (2-2/m) رقابتی است. در سال ۱۹۹۲، بارتال، فیات، کارلفت و وهرا الگوریتمی ۱٫۹۸۶-رقابتی ارائه کردند. در سال ۱۹۹۴، کارگر، فیلیپس و تورنگ یک الگوریتم ۱٫۹۴۵ رقابتی ارائه دادند. در سال ۱۹۹۲، آلبرز یک الگوریتم جدید که ۱٫۹۲۳-رقابتی بود ارائه داد. در حال حاضر، بهترین پاسخ موجود، الگوریتمی از فلیشر و وهل می‌باشد که یک راه حل ۱٫۹۲۰رقابتی است.
یک حد پایین ۱٫۸۵۲-رقابتی نیز توسط آلبرز ارائه داده شد. نمونه‌های Taillard نقش مهمی در ایجاد زمان‌بندی مغازهٔ کار با اهداف مدت ایجاد(makespan objectives) ایفا می‌کنند.
در سال ۱۹۷۶ گری، اثبات کرد که این مسئله برای nهای بزرگ‌تر از ۲ یک مسئلهٔ NP-Complete است، به این معنا که برای بیش از ۳ ماشین، نمی‌توان راه‌حلی از زمان چندجمله ای برای حل این مسئله ارائه داد.

بهینه‌سازی آفلاین (برون خطی) بازهٔ زمانی تولید

ساده‌ترین حالت مسئله حداقل‌کردن offline makespan برای مشاغل اتومیک می‌باشد، که در این مشاغل اتومیک، مشاغلی هستند که شغل قابلیت تقسیم‌شدن به مشاغل کوچکتر را ندارد. برای مثال، این مفهوم مشابه بسته‌بندی کردن چندین تکه با حجم‌های متفاوت درون تعداد ثابتی از صندوق‌ها، به گونه‌ای که بزرگترین حجم صندوق مورد نیاز، در کمترین حد ممکن باشد. (در صورتی که حالت برعکس این مورد، یعنی کمینه کردن تعداد صندوق‌ها و ثابت‌بودن سایز هر صندوق مد نظر باشد، این مسئله تبدیل به مسئلهٔ دیگری به نام مسئلهٔ دسته‌بندی صندوق‌ها می‌شود).
هاشبوم و اشمویز یک شمای تخمینی از زمان چند جمله‌ای را در سال ۱۹۸۷ ارائه دادند که یک راه حل تخمینی برای مسئله را با هر درجه‌ای از دقت که مد نظر باشد به دست می‌آورد.

مشاغلی که از چندین عملیات تشکیل شده‌اند

حالت ابتدایی از زمان‌بندی کردن مشاغل با چندین عملیات(M)، بر روی چندین ماشین (M)، به گونه‌ای که تمامی عملیات اول باید روی ماشین اول اجرا شوند، تمامی عملیات دوم روی ماشین دوم و …. و چند شغل نمی‌توانند به صورت موازی اجرا شوند، به عنوان مسئله زمان‌بندی مغازهٔ باز شناخته می‌شوند. الگوریتم‌های مختلفی برای این سؤال موجود است، از جمله الگوریتم‌های ژنتیک.