زمانبندی کارگاهی
- معرفیشده توسط
- Pinedo, M. L.
- سال
- 2016
- نوع
- Combinatorial scheduling problem
- خانواده
- Optimization
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
زمانبندی کارگاهی مسئله تخصیص مجموعهای از کارها (وظایف) به مجموعهای از ماشینها (منابع) در طول زمان است، با رعایت محدودیتهای تقدم و ظرفیت، و با هدف بهینهسازی معیارهای عملکردی مانند زمان تکمیل کل (makespan)، تأخیر، یا هزینه. مسئله کارگاهی یک مسئله بهینهسازی ترکیبیاتی کلاسیک در تحقیق در عملیات است که از طریق ابتکارات (قوانین اعزام حریصانه، تبرید شبیهسازیشده، الگوریتمهای ژنتیک) و الگوریتمهای دقیق (شاخه و کران، برنامهریزی محدودیتگرا) حل میشود. این مسئله برای تولید، مدیریت پروژه، و زمانبندی محاسباتی اساسی است.
شهود پشت روش
یک کارگاه ماشینکاری کوچک با ۱۰ ماشین را تصور کنید. یک سفارش مشتری (کار) شامل ۵ قطعه است که هر کدام به دنبالهای از عملیات روی ماشینهای مختلف نیاز دارند: قطعه ۱ نیاز به ماشینکاری روی ماشین A، سپس سوراخکاری روی ماشین C دارد. قطعه ۲ نیاز به سوراخکاری روی ماشین B، سپس جوشکاری روی ماشین D دارد. همه قطعات برای مونتاژ نهایی همگرا میشوند. چالش این است: همه عملیات را طوری زمانبندی کنید که زمان تکمیل کل به حداقل برسد، بدون تجاوز از ظرفیت ماشین، و با رعایت توالی عملیات برای هر قطعه. اگر قطعه ۱ را خیلی دیر به ماشین A اختصاص دهید، ماشین C بیکار میماند. اگر ماشین C را بیش از حد بارگذاری کنید، همه چیز به تأخیر میافتد. مسئله کارگاهی این پیچیدگی را به تصویر میکشد: با ۱۰۰ کار و ۲۰ ماشین، تعداد زمانبندیهای ممکن نجومی است، که حل دقیق را غیرعملی میکند. در عوض، از ابتکارات برای یافتن یک زمانبندی خوب (نه لزوماً بهینه) به سرعت استفاده میکنید.
تاریخ
مسئله زمانبندی کارگاهی در دهه ۱۹۵۰ به عنوان یک مسئله تحقیقاتی در تحقیق در عملیات پدیدار شد. کار پیشگامانه جانسون (۱۹۵۴) مسئله دو ماشین را بهینه حل کرد؛ فیشر و تامپسون (۱۹۶۳) مسائل معیار را ایجاد کردند که امروزه نیز مورد استفاده قرار میگیرند. این مسئله NP-hard است (در دهه ۱۹۷۰ اثبات شد)، که توسعه ابتکارات و فراابتکارات را تحریک کرد. رویکردهای مدرن شامل برنامهریزی محدودیتگرا (دهههای ۱۹۹۰-۲۰۰۰)، الگوریتمهای ژنتیک، و روشهای ترکیبی است. زمانبندی کارگاهی اکنون یک حوزه بالغ با کاربردهایی فراتر از تولید به رایانش ابری، مخابرات، و حمل و نقل است.
چه زمانی استفاده شود
زمانبندی کارگاهی در هر محیط تولیدی یا خدماتی با چندین ماشین/منبع و کارها با توالی عملیات متمایز کاربرد دارد. کاربردهای معمول شامل کارگاههای ماشینکاری، چاپخانهها، ساخت ویفرهای نیمهرسانا، بیمارستانها (زمانبندی اتاق عمل)، و زمانبندی پروژه است. زمانی از آن استفاده کنید که پیچیدگی کار زیاد است (چندین عملیات برای هر کار)، استفاده از ماشین حیاتی است، یا تاریخهای سررسید فشرده هستند. در محیطهای خط مونتاژ (جریان خطی) یا عملیات ساده و تکماشینه اهمیت کمتری دارد.
محدودیتها و ملاحظات
- پیچیدگی ترکیبیاتی: یافتن راهحلهای بهینه NP-hard است؛ راهحلهای عملی نیاز به ابتکاراتی دارند که ممکن است بهینه سراسری نباشند.
- راهحلهای ابتکاری وابسته به زمینه هستند؛ قانونی که برای یک کارگاه خوب عمل میکند ممکن است در دیگری عملکرد ضعیفی داشته باشد و نیاز به تنظیم و اعتبارسنجی دارد.
- ورودی ایستا (کارها و ماشینهای ثابت) را فرض میکند؛ کارگاههای واقعی ورودهای پویا، لغو، و خرابی تجهیزات را تجربه میکنند که نیاز به زمانبندی مجدد مکرر دارد.
- پایداری زمانبندی: تغییرات مکرر در زمانبندیها (به دلیل کارهای جدید یا اختلالات) میتواند هزینهها را افزایش داده و هماهنگی با کارگران و مشتریان را پیچیده کند.
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- محدودیتهای پیچیده و واقعبینانه (تقدم، قابلیتهای ماشین، تاریخهای سررسید) را که قوانین زمانبندی ساده نمیتوانند مدیریت کنند، در خود جای میدهد.
- برای معیارهای تجاری مرتبط (زمان تکمیل کل، تأخیر، استفاده از ماشین) به جای قوانین خودسرانه بهینهسازی میکند.
- پاسخ سریع به اختلالات را امکانپذیر میسازد؛ الگوریتمهای زمانبندی مجدد میتوانند برنامههای بازنگری شده را در صورت خرابی ماشین یا ورود یک کار فوری ایجاد کنند.
- فرمولبندی ریاضی امکان تحلیل حساسیت و بررسی مبادلات (مثلاً تأخیر در مقابل زمان تکمیل کل) را فراهم میکند.
- توسط ابزارهای نرمافزاری کارآمد و الگوریتمهای فراابتکاری بالغ پشتیبانی میشود.
کاربردها
- یک کارگاه ماشینکاری دقیق از زمانبندی کارگاهی با تبرید شبیهسازیشده برای زمانبندی بیش از ۲۰۰ قطعه سفارشی در ۱۵ ماشین CNC استفاده میکند که زمان تکمیل کل را ۱۵ درصد کاهش داده و تحویل به موقع را از ۸۵ درصد به ۹۵ درصد بهبود میبخشد.
- یک کارخانه ساخت نیمهرسانا از زمانبندی مبتنی بر محدودیت برای مدیریت بیش از ۵۰۰ مرحله فرآیند در ۵۰ ابزار استفاده میکند که زمان چرخه ویفر را به حداقل رسانده و موجودی در حال پردازش را ۲۰ درصد کاهش میدهد.
- یک شرکت چاپ از زمانبندی کارگاهی پویا برای تخصیص کارهای چاپی به ۸ دستگاه چاپ با قابلیتهای مختلف استفاده میکند که برای ترکیب کار (حجم بالا در مقابل تخصصی) بهینهسازی کرده و زمان تغییر را به حداقل میرساند.
- یک تیم زمانبندی بیمارستان الگوریتمهای زمانبندی کارگاهی را برای زمانبندی اتاق عمل پیادهسازی میکند که جراحان، تیمهای جراحی، و تجهیزات را هماهنگ میکند و استفاده از اتاق عمل را از ۶۵ درصد به ۸۲ درصد بهبود میبخشد.
چگونه کار میکند
چگونه کار میکند
کارها (سفارشات، وظایف) را با توالی عملیات، الزامات ماشین، زمانهای پردازش، و تاریخهای سررسید تعریف کنید. ماشینهای موجود و پنجرههای در دسترس بودن آنها را تعریف کنید.
محدودیتها را مشخص کنید: تقدم عملیات (قطعه ۱ باید عملیات A را قبل از شروع عملیات B به پایان برساند)، ظرفیت (هر ماشین میتواند یک کار را در یک زمان پردازش کند)، و به صورت اختیاری، زمانهای انتشار و تاریخهای سررسید.
یک قانون اعزام (مانند کوتاهترین زمان پردازش، زودترین تاریخ سررسید، نسبت بحرانی) را برای توالیبندی کارها در هر ماشین اعمال کنید و یک زمانبندی اولیه ایجاد کنید.
از فراابتکارات (تبرید شبیهسازیشده، جستجوی ممنوعه، الگوریتمهای ژنتیک، بهینهسازی کلونی مورچگان) برای بهبود زمانبندی از طریق جستجوی محلی یا روشهای مبتنی بر جمعیت استفاده کنید.
کیفیت زمانبندی را ارزیابی کنید (زمان تکمیل کل، تأخیر، زمان بیکاری، زمان بافر). اگر قابل قبول است، اجرا کنید؛ در غیر این صورت، پارامترها را تنظیم کرده و مجدداً بهینهسازی کنید.
دامهای رایج
- بهینهسازی برای معیار اشتباه؛ به حداکثر رساندن استفاده از ماشین ممکن است تأخیر کار را افزایش دهد، در حالی که رعایت همه تاریخهای سررسید ممکن است نیاز به زمان بیکاری قابل توجهی داشته باشد.
- نادیده گرفتن زمانهای راهاندازی و تغییرات؛ زمانبندیای که زمان بیکاری را به حداقل میرساند اما نیاز به راهاندازیهای مکرر و زمانبر دارد ممکن است در عمل بهینه نباشد.
- اعتماد بیش از حد به زمانبندیهای ابتکاری بدون اعتبارسنجی در برابر رفتار واقعی کارگاه؛ محدودیتها اغلب پیچیدهتر از آن چیزی هستند که مدل به تصویر میکشد.
پرسشهای متداول
زمان تکمیل کل (makespan) چیست و چرا اهمیت دارد؟
زمان تکمیل کل، کل زمان از شروع اولین عملیات تا اتمام آخرین عملیات است. این معیار مستقیماً با استفاده از تجهیزات، جریان نقدی (تکمیل سریعتر = پرداخت سریعتر)، و رضایت مشتری مرتبط است. به حداقل رساندن زمان تکمیل کل یک هدف اصلی رایج در زمانبندی کارگاهی است.
تفاوت بین زمانبندی کارگاهی ایستا و پویا چیست؟
زمانبندی ایستا فرض میکند که همه کارها از قبل مشخص هستند؛ شما یک مجموعه ثابت را بهینه میکنید. زمانبندی پویا کارهایی را که در طول زمان میرسند مدیریت میکند؛ زمانبندیها با ورود کارهای جدید یا بروز اختلالات بازنگری میشوند. اکثر کارگاههای واقعی پویا هستند و نیاز به الگوریتمهای بهینهسازی مجدد سریع دارند.
از کدام قانون اعزام باید استفاده کنیم؟
هیچ قانون واحدی غالب نیست. کوتاهترین زمان پردازش (SPT) زمان تکمیل کل را به حداقل میرساند؛ زودترین تاریخ سررسید (EDD) تأخیر را به حداقل میرساند؛ نسبت بحرانی هر دو را متعادل میکند. قوانین را با دادههای تاریخی یا شبیهسازی آزمایش کنید تا بهترین تناسب را برای اولویتها و محدودیتهای کارگاه خود بیابید.
آیا زمانبندی کارگاهی میتواند مهارتهای کارگران و آموزش متقابل را مدیریت کند؟
بله، با گسترش مدل منبع: به جای فقط «ماشین A»، «ماشین A با کارگر ۱» یا «ماشین A با کارگر ۲» را مشخص کنید. با این حال، این کار پیچیدگی مسئله را افزایش میدهد؛ اطمینان حاصل کنید که نرمافزار زمانبندی شما از محدودیتهای چند منبعی پشتیبانی میکند.
روشهای مرتبط
منابع
Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems (5th ed.). Cham: Springer.
باز کردن مرجع DOIکپی شد.Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.
باز کردن مرجع DOIکپی شد.