از ویکیپدیا، دانشنامه آزاد
مسئلهٔ زمانبندی کار کارگاهی (به انگلیسی: 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)، به گونهای که تمامی عملیات اول باید روی ماشین اول اجرا شوند، تمامی عملیات دوم روی ماشین دوم و …. و چند شغل نمیتوانند به صورت موازی اجرا شوند، به عنوان مسئله زمانبندی مغازهٔ باز شناخته میشوند. الگوریتمهای مختلفی برای این سؤال موجود است، از جمله الگوریتمهای ژنتیک.[۱۳]
برای حل حالتی از این مسئله که در آن ۲ ماشین وN شغل متفاوت موجود است و تمامی مشاغل باید به ترتیب مورد پردازش قرارگیرند، میتوان از یک الگوریتم مکاشفهای که توسط S.M. Johnson ایجاد شدهاست، استفاده کرد.[۱۴] قدمهای مختلف این الگوریتم به صورت زیر است:
شغل Pi دارای دو عمل است، طول هرکدام از این عملها pi۱ و pi۲ است، که روی ماشینهای M۱ و M۲ به همان ترتیب اجرا میشوند.
در صورتی که کمینه به Pk۱ تعلق داشته باشد، K را از لیست A حذف کنید، K را به انتهای لیست L۱ اضافه نمایید.
در صورتی که مقدار کمینه به Pk۲ تعلق داشته باشد،
روش جانسون، تنها در حالتی که دو ماشین داشته باشیم به صورت بهینه کار میکند. اما از آن جهت که این روش، روشی بهینه و ساده برای محاسبه است، بعضی از پژوهشگران در جهت تعمیم این الگوریتم به حالت M ماشین تلاش کردهاند.
ایده مورد نظر به صورت زیر است:
تصور کنید که هر شغل، نیاز به M عمل مختلف دنبال هم، روی M1, M2, M3, …, Mm دارد. ما به این گونه عمل میکنیم که m/۲ ماشین اول را به یک ماشین بزرگ (موهومی) تبدیل میکنیم و آن را MC۱ مینامیم. ماشینهای باقیمانده دیگر را نیز به یک ماشین بزرگ دیگر به نام MC۲ تبدیل میکنیم.
در این صورت، زمان پردازش نهایی برای شغل P روی MC۱ برابر است با مجموع زمان عملها روی m/۲ ماشین اول و زمان پردازش نهایی شغل p روی MC۲ برابر با مجموع زمان عملها روی m/۲ ماشین آخر است.
در این صورت، ما توانستیم این مسئلهٔ m-machine را به یک مسئلهٔ برنامهریزی ۲-machine کاهش دهیم. حال میتوانیم با استفاده از الگوریتم جانسون، این مسئله را حل کنیم.
اینجا یک مثال از مسئله زمانبندی مغازهٔ کارها که به صورت AMPL به عنوان یک مسئلهٔ mixed-integer programming محدودیتهای نشانگر آورده شدهاست.
param N_JOBS;
param N_MACHINES;
set JOBS ordered = 1..N_JOBS;
set MACHINES ordered = 1..N_MACHINES;
param ProcessingTime{JOBS, MACHINES}> 0;
param CumulativeTime{i in JOBS, j in MACHINES} = sum {jj in MACHINES: ord(jj) <= ord(j)} ProcessingTime[i,jj];
param TimeOffset{i1 in JOBS, i2 in JOBS: i1 <> i2} = max {j in MACHINES}(CumulativeTime[i1,j] - CumulativeTime[i2,j] + ProcessingTime[i2,j]);
var end>= ۰;
var start{JOBS}>= ۰;
var precedes{i1 in JOBS, i2 in JOBS: ord(i1) <ord(i2)} binary;
minimize makespan: end;
subj to makespan_def{i in JOBS}: end>= start[i] + sum{j in MACHINES} ProcessingTime[i,j];
subj to no12_conflict{i1 in JOBS, i2 in JOBS: ord(i1) <ord(i2)}:precedes[i1,i2] ==> start[i2]>= start[i1] + TimeOffset[i1,i2];
subj to no21_conflict{i1 in JOBS, i2 in JOBS: ord(i1) <ord(i2)}:!precedes[i1,i2] ==> start[i1]>= start[i2] + TimeOffset[i2,i1];
data;
param N_JOBS := ۴;
param N_MACHINES := ۳;
param ProcessingTime:
۱ ۲ ۳ := ۱ ۴ ۲ ۱
۲ ۳ ۶ ۲
۳ ۷ ۲ ۳
۴ ۱ ۵ ۸;
Seamless Wikipedia browsing. On steroids.