حساب کاربری
​
زمان تقریبی مطالعه: 6 دقیقه
لینک کوتاه

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

مسئلهٔ زمان‌بندی کار کارگاهی (به انگلیسی: Job shop scheduling) یک مسئلهٔ بهینه‌سازی در مهندسی صنایع و تحقیق در عملیات است که در آن کارها به منابع در زمان‌های خاصی نسبت داده می‌شوند. صورت اصلی آن در ادامه آمده‌ است:

در این مسئله n کار j1, j2, …, jn با اندازه‌های متفاوت که باید روی m ماشین یکسان زمان‌بندی شوند در تلاشند تا زمان کل(makespan) را به حداقل برسانند. زمان خالی مجموع زمان لازم برای انجام همهٔ کارهاست (که همهٔ کارها تمام شده‌اند).

امروزه، این مسئله به عنوان یک مسئلهٔ پویا(dynamic scheduling) مطرح می‌شود، که با ارائه شدن هر کار، الگوریتم پویا باید با اطلاعات موجود تصمیم‌گیری کند قبل از اینکه کار بعدی مطرح شود.

این مسئله یکی از مشهورترین مسائل پویاست، و اولین مسئله‌ای بود که برای آن تحلیل رقابتی(competitive analysis) به وسیلهٔ Graham در سال ۱۹۶۶ مطرح شد. بهترین نمونه‌های مسئله برای مدل پایه با هدف بهینه‌سازی زمان کل به وسیلهٔ Taillard مطرح شد.

فهرست

  • ۱ گونه‌های مختلف مسئله
  • ۲ تاریخچه
  • ۳ نمایش مسئله
  • ۴ بهینه‌سازی آفلاین (برون خطی) بازهٔ زمانی تولید
  • ۵ مشاغلی که از چندین عملیات تشکیل شده‌اند
  • ۶ الگوریتم جانسون
  • ۷ منابع
  • ۸ پیوند به بیرون

گونه‌های مختلف مسئله

  • ماشین‌ها می‌توانند وابسته، مستقل یا یکسان باشند.
  • ماشین‌ها می‌توانند بین شغل‌ها زمان مشخصی فاصله بیندازند یا اینکه بدون فاصله شغل‌ها را انجام دهند.
  • ماشین‌ها می‌توانند به صورت وابسته به دنباله (sequence-dependent) برنامه‌ریزی شوند.
  • هدف مسئله می‌تواند عملکردهای مختلفی چون کم کردن زمان کل، نرم Lp، تأخیر ورود، بیشترین تأخیر درانجام کارها و غیره باشد. *همچنین می‌تواند یک مسئلهٔ بهینه‌سازی چند هدفه باشد.
  • شغل‌ها می‌توانند محدودیت داشته باشند، برای مثال، شغل i باید قبل از شروع شغل j تمام شود.
  • شغل‌ها و ماشین‌ها محدودیت‌های مشترک داشته باشند، برای مثال، شغل‌های مشخصی فقط بتوانند روی برخی ماشین‌ها اجرا شوند.
  • مجموعه‌ای از شغل‌ها بتوانند به مجموعهٔ متفاوتی از ماشین‌ها مرتبط باشند.
  • زمان پردازش قطعی (deterministic) یا احتمالی(probabilistic).
  • ممکن است محدودیت‌های دیگری نیز وجود داشته باشد.

تاریخچه

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

نمایش مسئله

گراف منفصل(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۲ به همان ترتیب اجرا می‌شوند.

  • قدم ۱: لیست A = list L2 = {}, List L1 = {},{۱، ۲، ۳، …, N}
  • قدم ۲: از بین تمامی مدت عمل‌های ممکن، مدت کمینه را انتخاب نمایید.

در صورتی که کمینه به Pk۱ تعلق داشته باشد، K را از لیست A حذف کنید، K را به انتهای لیست L۱ اضافه نمایید.

در صورتی که مقدار کمینه به Pk۲ تعلق داشته باشد،

  • قدم ۳: قدم ۲ را تکرار کنید تا زمانی که List A خالی شود.
  • قدم ۴: List L۱ و List L۲ را با هم مخلوط کنید. این دنباله بهینه می‌باشد.

روش جانسون، تنها در حالتی که دو ماشین داشته باشیم به صورت بهینه کار می‌کند. اما از آن جهت که این روش، روشی بهینه و ساده برای محاسبه است، بعضی از پژوهشگران در جهت تعمیم این الگوریتم به حالت 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:

۱ ۲ ۳ := ۱ ۴ ۲ ۱

۲ ۳ ۶ ۲

۳ ۷ ۲ ۳

۴ ۱ ۵ ۸;

منابع

  1. ↑ Graham, R. (1966). "Bounds for certain multiprocessing anomalies" (PDF). Bell System Technical Journal. 45: 1563–1581.
  2. ↑ B. Roy, B. Sussmann, Les problèmes d’ordonnancement avec constraintes disjonctives, SEMA, Note D.S. , No. 9, Paris, 1964.
  3. ↑ Jacek Bl̶ażewicz, Erwin Pesch, Mal̶gorzata Sterna, The disjunctive graph machine representation of the job shop scheduling problem, European Journal of Operational Research, Volume 127, Issue 2, 1 December 2000, Pages 317-331, ISSN 0377-2217, 10.1016/S0377-2217(99)00486-5.
  4. ↑ Coffman, E. G. , Jr.; Graham, R. L. (1972), "Optimal scheduling for two-processor systems" (PDF), Acta Informatica, 1: 200–213, MR 0334913.
  5. ↑ Lam, Shui; Sethi, Ravi (1977), "Worst case analysis of two scheduling algorithms", SIAM Journal on Computing, 6 (3): 518–536, doi:10.1137/0206037, MR 0496614.
  6. ↑ Bartal, Y. (1992). "New Algorithms for an Ancient Scheduling Problem". Proc. 24th ACM Symp. Theory of Computing. pp. 51–58. doi:10.1145/129712.129718.
  7. ↑ Karger, D. (1994). "A Better Algorithm for an Ancient Scheduling Problem". Proc. Fifth ACM Symp. Discrete Algorithms.
  8. ↑ Albers, Susanne (1992). "Improved parallel integer sorting without concurrent writing". Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms. pp. 463–472. ;
  9. ↑ Fleischer, Rudolf (2000). Algorithms - ESA 2000. Berlin / Heidelberg: Springer. pp. 202–210. ISBN 978-3-540-41004-1.
  10. ↑ Albers, Susanne (1999). "Better bounds for online scheduling". SIAM Journal on Computing. 29 (2): 459–473. doi:10.1137/S0097539797324874.
  11. ↑ Garey, M.R. (1976). "The Complexity of Flowshop and Jobshop Scheduling". Mathematics of Operations Research. 1 (2): 117–129. doi:10.1287/moor.1.2.117. JSTOR 3689278.
  12. ↑ Hochbaum, Dorit; Shmoys, David (1987). "Using dual approximation algorithms for scheduling problems: theoretical and practical results" (PDF). Journal of the ACM. 34 (1): 144–162. doi:10.1145/7531.7535.
  13. ↑ Khuri, Sami (1999). "Genetic Algorithms for Solving Open Shop Scheduling Problems". Proceedings of the 9th Portuguese Conference on Artificial Intelligence: Progress in Artificial Intelligence. London: Springer Verlag. CiteSeerX: 10.1.1.29.4699. ;
  14. ↑ S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954)61-68.

پیوند به بیرون

Job shop scheduling

آخرین نظرات
کلیه حقوق این تارنما متعلق به فرا دانشنامه ویکی بین است.