۵-۵- جمع­بندی و نتیجه ­گیری

در این فصل به مروری بر بهینه­سازی چندهدفه با کمک الگوریتم حرکت جمعی ذرات پرداخته شد و یکی از مهم­ترین و پایه­ای­ترین روش­ها در این زمینه با عنوان MOPSO معرفی گردید. سپس تعمیمی از این روش مطرح گردید که براساس آن انتخاب راهنمای سراسری یا راهنمای بخش اجتماعی حرکت ذرات، بر پایه محاسبه چگالی هسته برای هر راه­حل یافت شده تا کنون و انتخاب راهنما از بین ذراتی که دارای کمترین چگالی هسته هستند، صورت می­پذیرد. این روش، DbMOPSO نام­گذاری شده است. با بهره گرفتن از تعدادی تابع تست که توسط محققین مختلف برای سنجش کارکرد الگوریتم­های بهینه­سازی تکاملی پیشنهاد شده ­اند، نتایج الگوریتم جدید مطرح شده با نتایج الگوریتم MOPSO و همچنین روش­های PAES و NSGA II مقایسه گردید.

با دقت در نتایج شبیه­سازی معلوم می­ شود که الگوریتم­های مبتنی بر حرکت ذرات (چه روش MOPSO و چه روش DbMOPSO) هم از نظر تعداد راه­حل­هایی که ارائه می­ دهند و هم از نظر دقت راه­ حل­های یافت شده از PAES و NSGA II بسیار بهتر عمل می­ کنند. باید توجه کرد که تعداد راه حل­های یافت شده بهینه نیز می ­تواند بعنوان یک معیار عملکرد مورد بررسی قرار بگیرد. بین روش­های MOPSO و DbMOPSO تفاوت­ها چندان فاحش نیستند. در عین حال، نتایج شبیه­سازی نشان می­دهد که روش DbMOPSO در انتخاب راه­حل­ها دقیق­تر عمل می­ کند و در ضمن دقت بالاتر، تعداد راه­ حل­های بیشتری را نیز برمی­گرداند. در واقع ضعف عمده روش DbMOPSO در مقابل MOPSO، زمان اجرای طولانی­تر است که به واسطه عملگر محاسبه چگالی هسته، به الگوریتم تحمیل می­ شود.

فصل ۶

کاربرد DbMOPSO در
برنامه­ ریزی و زمانبندی کار کارگاهی منعطف

Flexible Job Shop
Planning and Scheduling Using DbMOPSO

۶-۱- مقدمه

برنامه­ ریزی و زمانبندی کارگاهی زیر مجموعه ­ای از برنامه­ ریزی و زمانبندی تولید است که یکی از پیچیده­ترین مسائل در بهینه­سازی ترکیبیاتی است. برای هر کار، روتینگ ثابت و از پیش تعیین شده­ای وجود دارد. هر ماشین بطور پیوسته آماده انجام کار است و هر ماشین در هر زمان فقط قادر به انجام یک کار است. تمام ماشین­ها از لحظه صفر آماده انجام کار هستند. در حالت عمومی مسئله زمابندی کارگاهی یک مسئله شدیداٌ NP-hard است [۲۳]. در زمانبندی کار کارگاهی منعطف زمانبندی شکل پیچیده­تری بخود می­گیرد چراکه در اینجا علاوه بر تعیین زمان­های شروع در عملیات روی ماشین، باید زیرمسئله تخصیص انجام هر عملیات به ماشین نیز حل شود [۲۳]. در این بخش با بهره گرفتن از الگوریتمی که در فصل قبل ارائه شد، سعی می­ شود روشی ارائه داده شود که زیر مسئله تخصیص وظایف و زمانبندی عملیات را در مسئله زمانبندی کار کارگاهی منعطف بطور یکجا حل کند. در ادامه این بخش ابتدا به طراحی و انتخاب فضای جستجوی مسئله پرداخته می­ شود که یکی از مهم­ترین بخش­های حل مسائل بهینه­سازی را تشکیل می­دهد و فضای جستجوی جدیدی معرفی می­ شود که مهم­ترین و جذاب­ترین خصوصیت آن این است که تمام این فضای جستجو صرف نظر از محدودیت­ها و قیود مسئله، شدنی^[۹۵] هستند. در قسمت بعدی روش کدبرداری و کدگذاری فضای جستجو شرح داده می­ شود. در قسمت دوم، مسائلی را که برای مقایسه نتایج شبیه­سازی استفاده شده است معرفی شده و در نهایت در قسمت سوم نتایج بکارگیری الگوریتم DbMOPSO برای حل مسئله برنامه­ ریزی و زمانبندی کار کارگاهی منعطف آورده شده است. در قسمت پنجم نتایج بدست آمده را با نتایج ارائه شده در یکی از مهمترین مقالات در این زمینه مقایسه می­کنیم.

۶-۲- فضای جستجو

فضای جستجو در اینجا براساس اولویت هر عملیات بر دیگری یا هر ماشین بر دیگری در اجرای عملیات تعریف می­ شود. به این معنی که برای یک عملیات که می ­تواند روی تعدادی ماشین اجرا شود، ماشینی برای اجرای آن انتخاب می­ شود که دارای اولویت بیشتری باشد و برای چند عملیات که می­توانند در یک زمان روی یک ماشین شروع شوند، عملیاتی برای اجرا انتخاب می­ شود که دارای اولویت بیشتری باشد.
فضای مسئله را بصورت مجموعه ای از ۴-تایی ها بصورت تعریف می­کنیم که در آن نشان دهنده کار، نشان دهنده عملیات، نشان دهنده ماشین و نشان دهنده زمان اجرای عملیات روی ماشین است. اگر تعداد اعضای مجموعه را با نشان دهیم، آنگاه فضای جواب مسئله را بصورت تعریف می­کنیم که در آن هر بعد فضا نماینده عدد اولویت اجرای چهارتایی متناظر آن در فضای مسئله خواهد بود. نگاشتی که یک عضو از فضای مسئله را به یک نقطه از فضای جواب می­نگارد، با نمایش داده می­ شود و بدیهی است که .
بعنوان مثال برای مسئله­ای با ۵ کار که هر کدام دارای ۴ عملیات هستند و هر عملیات میتواند روی یکی از ۳ ماشین موجود اجرا شود، فضای جواب مسئله خواهد بود. در این مثال اگر داشته باشیم
در اینصورت برای عملیات ۱ از کار ۱، ماشین ۲ انتخاب میشود چراکه دارای اولویت بالاتری است و همچنین اگر داشته باشیم
در اینصورت عملیات ۱ از کار ۲ در لحظه جاری برای شروع اجرا روی ماشین ۲ انتخاب می­ شود.
با توجه به توضیح بالا الگوریتم بدست آوردن برنامه زمانی اجرای عملیات از یک نقطه از فضای جواب براساس دو قاعده ساده زیر نوشته می­ شود:
به ازای یک عملیات از یک کار که روی چند ماشین قابل اجرا است، ماشینی انتخاب می­ شود که عدد اولویت آن در فضای جواب بیشتر است. (تخصیص ماشین به عملیات)
به ازای چند عملیات که روی یک ماشین در یک زمان قابل اجرا هستند، عملیاتی انتخاب می­ شود که دارای عدد اولویت بیشتری در فضای جواب باشد (زمانبندی اجرای عملیات)
فضای جستجوی معرفی شده در اینجا دارای خصوصیات جالبی است که عبارتند از:
فضای جواب پیوسته و همبند است.
تمام نقاط این فضا، شدنی هستند بنابراین شرایط مربوط به اعمال محدودیت­ها و شرایط مسئله برای تضمین شدنی بودن جواب که عمدتاً در روش­های بهینه­سازی بعنوان بخشی از الگوریتم حل مطرح است در اینجا وجود نخواهد داشت.
هر نقطه از این فضا راه حلی برای هر دو مسئله تخصیص عملیات به ماشین­ها و زمانبندی اجرای عملیات بطور یکجا ارائه می­دهد.

۶-۳- مسائل مورد بررسی

مسائل مورد بررسی در این بخش تماماٌ از کارهای کاسم^[۹۶] و همکارانش استخراج شده ­اند. در اینجا شش مسئله ای که او و همکارانش در [۲۴] به آنها پرداخته­اند، آورده شده و در بخش­های بعدی نتایج تحقیقات او با نتایج بدست آمده در این تحقیق مقایسه گشته­اند. در جداول زیر زمان­های اجرای عملیات براساس کار-عملیات-ماشین مشخص شده ­اند. توابع هدف در تمام این مسائل عبارتند از آخرین زمان خاتمه کارها^[۹۷]()، ماکزیمم بارکاری ماشین ها^[۹۸]() و مجموع بارکاری ماشین ها^[۹۹]().
جدول ۶-۱: زمان های اجرای عملیات مربوط به نمونه مسئله ۱