موضوع مقاله: زمان‌بندی مغازه کارها | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # زمان‌بندی مغازه کارها | مقدمه: صورت اصلی آن در ادامه آمده است: در این مسئله n کار j1, j2, …, jn با اندازه‌های متفاوت که باید روی m ماشین یکسان زمان‌بندی شوند در تلاشند تا زمان کل(makespan) را به حداقل برسانند. | ## بخش 1: زمان‌بندی مغازه کارها | ماشین‌ها می‌توانند بین شغل‌ها زمان مشخصی فاصله بیندازند یا اینکه بدون فاصله شغل‌ها را انجام دهند. هدف مسئله می‌تواند عملکردهای مختلفی چون کم کردن زمان کل، نرم Lp، تأخیر ورود، بیشترین تأخیر درانجام کارها و غیره باشد. شغل‌ها می‌توانند محدودیت داشته باشند، برای مثال، شغل i باید قبل از شروع شغل j تمام شود. شغل‌ها و ماشین‌ها محدودیت‌های مشترک داشته باشند، برای مثال، شغل‌های مشخصی فقط بتوانند روی برخی ماشین‌ها اجرا شوند. لیست الگوریتم‌های زمان‌بندی موجود در سال ۱۹۶۶ را گراهام از قبل آماده کرده بود، که تمامی آن‌ها (2-1/m)رقابتی بوده‌اند. همچنین این امر که زمان‌بندی لیست، راه حل بهینه برای مسئلهٔ آنلاین ۲ یا ۳ ماشین است اثبات شده بود. در حال حاضر، بهترین پاسخ موجود، الگوریتمی از فلیشر و وهل می‌باشد که یک راه حل ۱٫۹۲۰رقابتی است. در سال ۱۹۷۶ گری، اثبات کرد که این مسئله برای nهای بزرگ‌تر از ۲ یک مسئلهٔ ان‌پی کامل است، به این معنا که برای بیش از ۳ ماشین، نمی‌توان راه‌حلی از زمان چندجمله ای برای حل این مسئله ارائه داد. | ## بخش 2: زمان‌بندی مغازه کارها | بهینه‌سازی آفلاین (برون خطی) بازهٔ زمانی تولید ساده‌ترین حالت مسئله حداقل‌کردن offline makespan برای مشاغل اتومیک می‌باشد، که در این مشاغل اتومیک، مشاغلی هستند که شغل قابلیت تقسیم‌شدن به مشاغل کوچکتر را ندارد. برای مثال، این مفهوم مشابه بسته‌بندی کردن چندین تکه با حجم‌های متفاوت درون تعداد ثابتی از صندوق‌ها، به گونه‌ای که بزرگ‌ترین حجم صندوق مورد نیاز، در کمترین حد ممکن باشد. (در صورتی که حالت برعکس این مورد، یعنی کمینه کردن تعداد صندوق‌ها و ثابت‌بودن سایز هر صندوق مد نظر باشد، این مسئله تبدیل به مسئلهٔ دیگری به نام مسئلهٔ دسته‌بندی صندوق‌ها می‌شود). هاشبوم و اشمویز یک شمای تخمینی از زمان چند جمله‌ای را در سال ۱۹۸۷ ارائه دادند که یک راه حل تخمینی برای مسئله را با هر درجه‌ای از دقت که مد نظر باشد به دست می‌آورد. مشاغلی که از چندین عملیات تشکیل شده‌اند حالت ابتدایی از زمان‌بندی کردن مشاغل با چندین عملیات(M)، بر روی چندین ماشین (M)، به گونه‌ای که تمامی عملیات اول باید روی ماشین اول اجرا شوند، تمامی عملیات دوم روی ماشین دوم و …. و چند شغل نمی‌توانند به صورت موازی اجرا شوند، به عنوان مسئله زمان‌بندی مغازهٔ باز شناخته می‌شوند. الگوریتم جانسون برای حل حالتی از این مسئله که در آن ۲ ماشین وN شغل متفاوت موجود است و تمامی مشاغل باید به ترتیب مورد پردازش قرارگیرند، می‌توان از یک الگوریتم مکاشفه‌ای که توسط S.M. قدم‌های مختلف این الگوریتم به صورت زیر است: شغل Pi دارای دو عمل است، طول هرکدام از این عمل‌ها pi۱ و pi۲ است، که روی ماشین‌های M۱ و M۲ به همان ترتیب اجرا می‌شوند. | ## بخش 3: زمان‌بندی مغازه کارها | در صورتی که کمینه به Pk۱ تعلق داشته باشد، K را از لیست A حذف کنید، K را به انتهای لیست L۱ اضافه نمایید. در صورتی که مقدار کمینه به Pk۲ تعلق داشته باشد، قدم ۳: قدم ۲ را تکرار کنید تا زمانی که List A خالی شود. اما از آن جهت که این روش، روشی بهینه و ساده برای محاسبه است، بعضی از پژوهشگران در جهت تعمیم این الگوریتم به حالت M ماشین تلاش کرده‌اند. ایده مورد نظر به صورت زیر است: تصور کنید که هر شغل، نیاز به M عمل مختلف دنبال هم، روی M1, M2, M3, …, Mm دارد. ما به این گونه عمل می‌کنیم که m/۲ ماشین اول را به یک ماشین بزرگ (موهومی) تبدیل می‌کنیم و آن را MC۱ می‌نامیم. ماشین‌های باقی‌مانده دیگر را نیز به یک ماشین بزرگ دیگر به نام MC۲ تبدیل می‌کنیم. | ## جمع‌بندی | در این صورت، زمان پردازش نهایی برای شغل P روی MC۱ برابر است با مجموع زمان عمل‌ها روی m/۲ ماشین اول و زمان پردازش نهایی شغل p روی MC۲ برابر با مجموع زمان عمل‌ها روی m/۲ ماشین آخر است.