فایل *75- فایل

Performing additional custom work Point of delivery customization 5. Additional custom work
Providing additional services Customized services; providing quick response 4. Additional services
Customizing packaging Segmented standardization Cosmetic 3. Package and distribution
Embedded customization Adaptive 2. Usage
Pure standardization 1. Standardization
جدول 2-1 : سطوح سفارشی سازی عام [5]
در سطح سوم سفارشی‌سازی از طریق توزیع یا بسته‌بندی محصولات استانداردسازی شده به شکل‌ها، سایزها و روش‌های مختلف بدست می‌آید.
در سطح دوم سفارشی‌سازی پس از ارائه محصول صورت می‌گیرد. بدین صورت که محصول می‌تواند برای انجام عملیات یا وضعیت‌های مختلف تطابق یابد.
و بالاخره در سطح اول استانداردسازی بطور کامل انجام می‌شود و سفارشی‌سازی در آن وجود ندارد همچنانکه اغلب تولیدکنندگان امروزی بدین گونه عمل می‌کنند.
2-3- توانمندی‌های مورد نیاز برای اجرای سفارشی‌سازی در تولید انبوهدر این بخش توانمندسازان یعنی متدولوژی‌ها و تکنولوژی‌هایی که در پیاده‌سازی سیستم‌های سفارشی‌سازی در تولید انبوه استفاده می‌شوند بنابر آنچه در ادبیات موضوع آمده است، معرفی می‌شوند. این توانمندسازان را در دو دسته بصورت زیر معرفی می‌کنیم:
2-3-1- فرآیندها و متدولوژی‌ها
بررسی ادبیات موضوعی در پیاده‌سازی سیستم‌های سفارشی‌سازی در تولید انبوه، ما را به این نتیجه می‌رساند که حداقل چهار مفهوم زیر در پیاده‌سازی آن مورد توجه اساسی قرار گرفتهاند. این چهار مفهوم عبارتند از:
تولید چابکتولید چابک در دو حوزه مورد توجه قرار گرفته شده است: چابکی درونی که به معنی توانایی پاسخ سریع به بازار یا مشتریان برای محصولات جدید یا ویژگی‌های جدید در محصولات جاری می‌باشد. این توانایی نیازمند سیستم تولید قابل برنامه‌ریزی مجدد، قابل پیکربندی مجدد و با قابلیت انجام تغییرات پیوسته و در عین حال مقرون به صرفه بودن و تولید با اندازه بهرهای کوچک محصول است. چابکی بیرونی وابسته به مفهوم سازمان‌های مجازی است. سازمان‌های مجازی مجموعه‌ای از چندین شرکت هستند که برای تولید محصولات با کیفیت بالا و سفارشی‌شده با یکدیگر همکاری می‌کنند.
مدیریت زنجیره تأمینمدیریت زنجیره تأمین در واقع مدیریت هماهنگی بین منابع و بهینه‌سازی فعالیت‌ها در زنجیره ارزش، برای دست‌یابی به مزیت رقابتی است. کارامدی مدیریت زنجیره تأمین یکی از فاکتورهای بسیار اساسی در موفقیت سیستم‌های سفارشی‌سازی در تولید انبوه به شمار می‌رود.
طراحی و تولید مبتنی بر مشتریبا توضیحاتی که تا کنون آورده شده، روشن است که تولید مبتنی بر نیاز مشتری در واقع هسته اصلی سفارشی‌سازی در تولید انبوه است. مثلاً تولید مبتنی بر نیاز مشتری می‌تواند از طریق فراهمسازی شرایطی برای مشتری برای شروع کردن فرآیند طراحی یک محصول بدست آید.
Lean Manufacturingسیستم‌های سفارشی‌سازی در تولید انبوه چهار مؤلفه اساسی از Lean Manufacturing را مورد توجه قرار می‌دهند که عبارتند از: توسعه محصول، زنجیره تأمین، مدیریت صحن کارخانه و خدمات پس از فروش. برای پیاده‌سازی موفق سفارشی‌سازی در تولید انبوه توجه به موارد زیر ضروری است. الف) تعریف ارزش بر پایه مشتری، ب) تمرکز بر فعالیت‌های ارزش آفرین و پرهیز از اسراف و اتلاف منابع و پ) سازماندهی فعالیت‌های ارزش آفرین در فرآیندها.
2-3-2- تکنولوژی‌های پشتیبان
تکنولوژی‌های بسیاری در پیادهسازی موفق سیستم‌های سفارشیسازی در تولید انبوه نقش دارند که از آن جمله می‌توان به CNC، سیستم‌های تولید منعطف (FMS)، تکنولوژی‌های شبکه و مخابرات، طراحی به کمک کامپیوتر (CAD)، تولید به کمک کامپیوتر (CAM)، تولید یکپارچه کامپیوتری (CIM) و تبادل داده‌های الکترونیکی (EDI) همچنین استفاده از ماشین‌های پیشرفته قابل کنترل با کامپیوتر، ربات‌ها و سیستم های ترکیبی CAD/CAE اشاره کرد. این تکنولوژی‌ها خصوصیات انعطاف‌پذیری و چابکی را به سیستم خواهند داد.
تکنولوژی اطلاعات نیز برای فراهم کردن و ایجاد ارتباط بین گروه‌های کاری در سیستم تولید مانند گروه‌های طراحی، تحلیل، تولید، تست و غیره بطور وسیع و گسترده‌ای مورد استفاده قرار می‌گیرد. استفاده از تکنولوژی‌های پیشرفته اطلاعات مانند حرکت از CIM به سمت شبکه‌های هوشمند مبتنی بر کامپیوتر در سال‌های اخیر به شدت مورد توجه قرار گرفته‌اند.
2-5- جمعبندی و نتیجهگیریدر این فصل بطور خلاصه به مفهوم و ویژگیهای سیستمهای سفارشیسازی در تولید انبوه پرداخته شد و خصوصیات چنین سیستمهای تولیدی، به اختصار بیان گردیدند. سطوح مختلف سفارشیسازی از دید محقیق مختلف معرفی شد و توانمندیهای مورد نیاز برای پیادهسازی یک سیستم تولیدی به روش سفارشیسازی در تولید انبوه برشمرده شدند. در بخش چهارم به فرایندها و متدولوژیهای مورد استفاده در سفارشیسازی انبوه اشاره گردید و بخش پنجم به تکنولوژیهای پشتیبان در این سیستمها اختصاص یافت.
با توجه به مطالب مطرح شده، میتوان دریافت که مهمترین و پایهایترین ویژگی سیستمهای تولیدی سفارشیسازی انبوه، انعطافپذیری سیستم تولیدی برای تهیه محصولاتی با تنوع بالا در ویژگیهای آن است. بنابراین در ادامه این تحقیق، صورت مسئله مورد تحقیق که برنامهریزی سیستم تولیدی برای حصول به سفارشیسازی در تولید انبوه است، به زیر مسئله برنامهریزی و زمانبندی کار کارگاهی منعطف در حالت چندهدفه، شکسته شده و به روشهای حل آن پرداخته خواهد شد. در فصل آینده به مفهوم زمانبندی کارگاهی، پرداخته و مدل ریاضی مناسب برای مسئله برنامهریزی و زمانبندی کار کارگاهی منعطف ارائه خواهد گردید.
فصل 3برنامهریزی و زمانبندیPlanning and Scheduling

3-1- مقدمهبرنامهریزی فرایند و زمانبندی تولید دو چالش عمده در سیستمهای تولیدی هستند. آنها مشخص میکنند که چگونه و چهزمانی، کدام محصولات با منابع موجود تولید شوند. بطور سنتی، برنامهریزی فرایند و زمانبندی تولید بعنوان دو فعالیت مجزا از هم انجام میپذیرند و معمولاً توسط دپارتمانهای جداگانه در سازمان تولیدی انجام میشوند که این مسئله شکاف زمانی و اطلاعاتی بزرگی را در آنها ایجاد میکند. در شیوه سفارشیسازی در تولید انبوه، این مسئله شکل پیچیدهتری بهخود میگیرد چرا که در این شیوه بدلیل تنوع کالاهای سفارش، انعطافپذیری خطوط تولید نیازمند مدلهای بسیار دقیق و پیچیدهای از سیستم است.
برنامهریزی فرایند مشخص میکند که تولید محصولات در جهت حصول به حداکثر کارایی سیستم تولیدی با استفاده از منابع موجود چگونه انجام شود و زمانبندی تولید تعیین کننده زمان شروع تولید هر محصول و تعیین منابع مشخص تولید است تا محصول در زودترین زمان و با کمترین هزینه ممکن بر اساس سفارش مشتری تولید شود. به بیان دیگر این دو عملکرد مشخص کننده زمان تولید و هزینه فرایند تولید موردنیاز برای محصولات مورد سفارش مشتری هستند.
با افزایش رقابت تولیدکنندگان در بازار، در نظر گرفتن نیازهای هر مشتری بطور خاص، تبدیل به یکی از مهمترین فاکتورهای برتری تولیدکنندگان در مقابل یکدیگر شده است. بر این اساس سفارشیسازی در تولید انبوه بعنوان روشی که نیازهای هر مشتری را بطور خاص در تولید محصول مورد توجه قرار داده و در عین حال محصولات را با هزینهای نزدیک به تولید انبوه تولید میکند، هر روز جایگاه مهمتری در میان محققین و صنایع پیدا میکند.
در ادامه این فصل توجه خود را به مدلسازی مسئله زمانبندی کار کارگاهی منعطف که مسئله اصلی تحقیق حاضر را تشکیل میدهد، معطوف میکنیم.
3-2- مدلسازی سیستم تولید در برنامهریزی و زمانبندیبهتر است در ابتدا یک محیط تولیدی عمومی را فرض کنیم و سپس نقش برنامهریزی و زمانبندی را در آن توصیف نماییم. سفارشاتی که به یک سیستم تولیدی ارائه میشوند باید به کارهایی با زمانهای سررسید معین تبدیل شوند. هرکدام از این کارها باید در یک مرکزکاری مشخص روی تعدادی ماشین با ترتیب یا توالی از پیش طراحی شدهای اجرا شوند. از آنجایی که هرکدام از ماشینها ممکن است در مقاطع زمانی خاصی درگیر انجام کار باشند، اجرای هرکدام از کارها ممکن است بعلت مشغول بودن ماشینهای مربوطه با تأخیر مواجه شود. رویدادهای ناخواستهای در کارگاه مانند خرابی ماشین(ها)، زمانهای کار طولانیتر از انتظار و غیره میتوانند برنامه زمانبندی اجرای کارها را با مشکل مواجه کنند. در چنین محیطهایی تهیه یک برنامه زمانی دقیق و کامل میتواند به کارایی و کنترل بهتر عملیات کمک کند.
کارگاه تنها قسمتی از سازمان که تحت تأثیر فرایند زمانبندی قرار دارد نیست. فرایند زمانبندی همچنین با فرایند برنامهریزی تولید – که برنامههای میان مدت و دراز مدت تولید را برای سازمان مشخص میکنند – در ارتباط تنگاتنگ است. تصمیمگیریهایی که دراین سطح از سازمان گرفته میشود ممکن است بر برنامههای زمانبندی کارگاهی نیز مستقیماً تأثیر گذار باشند. شکل 3-1 نمودار جریان اطلاعات را در یک سیستم تولیدی نوعی نمایش میدهد [9].
سیستم زمانبندی تولید دارای سه نوع ورودی است. سفارش مشتری (یا محصولاتی که باید تولید شوند)، برنامه تولید (هرکدام از عملیات مورد نیاز برای تولید هر محصول باید روی چه منبع یا منابعی اجرا شوند)، وضعیت منابع با توجه به محدودیتها و قیود کارگاه. سفارش مشتری دارای خصوصیات نوع محصول، تعداد یا مقدار و زمان تحویل میباشد. برنامه تولید باید مشخص کننده روتینگ تولید محصول و تخمین زمان یا هزینه استاندارد تولید هر عملیات در روتینگ بر روی منبع مقتضی است. خروجی سیستم زمانبندی تولید، ترتیب زمانی اجرای عملیات برای تولید محصول یا محصولات نهایی در قالب گانت چارت است که در آن دقیقاً مشخص شده که هر کدام از عملیات بر روی کدام یک از منابع و با چه زمانهای آغاز و پایانی اجرا میشوند.
در تولید، سیستمهای برنامهریزی و زمانبندی باید با فرایندهای دیگر تصمیمگیری سازمان در تعامل باشند. یک فرایند بسیار عمومی در این زمینه برنامهریزی مواد (MRP) است. هنگامی که زمانبندی عملیات در حال برنامهریزی است، مهم است که تمام مواد خام و منابع مورد نیاز در زمان مقتضی فراهم باشند. زمانهای برنامهریزی شده اجرای کار باید توسط سیستم برنامهریزی و زمانبندی و با هماهنگی سیستم MRP بدست آیند.
سیستمهای MRP بطور معمول دارای جزئیات نسبتاً کمی از برنامه اجرای کارها هستند. هر کار، دارای یک ساختار مواد (BOM) است که قطعات و مواد مورد نیاز برای انجام عملیات تولید را مشخص میسازد. سیستم MRP انبار مربوط به هرکدام از قطعات یا مواد را زیرنظر دارد. بعلاوه زمان سفارش هرکدام از قطات را نیز معین میکند. در سازمانهایی که هیچ سیستم برنامهریزی و زمانبندی وجود ندارد، عمدتاً به برنامه MRP بسنده میشود. بدیهی است که یک سیستم تولیدی پیچیده نمیتواند به برنامه حاصل از MRP بسنده کند. در چنین سازمانهایی، وجود یک سیستم برنامهریزی وزمانبندی عملیات، ضروری است.
امروزه کارخانجات تولیدی مدرن از سیستمهای اطلاعات تولید که شامل شبکهای از کامپیوترهای بهم پیوسته و پایگاههای داده مختلف است استفاده میکنند. کامپیوترهای محلی،
51781423751شکل 3-1: نمودار جریان اطلاعات در یک سیستم تولیدی [9]
ایستگاههای کاری و ترمینالهای ورود اطلاعات به سرورهای مرکزی یا پایگاههای داده مرتبط هستند و از دادههای ثبت شده استفاده یا دادههای جدید را ثبت میکنند. برنامهریزی و زمابندی هم توسط یکی از کامپیوترهای مستقر در این شبکه انجام میگردد. هرکدام از ترمینالهای شبکه میتوانند از اطلاعات برنامهریزی و زمابندی استفاده کنند و همچنین نقش اساسی در ثبت رویدادهای کارگاه مانند تغییرات در وضعیت ماشینها، کارها و انبار ایفا کنند.
در سیستمهای امروزیتر، کلیه فرایندها و جریانهای اطلاعات سازمان در یک سیستم یکپارچه اطلاعاتی تحت عنوان Enterprise Resource Planning Sys-- مجتمع شده و امکانات وسیعی در کنترل، تصمیمگیری و ارزیابی فرایندها، از بالاترین سطوح سازمان و زیرمجموعههای آن و حتی تأمینکنندگان و مشتریان تا جزئیترین سطوح فعالیت در سازمان را در اختیار قرار میدهند.
3-3- کارها، ماشینها و کارگاههادر این بخش تعاریف پایهای و نمادهای استفاده شده در مدلسازی مسئله برنامهریزی و زمانبندی شرح داده شده است. در تمام این پایاننامه تعداد کارها با n و تعداد ماشینها با m نمایش داده شده است. زیرنویسهای k و j برای نشان دادن اندیس کار و زیرنویسهای h و i برای نشان دادن اندیس ماشین استفاده شدهاند.
زمان کار (pij): زمان کار pij نشان دهنده مدت زمانی است که انجام کار j روی ماشین i بطول میانجامد. درصورتیکه زمان کار به ماشین وابسته نباشد از زیر نویس i صرفنظر کرده و آن را با pj نمایش میدهیم. نرخ تولید یک ماشین برهمین اساس بصورت Qj=1pj تعریف میشود که بیانگر تعداد دفعات انجام کار در واحد زمان است.
زمان ورود (rj): زمان ورود rj کار j زمانی است که کار به سیستم وارد میشود؛ یعنی زودترین زمانی که کار j میتواند آغاز شود را زمان ورود آن کار مینامند.
زمان تحویل (dj): زمان تحویل dj زمانی است که نتیجه انجام کار باید به مشتری تحویل داده شود یا به بیان دیگر زمانی است که انجام کار در آن باید خاتمه یافته باشد. زمان خاتمه انجام کار میتواند دیرتر از زمان تحویل آن باشد اما باعث ایجاد جریمه میشود. درصورتیکه زمان تحویل بطور قطع باید رعایت شود، به این زمان، مهلت گفته میشود.
وزن کار (wj): وزن یک کار در واقع یک ضریب اولویت برای آن کار است که بیانگر اهمیت اجرای آن کار در مقایسه با کارهای دیگر در سیستم است.
چهار مشخصهای که در بالا ذکر شدند، اطلاعات ایستا بودند چراکه به زمانبندی انجام شده وابسته نیستند. در مقابل این مشخصات، اطلاعاتی که ثابت نبوده و به زمانبندی وابسته هستند اطلاعات پویا نام دارند. در ادامه به چند مورد از مهمترین اطلاعات پویا میپردازیم.
زمان شروع (Sij): زمان شروع Sij ، زمان آغاز اجرای کار j روی ماشین i است و در صورتیکه زیرنویس i در آن نیامده باشد، به معنی زمان شروع اولین عملیات مربوط به کار j در سیستم است.
زمان تکمیل (Cij): زمان تکمیل Cij ، زمان خاتمه اجرای کار j روی ماشین i است و درصورتیکه زیرنویس i در آن نیامده باشد، به معنی زمان تکمیل آخرین عملیات مربوط به کار j در سیستم است.
یکی از مشخصههای مهم در مدل زمانبندی، جانمایی ماشینها در سیستم است. چندین جانمای مهم در طراحی کارگاه برای ماشینها وجود دارد که در ادامه به آنها اشاره میشود.
مدل تک ماشین: بسیاری از سیستمهای تولید میتوانند بعنوان یک مدل تک ماشین درنظر گرفته شوند. بعنوان مثال اگر در یک سیستم چند ماشین، یک ماشین بعنوان گلوگاه سیستم مطرح باشد، تنها همان ماشین تعیین کننده عملکرد سیستم زمانبندی در سیستم خواهد بود. در چنین شرایطی منطقی است که ابتدا ماشین گلوگاه سیستم در مرحله اول برنامهریزی و زمانبندی شده و ماشینهای دیگر به طبع آن در مراحل بعدی قرار بگیرند. این راه حل ایجاب میکند که در مرحله اول مسئله برنامهریزی و زمانبندی به یک مدل تک ماشین تقلیل پیدا کند. مدل تک ماشین همچنین در سیستمهایی که دارای پیچیدگی بسیار زیاد هستند کاربرد دارد. در این سیستمها معمولاً سعی میشود که مسئله بزرگ مورد مطالعه به چندین مسئله تقلیل یافته کوچکتر (مانند مسئله زمانبندی مدل تک ماشین) شکسته شده و سپس حل شود.
مدل ماشینهای موازی: یکی از تعمیمهای مدل تک ماشین بصورت مجموعهای از ماشینهاست که بصورت موازی در کنار هم کار میکنند. تعداد زیادی از سیستمهای تولیدی از تعدادی مراکز کاری تشکیل شدهاند که هر کدام از آنها شامل تعدادی ماشین موازی هستند. در اغلب موارد ماشینهای موجود در یک مرکز کاری مشابه هستند، و بدین ترتیب یک کار که به مرکز کاری وارد شده است میتواند روی هرکدام از آن ماشینها اجرا شود. دلایلی که در اهمیت توجه به مدل تک ماشین مطرح شدند میتوانند درمدل ماشینهای موازی هم مطرح باشند. مثلاً اگر در یک سیستم با چندین مرکز کاری، یکی از مراکز گلوگاه اجرای فرایندهای سیستم باشد، میتوان آن را بعنوان یک مرکز کاری با ماشینهای موازی فرض کرده و برنامهریزی و زمانبندی را ابتدا برای آن و سپس برای باقی مراکز کاری انجام داد.
باید به این نکته توجه داشت در مدل ماشینهای موازی لزوماً همواره تمام ماشینها مشابه نیستند مثلاً برخی ماشینهای مجموعه ممکن است قدیمیتر باشند و درنتیجه سرعت یا کیفیت اجرای کارها روی این ماشینها کمتر از سرعت یا کیفیت اجرای همان کارها روی ماشینهای دیگر از همان نوع باشد.
مدل جریان کارگاهی : در بسیاری از سیستمهای تولیدی، خصوصاً تولید کنندگان محصولات مونتاژی، اجرای هر کار مستلزم انجام تعدادی عملیات پشت سر هم روی تعدادی ماشین است. درصورتی که روتینگ همه کارها یکسان باشند یعنی همه کارها برای اجراشدن به ترتیب یکسان از ماشینهای یکسانی عبور کنند، به آن جریان کارگاهی گفته میشود. در چنین سیستمی، ماشینها بصورت سری قرار داشته و با هم راهاندازی میشوند. هر کار پس از اجرا شدن روی یک ماشین به صف انتظار اجرای ماشین بعدی منتقل میشود. یک تعمیم از مدل جریان کارگاهی، مدل جریان کارگاهی منعطف است. جریان کارگاهی منعطف دارای تعدادی مراحل مختلف است که هر کدام از مراحل شامل تعدادی ماشین موازی هستند و در مجموع شیوه ارتباط مراحل مختلف بصورت یک جریان کارگاهی است. در هرکدام از مراحل، این انعطاف وجود دارد که کار رسیده بتواند روی هرکدام از ماشینهای آن مرحله اجرا شود.
مدل کار کارگاهی: در برخی کارگاهها، کارهای رسیده دارای روتینگهای متفاوتی هستند. در نتیجه هر کار برای اجرا شدن باید از ماشینهای مشخصی که در روتینگ آن معین است عبور کند. چنین مدلی را مدل کار کارگاهی نامیده اند. در واقع مدل جریان کارگاهی حالت خاصی از مدل کار کارگاهی است که در آن تمام کارها دارای روتینگ یکسان هستند. یک تعمیم از مدل کار کارگاهی، مدل کار کارگاهی منعطف است. در این مدل، هر کار میتواند روی یک یا چند ماشین اجرا شود. بنابراین در مدل کار کارگاهی منعطف، پیش از زمانبندی اجرای عملیات باید معین شود هر کار روی کدام ماشین اجرا گردد.
مدل زنجیره تأمین: این مدل، یک مدل سطح بالا است که در آن یک محیط تولیدی به شبکهای از اجزای بهم مرتبط تقسیم میشود که هرکدام از این اجزا خود دارای یک مدل کار کارگاهی (منعطف) یا جریان کارگاهی (منعطف) هستند.
3-4- معیارهای کارایی در زمانبندی تولیددر عمل از معیارهای کارایی مختلفی برای برنامهریزی و زمانبندی در سیستمهای تولیدی استفاده میشود اما در واقع همگی این معیارهای کارایی ترکیبی از تعدای معیار پایه هستند. در ادامه به چند نمونه از معیارهای پایهای و معروف در بررسی عملکرد سیستمهای زمانبندی تولید اشاره میگردد.
معیارهای توان عملیاتی و Makespan: در بسیاری از سیستمهای تولیدی، افزایش میزان توان عملیاتی یکی از مهمترین معیارهایی کارایی برنامهریزی به شمار میرود تا جایی که در بسیاری از موارد عملکرد مدیران براساس میزان بهبود در این معیار اندازهگیری میشود. زمان throughput یک قطعه، مدت زمانی است که طول میکشد تا آن قطعه از سیستم عبور کند. توان عملیاتی یک سیستم تولیدی که برابر نرخ خروجی آن نیز است، بر اساس ظرفیت ماشینهای گلوگاهها (یعنی ماشینهای دارای کمترین ظرفیت) مشخص میشود. بنابراین بیشینه کردن میزان توان عملیاتی یک سیستم تولیدی معادل بیشینه کردن ظرفیت تولید ماشینهای گلوگاه سیستم است.
معیار Makespan زمانی مهم ارزیابی میشود که تعداد کارها محدود باشد. Makespan که با Cmax نشان داده میشود عبارت از زمانی است که آخرین کار خاتمه پیدا کند.
Cmax=max⁡(C1, C2, …,Cn)که در آن Cj زمان خاتمه کار j است. معیار Makespan شباهت زیادی به معیار توان عملیاتی دارد.
معیارهای وابسته به زمان تحویل: تعداد زیادی معیار کارایی وابسته به زمان تحویل کار وجود دارد که در ادامه به برخی از آنها اشاره شده است.
اغلب سیستمهای زمانبندی براین اساس ایجاد میشوند که دیرشدگی انجام کارها را به حداقل برسانند. دیرشدگی انجام یک کار بصورت زیر تعریف میشود:
Lj=Cj-dj که در آن dj زمان تحویل کار است. حداکثر دیرشدگی در یک سیستم بصورت زیر تعریف میشود:
Lmax=max⁡(L1,L2,…,Ln)کمینهسازی بیشینه دیرشدگی معادل کمینهسازی دیرشدگی مربوط به بدترین شرایط کارایی در سیستم زمانبندی است.
معیار کارایی دیگری که در این زمینه قابل توجه است، تعداد کارهای دیرکرد است. دیرکرد با رابطه زیر بدست میآید:
Tj=max⁡(Cj-dj, 0)مجموع دیرکرد کارها بعنوان یک معیار کارایی سیستم زمانبندی نیز بصورت i=1nTj تعریف میشود.
هزینههای برپایی: اغلب هنگامی که قصد داریم به بیشینهسازی توان عملیاتی یا کمینهسازی Makespan بپردازیم، باید به کمینه بودن هزینههای راهاندازی کارها نیز توجه لازم را داشته باشیم. باید توجه داشت که هزینههای راهاندازی لزوماً متناسب با زمانهای راهاندازی نیستند. بعنوان مثال هزینههای راهاندازی برای ماشینی که دارای ظرفیت بسیار زیادی است، قابل توجه نیست حتی اگر این راهاندازی شامل به هدر رفتن منابع یا زمان زیادی شود.
هزینههای انبارداری کالای درجریان ساخت: هدف مهم دیگر در یک سیستم زمانبندی کمینه کردن هزینههای نگهداری و انبارداری کالای در جریان ساخت (WIP) است. WIP باعث افزایش هزینههای نقل و انتقال میشود ضمن آنکه WIPهای قدیمیتر همواره در معرض آسیبهای ناشی از نقل و انتقال و نگهداری قرار دارند. معیار دیگری که میتواند بعنوان جایگزین WIP مورد استفاده قراربگیرد میانگین زمان throughput است. کمینهسازی میانگین توان عملیاتی، با وجود سطح خروجی ثابت، باعث کاهش WIP خواهد شد. همچنین کمینهسازی زمان throughput وابستگی نزدیکی به کمینهسازی مجموع زمانهای تکمیل کارها یعنی j=1nCj دارد. هدف شرح داده شده اخیر، معادل کمینهسازی میانگین تعداد کارهای سیستم نیز میباشد.
هزینههای انبارداری محصول نهایی: کمینهسازی هزینههای انبارداری محصولات تولید شده نیز یکی دیگر از اهداف مهم در سیستمهای زمانبندی محسوب میگردد. درصورتیکه سیستم تولیدی از نوع ساخت-براساس-سفارش باشد، آنگاه هزینههای انبارداری محصول معادل هزینههای تعجیل در تولید خواهند بود. در سیستمهای Just-In-Time معمولاً کمینهسازی مجموع تعجیل کارها بعنوان یک هدف مهم مطرح است. چرا که در یک سیستم JIT بدلیل اجتناب از هزینههای نگهداری و رسیدگی نباید کارها زودتر از موعد انجام شوند.
هزینههای انتقال: در سیستمهایی که شامل بخشهای تولیدی مجزا و دور از هم هستند، هزینههای انتقال کالاها بین مراکز کاری میتواند قسمت چشمگیری از هزینههای تولید باشد. از این روی کاهش هزینههای انتقال نیز میتواند از جمله اهداف مهم سیستمهای برنامهریزی و زمانبندی محسوب گردد.
3-5- مدلسازی ریاضی مسأله زمانبندی کار کارگاهی منعطفمسائل زمانبندی در تمام حوزههای علوم از مهندسی کامپیوتر گرفته تا اقتصاد وجود داشته و نقش مهمی دارند. اغلب مسائل زمانبندی، از نوع مسائل بهینهسازی ترکیبیاتی پیچیده هستند که حل آنها در حوزه زمان بوسیله الگوریتمهایی که دارای پیچیدگی زمانی چندجملهای هستند ناممکن است. در میان این مسائل، زمانبندی کار کارگاهی منعطف یکی از پیچیدهترین مسائل بهینهسازی ترکیبیاتی است.
زمانبندی کار کارگاهی منعطف یکی از مباحث مهم در مدیریت تولید و همچنین بهینهسازی ترکیبیاتی است. ثابت میشود که بدلیل پیچیدگیهای محاسباتی بسیار زیاد، غیرممکن است که بتوان جواب بهینه چنین مسألهای را در مقیاسهای عملی با روشهای متداول در بهینهسازی ترکیبیاتی بدست آورد. برای حل مسأله زمانبندی در محیط کارگاهی دو رویکرد وجود دارد: رویکرد سلسله مراتبی و رویکرد یکپارچه. در رویکرد سلسله مراتبی، تخصیص وظایف به ماشینها و توالی عملیات روی ماشینها بطور جداگانه بررسی و حل میشوند. در رویکرد یکپارچه، تخصیص وظایف و توالی عملیات توأمان مورد توجه و حل قرار میگیرند. از آنجایی که مسأله زمانبندی کار کارگاهی منعطف یک مسأله NP-hard است روش بکار گرفته شده در این پایاننامه یک روش مکاشفهای مبتنی بر همکاری تعدادی عاملهای واکنشی ساده و تکامل آنها در جهت جستجوی جواب(های) بهینه است.
در مسأله کلاسیک زمانبندی کارگاهی، اجرای تعداد n کار روی m ماشین مستقل زمانبندی میشود. برای هر کار مسیر اجرا، بطور کامل مشخص و معین است. همه ماشینها از لحظه صفر تا انتهای کارها آماده هستند و کارها بدون هیچگونه رقابتی برای در اختیار گرفتن ماشینها اجرا میشوند. مسأله عمومی زمانبندی کارگاهی یک مسأله شدیداً NP-hard است. امروزه انعطافپذیری ماشینها و خطوط تولید در صنایع نیازمند سیستمهایی برای برنامهریزی چنین شرایطی است. مسأله زمانبندی کار کارگاهی منعطف تعمیمی از مسأله زمانبندی کارگاهی عمومی که در بالا شرح داده شد است که در آن فرض میشود که به ازای هر عملیات، حداقل یک نوع ماشین برای اجرای آن در کارگاه وجود دارد. بنابراین زمانبندی کار کارگاهی منعطف علاوه بر مسأله زمانبندی شامل یک زیر مسأله تخصیص وظایف برای تخصیص هر کدام از عملیات به یکی از ماشینهایی که قابلیت اجرای آنرا دارند نیز میباشد. بنابراین مسأله زمانبندی کار کارگاهی منعطف دارای دو مشکل است: یکی تخصیص هرکدام از عملیات به ماشین مقتضی و دوم زمانبندی آنها در جهت حداقل سازی یک یا تعدادی از توابع هدف معین از پیش تعریف شده.
مدل ریاضی مسأله زمانبندی کار کارگاهی منعطف در این تحقیق بصورت زیر درنظر گرفته شده است. در این مدل m ماشین و n کار تعریف شده است. هر کار شامل تعدادی عملیات است که با Oj,h نمایش داده میشوند که در آن j اندیس کار مربوطه و h=1,2,…,hj اندیس عملیات مربوط به کار j ام است و hj تعداد عملیات مربوط به کار j ام میباشد. درنتیجه Oj,h نشان دهنده عملیات h ام از کار j ام است. بهمین ترتیب مجموعه ماشینها با M=M1,M2,…,Mm نمایش داده میشود. مجموعهای از ماشینهایی را که میتوانند عملیات Oj,h را انجام دهند را با Mj,h M نمایش میدهیم. مجموعه Mj,h توسط ماتریس A با اعضای زیر تعریف میشود.
ai,j,h=1, if Oj,h can be performed on machine i0, otherwise که در آن i=1,2,…,m اندیس ماشین، j=1,2,…,n اندیس کار و h=1,2,…,hj اندیس عملیات مربوط به کار j است. اجرای هر عملیات Oj,h روی ماشین Mi∈Mj,h به اندازه pi,j,h واحد زمانی بطول خواهد انجامید.
با توجه به تعاریف فوق ماتریسهای زیر را تعریف میکنیم:
yi,j,h=1, if machine i is selected for operation Oj,h0, otherwise xi,j,h,k=1, if Oj,h is performed on machine i in priority k0, otherwise زمان شروع کار ماشین i در اولویت k با Tmi,k نمایش داده میشود. تعداد عملیات تخصیص داده شده به ماشین i با ki نشان داده میشود.
با توجه به فرضیات و نمادگذاری بالا، محدودیتهای مسأله زمانبندی کار کارگاهی منعطف بصورت زیر بیان میشوند:
Cmax≥tj,hj+Psj,hj, for j=1,2,…,mکه در آن Cmax زمان اتمام آخرین عملیات از مجموعه عملیات همه کارهاست که makespan نامیده میشود. tj,h زمان شروع هر عملیات Oj,h بوده و Psj,h زمان انجام عملیات Oj,h روی ماشین انتخاب شده بعد از تخصیص عملیات است. و داریم؛
iyi,j,h.pi,j,h=Psj,h, for j=1,2,…,n; h=1,2,…,hjtj,h+Psj,h≤tj,h+1, for j=1,…,n;h=1,…,h-1Tmi,k+Psj,h.xi,j,h,k≤Tmi,k+1, for i=1,…,m;j=1,…,n;h=1,…,hj; k=1,…,ki-1yi,j,h≤ai,j,h, for i=1,…,m;j=1,…,n;h=1,…,hjiyi,j,h=1, for j=1,…,n;h=1,…,hjjhxi,j,h,k=1, for i=1,…,m;k=1,…,kikxi,j,h,k=yi,j,h, for i=1,…,n; j=1,…,n;h=1,…,hj3-6- پیشینه تحقیق در زمینه زمانبندی کار کارگاهی منعطفدر حالت کلی اغلب مسائل زمانبندی تولید از جهت پیچیدگی زمانی در ردیف مسائل NP-hard قرار دارند. بدین معنی که برنامهای با پیچیدگی زمانی چندجملهای برای حل این مسائل و یافتن راه حل بهینه برای این مسائل وجود ندارد. از این رو حل مسائل زمانبندی تولید همواره از موضوعات مورد توجه محققین بوده است. عمدهی روشهایی که در این زمینه تا کنون مورد بررسی قرار گرفتهاند، براساس ارائه روشهای مکاشفهای در جهت یافتن پاسخهای مناسبی که نزدیک به شرایط بهینه قطعی باشند متمرکز بوده است.
بر خلاف تحقیقات انجام شده روی مسأله زمانبندی کارگاهی، تحقیقاتی که تا کنون درباره مسأله زمانبندی کار کارگاهی منعطف انجام شده بسیار پراکنده و محدود است. اولین افرادی که بطور مشخص به مسأله زمانبندی کار کارگاهی منعطف پرداختند بروکر و شایل بودند [10] که الگوریتمی با پیچیدگی زمانی چندجملهای، برای مسأله زمانبندی کار کارگاهی منعطف با دو کار ارائه دادند. برای حل مسائل واقعیتر با بیش از دو کار، دو رویکرد به حل این مسأله در تحقیقات دنبال شده است. رویکرد اول رویکرد سلسله مراتبی است که در آن ابتدا زیر مسأله تخصیص کارها (وظایف) به ماشینها حل شده و سپس به حل مسأله زمانبندی پرداخته میشود. ایده اصلی در این رویکرد این است که تقسیم مسأله به دو زیرمسأله کوچکتر باعث کاهش پیچیدگی مسأله خواهد شد. براندیمارت اولین کسی بود که از این رویکرد در حل مسأله زمانبندی کار کارگاهی منعطف استفاده نمود. او در مقالهاش زیر مسأله تخصیص وظایف را با استفاده از روشهای کلاسیک قواعدتوزیع و زیرمسأله زمانبندی را باستفاده از روش جستجوی ممنوع حل کرده است.
رویکرد دوم در حل مسأله زمانبندی کار کارگاهی منعطف ارائه الگوریتمهایی است که دو زیر مسأله مذکور را توأمان حل میکنند. هورینک و همکارانش اولین کسانی بودند که از این رویکرد استفاده کردند [11]. آنها در مقالهشان از روش جستجوی ممنوع استفاده کردند که در آن تخصیص مجدد و توالی مجدد بعنوان عملگرهای حرکت در فضای جستجو انتخاب شدهاند.
در تحقیق دیگری، ماسترولیلی و گامباردلا [12] از توابع همسایگی بعنوان فرااکتشاف استفاده کردهاند. کاسم و همکارانش [13]، از الگوریتمهای ژنتیکی برای حل مسئله زمانبندی کار کارگاهی منعطف در حالت چندهدفه استفاده کردهاند.
اونگ و همکارانش از روشی مبتنی بر کارکرد سیستم مصونیت در انسانها برای حل مسئله کار کارگاهی منعطف با درنظرگرفتن دوباره کاری استفاده کردهاند.
زا و همکارانش [14] با ترکیب فرااکتشافات حرکت دسته جمعی ذرات و گداخت شبیهسازی شده، روش ترکیبیای برای حل این مسئله در حالت چند هدفه ارائه کردند.
در این پایاننامه الگوریتمی ارائه خواهد شد که زیر مسئلههای تخصیص عملیات و تعیین ترتیب اجرای آنها را همزمان انجام میدهد و نتایج شبیهسازیها با روش کاسم و همکارانش مقایسه خواهد گردید.
3-7- جمعبندی و نتیجهگیریدر ابتدای این فصل مروری بر مفاهیم برنامهریزی و زمانبندی تولید آورده شد. سپس تعاریف کار، ماشین، کارگاه و انواع آنها مطرح گردیده و برخی از معیارهای پایه در برنامهریزی و زمانبندی تولید معرفی شدند. سپس با استفاده از مفاهیم و تعاریف مطرح شده، یک مدل ریاضی برای مسئله زمانبندی کار کارگاهی منعطف ارائه گردید. در نهایت، پیشینهای از تحقیقات انجام شده در زمینه زمانیندی کار کارگاهی منعطف آورده شد.
مطالب مطرح شده در این فصل صورتبندی کاملی از مسئلهای که در این تحقیق قصد داریم مورد بررسی و کنکاش قراردهیم بدست میدهد. در فصلهای پنجم و ششم سعی میشود مسئله زمانبندی کار کارگاهی منعطف که در اینجا مطرح شده، در حالت چندهدفه حل شود.

فصل 5بهینهسازی چندهدفه با حرکت جمعی ذراتMulti-Objective Particle Swarm Optimization

5-1- مقدمهدر اغلب مسائل واقعی در بهینهسازی، ما با چند هدف روبرو هستیم که گاهاً بایکدیگر در تعارض نیز میباشند. در سالهای اخیر علاقمندی رو به گسترشی در زمینه بهینهسازی چند هدفه با استفاده از فرااکتشافهای تکاملی بوجود آمده است. این روشها از ترکیب دو حوزه مختلف بهره میبرند. یکی حوزه فرااکتشافات مبتنی بر جمعیت، و دیگری حوزه تئوریهای تصمیمگیری چند معیاره.
با اینکه در برخی از موارد، مسائل واقعی میتوانند به یک یا چند مسئله تک هدفه تقلیل یابند، اما در بسیاری از موارد انتخاب یک هدف بهگونهای که همه جنبههای چند هدف را دربر بگیرد بسیار سخت یا غیر ممکن مینماید. در چنین مواردی مجبور هستیم از تکنیکهای ویژهای برای حل مسئله بصورت چند هدفه استفاده کنیم. بهینهسازی چند هدفه نزدیک به بیست سال است که مورد توجه محققین قرار گرفته و بطور مداوم در مسائل کاربردی بیشتری مورد استفاده قرار میگیرد. با وجود این، برخلاف روشهای زیادی که برای حل مسائل تک هدفه وجود دارد، هنوز تعداد بسیار کمی روش برای حل مسائل چند هدفه معرفی شده است.
در مسائل بهینهسازی تک هدفه، عموماً فضای جستجوی جواب خوش تعریف است. به محض اینکه مجبور باشیم چند هدف (احتمالاً متناقض هم) را با هم برآورده سازیم، دیگر یک جواب بهینه نخواهیم داشت بلکه با مجموعهای از جواب ها با کیفیت یکسان روبرو خواهیم بود. در واقع جواب یک مسئله بهینهسازی با چند هدف، مجموعهای از t--e off های بهینه بین این اهداف متناقض است.

شکل 5-1: مفهوم راه حل بهینه پارتو
یک مسئله بهینهسازی چند هدفه را میتوان به فرم minimizef1x,f2x,…,fkx که در آن fi:Rn→R ، برای حداقل سازی k هدف براساس تعدادی تساوی و نامساویهای تعیین کننده محدودیتهای مسئله بیان کرد. برای بردار متغیرهای تصمیم گیری x=[x1, x2, …,xn]، هدف از حل مسئله فوق پیدا کردن مجموعه F از مقادیر متغیرهای تصمیمگیری است که علاوه بر ارضای محدودیتهای مسئله، مقادیر همه fi ها را نیز حداقل کنند.
همانطور که در شکل 5-1 نشان داده شده است، یک جواب نسبت به یک جواب دیگر، براساس مقادیر توابع هدف مسئله، میتواند بهتر، بدتر یا بیتفاوت باشد. در اینجا بهترین جواب یعنی جوابی که در هیچکدام از توابع هدف، بدتر از نقاط فضای جستجوی جواب نباشد و حداقل در یکی از توابع هدف بهتر از نقاط فضای جواب باشد. به زبان ریاضی، برای دو نقطهy و x از فضای جواب مسئله، میگوییم x بر y غلبه دارد و آن را با x≺y نشان میدهیم، اگر به ازای i=1,2,…,k داشته باشیم: fi(x)≤fi(y) و بعلاوه j∈1,2,…,k وجود داشته باشد بطوریکه fjx<fjy. این مفهوم در شکل 5-2 بخوبی نشان داده شده است.
در صورتیکه شرط دوم بالا برقرار نباشد، یعنی چنین j ای وجود نداشته باشد، آنگاه میگوییم y بر x غلبه ضعیف دارد و آنرا با x≼y نمایش میدهیم.
اگر در میان متغیرهای تصمیمگیری در فضای جستجوی جواب هیچ yای وجود نداشته باشد که y≺x، انگاه x یک بهینه پارتو نامیده میشود (ر.ک. شکل 5-1).
مجموعه همه نقاط بهینه پارتو، مجموعه بهینه پارتو یا Pareto Optimal Front نامیده میشود. به بیان ریاضی، اگر فضای جستجوی جواب را S بنامیم، آنگاه مجموعه S* با تعریف زیر یک Pareto Optimal Front است (ر.ک. شکل 5-3):
S*={x∈S|∄y∈S, y≺x}
شکل 5-2: نمایش مفهوم غلبه در فضای اهداف

شکل 5-3: نمایش Pareto Optimal Front در فضای اهداف
برای حل مسائل بهینهسازی چند هدفه، الگوریتمهای فراابتکاری به شکل گستردهای مورد استفاده قرار گرفتهاند. در میان این روشها بهنظر میرسد که استفاده از الگوریتم حرکت دسته جمعی ذرات بدلیل سرعت همگرایی زیاد آن، و تعداد کم متغیرهای تنظیم، بیشتر مورد توجه بوده است. در میان محققینی که در زمینه استفاده از الگوریتم حرکت دسته جمعی ذرات در بهینهسازی چند هدفه، فعالیت میکنند، بدون شک کارهای آقای C. A. Coello Coello جزو معتبرترینها ست. بنابراین در این پایان مبنای کار و مقایسه نتایج، براساس نتایج کارهای این محقق مکزیکی خواهد بود.
5-2- روش C. Coello Coello در استفاده از حرکت جمعی ذرات برای حل مسائل چند هدفه [19]
در این روش از تاریخچه بهترین جوابهایی که یک ذره در تکرارهای مختلف با آنها مواجه میشود استفاده شده است که مشابه همان تفکر نخبهگرایی در الگوریتمهای تکاملی است. در این روش از یک انبار عمومی استفاده میشود که دسته ذرات در هر سیکل تکرار خود، تجربه گذر از جوابهای بهینه پارتو خود را در آن ذخیره میکند. بعلاوه، بهروزرسانیهای این انبار براساس یک سیستم جغرافیایی (مبتنی بر موقعیت مکانی ذره در فضای جستجو) که با عنوان Pareto Archive Evolutionary Strategy معرفی شده است، انجام میشود. ذرات برای انتخاب راهنمای حرکت خود (همان Gbest که در توصیف الگوریتم حرکت جمعی ذرات معرفی شد) در هر سیکل حرکت، از همین انبار استفاده میکنند. در اینجا از این مکانیزم بگونهای استفاده میشود که هر ذره میتواند دارای راهنمای جداگانهای باشد. این روش بر پایه ایده استفاده از ابرمکعبها برای افراز فضای جستجو بنا نهاده شده است.
در ادامه مراحل الگوریتم ارائه شده توسط Coello که از این پس با عنوان MOPSO از آن نام میبریم، آورده شده است:
مقداردهی اولیه به مختصات هر کدام از ذرات در جمعیت (POP)
مقداردهی اولیه به سرعت هر ذره (VEL) با مقدار صفر
ارزیابی هر ذره در جمعیت
ذخیره مختصات ذرات non-dominated جمعیت در REP
افراز فضای جستجو به تعدادی ابرمکعب و ذخیره مکان هندسی هر ذره در فضای جستجو براساس ابرصفحهها
مقداردهی اولیه به حافظه هر ذره (حافظه ذره در اینجا به معنی محلی برای نگهداشت مختصات بهترین نقطهای از فضا که ذره از آن عبور کرده بکار رفته است؛ PBEST). بدیهی است که در این مرحله بهترین نقطهای که ذره از آن عبور کرده است، مختصات جاری ذره است.
تکرار مراحل زیر برای تعداد دفعات مشخص شده
محاسبه سرعت هر ذره بر اساس رابطه زیر:
VELi=W*VELi+R1*PBESTi-POPi+R2*(REPh-POPi)که در آن، W (ضریب اینرسی) مقدار 4/0 را بخود میگیرد و R1 و R2 مقادیر تصادفی در بازه [0,1] هستند. ایندکس h بصورت زیر بدست میآید؛ به هرکدام از ابرمکعبهایی که بیش از یک ذره در آن وجود دارد، یک مقدار برازندگی تخصیص داده میشود که حاصل تقسیم یک عدد صحیح بزرگتر از یک (در اینجا 10 بکار رفته است) بر تعداد ذرات در ابرمکعب است. سپس با استفاده از روش انتخاب roulette-wheel یکی از ابرمکعبها انتخاب شده و یکی از ذرات درون آن بطور تصادفی بعنوان REP[h] انتخاب میشود.
محاسبه مختصات جدید هر ذره براساس رابطه زیر:
POPi=POPi+VELiارزیابی هر ذره در جمعیت
بروزرسانی REP بدین طریق که در جمعیت جدید همه ذرات نامغلوب انتخاب شده و به REP اضافه میشوند و نقاطی که در مجموعه جدید نامغلوب نیستند از آن حذف میگردند. درصورتی که تعداد اعضای REP از مقدار حداکثر سایز درنظر گرفته شده برای آن بیشتر شده باشد، برخی از نقاط REP از ابرمکعبهایی که دارای جمعیت بیشتری هستند حذف میگردند.
بروزرسانی حافظه هر ذره (PBEST)؛ بدین صورت که اگر مختصات جاری ذره، بر مختصات ذخیره شده در حافظه ذره غلبه داشته باشد، حافظه جاری ذره با مختصات جدید آن جایگزین میشود و در صورتیکه مختصات ذخیره شده در حافظه ذره بر مختصات جاری آن غلبه داشته باشد، حافظه ذره بدون تغییر حفظ میشود. در صورتیکه هیچکدام از مختصات حافظه و جاری، بر یکدیگر غلبه نداشته باشند، با یک احتمال تصادفی، مختصات جاری ذره جایگزین مختصات حافظه خواهد شد.
خاتمه حلقه
خاتمه الگوریتم
الگوریتم فوق اگرچه در تستهای مطرح در این زمینه به نتایج خوبی میرسد اما واریاسیونهای دیگری از این روش را نیز میتوان در نظر گرفت. در این تحقیق، ایده تقسیم فضای جستجو به تعدادی ابرمکعب و انتخاب راهنمای ذرات براساس تعداد ذرات بهینه پارتو در هر مکعب که در این الگوریتم از آن استفاده شده، حذف شده و بجای آن از ایده دستهبندی نقاط بهینه پارتو براساس خوشهبندی آنها معرفی شده است. در بخش بعدی این روش مورد بحث قرار گرفته است.
5-3- الگوریتم MOPSO مبتنی بر چگالی هسته
در این تحقیق روش MOPSO به این صورت اصلاح میشود که در آن برای تعیین مقدار برازندگی هر ذره در جمعیت، بجای استفاده از افراز فضا به ابرمکعبها، از چگالی هسته هر ذره در جمعیت استفاده میشود. بنابراین الگوریتم MOPSO مبتنی بر چگالی هسته که از اینجا به بعد آنرا DbMOPSO نامیده میشود، بصورت زیر خواهد بود.
انتخاب بهترین ذره در REP براساس مقدار برازندگی هر ذره در و با استفاده از الگوریتم Roulette-Wheel صورت میگیرد. در اینجا برای افزایش تنوع در جوابهای بدست آمده، و توزیع همگنتر جوابها در فضای جواب، برازندگی هر ذره برابر معکوس مقدار چگالی هسته آن در نظر گرفته میشود. و بهترین ذره در مجموعه (GBEST) از ذرات با برازندگی بیشتر (چگالی هسته کمتر) با استفاده از الگوریتم Roulette-Wheel انتخاب میگردد.
در صورتی که تعداد اعضای REP بیشتر از سایز درنظر گرفته شده برای آن شود، از همین مقدار برازندگی استفاده شده و ذراتی که دارای چگالی هسته بیشتری هستند با استفاده از الگوریتم Roulette-Wheel برای حذف از REP کاندید میگردند.
73660-81915POP←GenerateInitialPopulation VEL←InitializeVelocities()EvaluatePOPInitialize PBEST, GBESTwhile termination condition not met do REP←FindNondominatedSolutionsPOP for i=1:size(REP) fitness[i]←KernelDensity(REPi) GBEST←SelectGuideREP, fitness for i=1:MAX VELi←ComputeVelocityVELi, POPi, PBESTi, GBEST POPi←POPi+VELi end for EvaluatePOPend whileشکل 5-4: الگوریتم DbMOPSO
020000POP←GenerateInitialPopulation VEL←InitializeVelocities()EvaluatePOPInitialize PBEST, GBESTwhile termination condition not met do REP←FindNondominatedSolutionsPOP for i=1:size(REP) fitness[i]←KernelDensity(REPi) GBEST←SelectGuideREP, fitness for i=1:MAX VELi←ComputeVelocityVELi, POPi, PBESTi, GBEST POPi←POPi+VELi end for EvaluatePOPend whileشکل 5-4: الگوریتم DbMOPSO
محاسبه چگالی هسته بدین صورت انجام میشود که برای هر ذره در فضای جستجو یک تابع توزیع احتمال گاوسی در نظر گرفته میشود. جمع این توابع توزیع در هر نقطه از فضا، مقدار چگالی هسته را در آن نقطه بدست میدهد.
5-4- مقایسه نتایج
چندین تابع تست براساس مراجع و مقالات موجود در بررسی الگوریتم های تکاملی برای مقایسه نتایج دو روش MOPSO و DbMOPSO بکار گرفته شدهاند. برای مقایسه کمی این دو الگوریتم یک معیار متریک بصورت زیر معرفی شده است [20].
M1*=1Y'd'∈Y'min d'-d*;d∈Yکه در آن Y',Y⊆Y مجموعه های بردارهای هدف هستند که به ترتیب مطابق با مجموعههای بردارهای تصمیمگیری نامغلوب X', X⊆X میباشند و X مجموعه بردارهای تصمیمگیری مسئله (مجموعه فضای جستجوی جواب) است. با کمی دقت مشخص است که M1* در واقع میانگین فاصله نسبت به مجموعه بهینه پارتو (POS) است. برای محاسبه M1* باید ابتدا مجموعه POS را داشته باشیم. برای مسائل تستی که در ادامه این بخش آورده شده اند، ابتدا مجموعه های POS از طریق مقایسه تمام محدوده نقاط در فضای جستجو بدست آمدهاند.
در اینجا نتایج مقایسه دو الگوریتم مذکور آورده شدهاند اما در [19] نتایج شبیهسازی الگوریتمهای NSGA II و PAES نیز مورد بررسی قرار گرفتهاند و در اینجا عیناً از همان مرجع برای مقایسه نقل شدهاند. پارامترهای بکار رفته در شبیهسازی برای هرکدام از توابع تست در قسمت مربوطه آورده شده است.
5-4-1- تابع تست 1
تابع تست اول بوسیله Deb در [21] معرفی شده است.
minimize f1x1,x2= x1minimize f2x1,x2=(1+10x2)×1-x11+10x2α-x11+10x2sin2πqx2که در آن 0≤x1,x2≤1 و پارامترهای α و q به ترتیب برابر 2 و 4 انتخاب شده اند. در شکل های زیر نتایج شبیه سازی با استفاده از الگوریتم های NSGA-II، PAES، MOPSO و DbMOPSO آورده شده اند.

Related posts: