*75

دانشگاه صنعتی خواجه نصیرالدین طوسیدانشکده مکانیک
پایان نامه کارشناسی ارشدرشته مهندسی مکاترونیک
عنوانسیستم برنامهریزی و کنترل تولید در صحن کارخانه با استفاده از همکاری عاملهای هوشمند برای حصول به سفارشیسازی انبوه
نگارشمهدی خواجه
استاد راهنمادکتر مهرداد کازرونی
بهمن 1388
بسم الله الرّحمن الرّحیم

فهرست مطالب
TOC o “1-3” h z u فصل 1: مقدمه PAGEREF _Toc253535934 h 51-1- مقدمه PAGEREF _Toc253535937 h 61-2- نوآوریهای تحقیق PAGEREF _Toc253535938 h 71-3- ساختار پایاننامه PAGEREF _Toc253535939 h 7فصل 2: سفارشی‌سازی در تولید انبوه PAGEREF _Toc253535940 h 92-1- مقدمه PAGEREF _Toc253535943 h 102-2- سطوح سفارشی‌سازی PAGEREF _Toc253535944 h 122-3- توانمندی‌های مورد نیاز برای اجرای سفارشی‌سازی در تولید انبوه PAGEREF _Toc253535945 h 162-5- جمعبندی و نتیجهگیری PAGEREF _Toc253535946 h 18فصل 3: برنامهریزی و زمانبندی PAGEREF _Toc253535947 h 193-1- مقدمه PAGEREF _Toc253535950 h 203-2- مدلسازی سیستم تولید در برنامهریزی و زمانبندی PAGEREF _Toc253535951 h 213-3- کارها، ماشینها و کارگاهها PAGEREF _Toc253535952 h 243-4- معیارهای کارایی در زمانبندی تولید PAGEREF _Toc253535953 h 283-5- مدلسازی ریاضی مسأله زمانبندی کارگاه منعطف PAGEREF _Toc253535954 h 323-6- پیشینه تحقیق در زمینه زمانبندی کارگاه منعطف PAGEREF _Toc253535955 h 353-7- جمعبندی و نتیجهگیری PAGEREF _Toc253535956 h 37فصل 4: فرااکتشافات در بهینهسازی PAGEREF _Toc253535957 h Error! Bookmark not defined.4-1- مقدمه PAGEREF _Toc253535960 h 804-2- تعاریف اولیه PAGEREF _Toc253535961 h 804-3- روشهای مبتنی بر مسیر PAGEREF _Toc253535962 h 854-4- روشهای جستجوی محلی کاوشگرانه PAGEREF _Toc253535963 h 924-5- روشهای مبتنی بر جمعیت PAGEREF _Toc253535964 h 974-6- جمعبندی و نتیجهگیری PAGEREF _Toc253535965 h 107فصل 5: بهینهسازی چندهدفه با حرکت جمعی ذرات PAGEREF _Toc253535966 h 405-1- مقدمه PAGEREF _Toc253535969 h 415-5- جمعبندی و نتیجهگیری PAGEREF _Toc253535970 h 61فصل 6: کاربرد DbMOPSO در برنامهریزی و زمانبندی کارگاه منعطف PAGEREF _Toc253535971 h 636-1- مقدمه PAGEREF _Toc253535974 h 646-2- فضای جستجو PAGEREF _Toc253535975 h 656-3- مسائل مورد بررسی PAGEREF _Toc253535976 h 666-4- نتایج شبیه سازی PAGEREF _Toc253535977 h 716-6- جمعبندی و نتیجهگیری PAGEREF _Toc253535978 h 75فصل 7: جمعبندی و نتیجهگیری PAGEREF _Toc253535979 h 767-1- مقدمه PAGEREF _Toc253535982 h 777-2- دستاوردهای تحقیق PAGEREF _Toc253535983 h 777-3- محورهای مطالعه و گسترش بیشتر PAGEREF _Toc253535984 h 78مراجع PAGEREF _Toc253535985 h 109

فهرست جداول
جدول 2-1: سطوح سفارشی سازی عام 15
جدول 6-1: زمانهای اجرای عملیات مربوط به نمونه مسئله 1 95
جدول 6-2: زمانهای اجرای عملیات مربوط به نمونه مسئله 2 96
جدول 6-3: زمانهای اجرای عملیات مربوط به نمونه مسئله 3 97
جدول 6-4: زمانهای اجرای عملیات مربوط به نمونه مسئله 4 98
جدول 6-5: مقادیر توابع هدف راه حلهای بدست آمده برای مسئله نمونه 1 توسط کاسم و همکاران 100
جدول 6-6: مقادیر توابع هدف راه حلهای بدست آمده برای مسئله نمونه 1 با استفاده از الگوریتم DbMOPSO 100
جدول 6-7: مقادیر توابع هدف راه حلهای بدست آمده برای مسئله نمونه 2 توسط کاسم و همکاران 101
جدول 6-8: مقادیر توابع هدف راه حلهای بدست آمده برای مسئله نمونه 2 با استفاده از الگوریتم DbMOPSO 101
جدول 6-9: مقادیر توابع هدف راه حلهای بدست آمده برای مسئله نمونه 3 توسط کاسم و همکاران 102
جدول 6-10: مقادیر توابع هدف راه حلهای بدست آمده برای مسئله نمونه 3 با استفاده از الگوریتم DbMOPSO 102
جدول 6-11: مقادیر توابع هدف راه حلهای بدست آمده برای مسئله نمونه 4 توسط کاسم و همکاران 103
جدول 6-12: مقادیر توابع هدف راه حلهای بدست آمده برای مسئله نمونه 4 با استفاده از الگوریتم DbMOPSO 103

فهرست اشکال
شکل 3-1: نمودار جریان اطلاعات در یک سیستم تولیدی 23
شکل 4-1: الگوریتم بهبود تکراری 46
شکل 4-2: الگوریتم گداخت شبیهسازی شده 46
شکل 4-3: ایده جستجوی محلی هدایت شده 54
شکل 4-4: یک مرحله دلخواه از ILS 56
شکل 4-5: قالب کلی الگوریتمهای محاسبات تکاملی 58
شکل 4-6: قالب کلی الگوریتم حرکت جمعی ذرات 65
شکل 5-1: مفهوم راهحل بهینه پارتو 70
شکل 5-2: نمایش مفهوم غلبه در فضای اهداف 71
شکل 5-3: نمایش Pareto Optimal Front در فضای اهداف 72
شکل 5-4: الگوریتم DbMOPSO 76
شکل 5-5: نتیجه حاصل از الگوریتم NSGA II در حل مسئله نمونه 1 78
شکل 5-6: نتیجه حاصل از الگوریتم PAES در حل مسئله نمونه 1 78
شکل 5-7: نتیجه حاصل از الگوریتم MOPSO در حل مسئله نمونه 1 79
شکل 5-8: نتیجه حاصل از الگوریتم DbMOPSO در حل مسئله نمونه 1 79
شکل 5-9: نتیجه حاصل از الگوریتم NSGA II در حل مسئله نمونه 2 81
شکل 5-10: نتیجه حاصل از الگوریتم PAES در حل مسئله نمونه 2 81
شکل 5-11: نتیجه حاصل از الگوریتم MOPSO در حل مسئله نمونه 2 82
شکل 5-12: نتیجه حاصل از الگوریتم DbMOPSO در حل مسئله نمونه 2 82
شکل 5-13: نتیجه حاصل از الگوریتم NSGA II در حل مسئله نمونه 3 84
شکل 5-14: نتیجه حاصل از الگوریتم PAES در حل مسئله نمونه 3 84
شکل 5-15: نتیجه حاصل از الگوریتم MOPSO در حل مسئله نمونه 3 85
شکل 5-16: نتیجه حاصل از الگوریتم DbMOPSO در حل مسئله نمونه 3 85
شکل 5-17: نتیجه حاصل از الگوریتم NSGA II در حل مسئله نمونه 4 87
شکل 5-18: نتیجه حاصل از الگوریتم PAES در حل مسئله نمونه 4 87
شکل 5-19: نتیجه حاصل از الگوریتم MOPSO در حل مسئله نمونه 4 88
شکل 5-20: نتیجه حاصل از الگوریتم DbMOPSO در حل مسئله نمونه 4 88
فصل 1مقدمهIntroduction

1-1- مقدمهپیشرفتهای اخیر در تولید منعطف و تکنولوژی اطلاعات این امکان را فراهم کرده است که سیستمهای تولیدی بتوانند با هزینه پایینتر طیف وسیعتری از محصولات یا خدمات را ارائه نمایند. بهعلاوه افزایش رقابت در سطح جهانی منجر به رویارویی صنایع با رویکرد افزایش ارزش مشتری در ارائه محصول یا خدمات شده است. بنابراین لزوم درنظر گرفتن نیازهای خاص هر کدام از مشتریان، تولیدکنندگان را به سمت دخالت دادن مشتریان در فرآیند تولید رهنمون شده است. در این میان سفارشی‌سازی در تولید انبوه یکی از روش‌های نوین تولید است که هر روز مورد توجه تولیدکنندگان بیشتری قرار می‌گیرد. سفارشی‌سازی در تولید انبوه، توانایی تولید محصول یا خدمات مختص هر مشتری بر اساس سفارش یا نیازهای شناخته شده او از طریق یک فرآیند کاملاً انعطاف‌پذیر و یکپارچه با حفظ مزایای تولید انبوه است. سفارشی‌سازی در تولید انبوه یکی از فرصت‌هایی است که از طریق رشد و هماهنگی تکنولوژی‌های تولید و تکنولوژی اطلاعات در اختیار تولیدکنندگان قرار گرفته است.
واضح است فعالیت‌هایی که در سیستم‌های سفارشی‌سازی در تولید انبوه انجام می‌شوند نیازمند همکاری گسترده، تبادل اطلاعات و تعامل در محدوده سازمان و خارج از آن است. بخشی از این تعامل در جهت برنامه‌ریزی تخصیص وظایف به منابع و زمان‌بندی اجرای وظایف بر روی منابع است. مسئله برنامهریزی تخصیص وظایف به منابع و زمانبندی اجرای وظایف یکی از پیچیدهترین مسائل بهینهسازی ترکیبیاتی بهشمار میآید که در این تحقیق سعی بر آن است که گسترشی در زمینه حل این دسته مسائل حاصل گردد.
در سیستم‌های سفارشی‌سازی در تولید انبوه، از آنجایی که هر کالای تولید شده دارای شرایط خاص خود، براساس نیاز اعلام شده مشتری خواهد بود، مسئله هماهنگی و تعامل اجزا در صحن کارخانه شکل پیچیدهتری به‌خود می‌گیرد. برای حل مسئله برنامهریزی در چنین شرایطی اجزای سیستم برنامه‌ریزی باید دارای ویژگی‌هایی همچون برقراری ارتباط با اجزای دیگر، واکنشی بودن و خودمختاری باشند. با توجه به این ویژگی‌ها بهره‌گیری از سیستم‌های تکاملی چندعاملی بعنوان یکی از راه‌حل‌های مناسب مطرح می‌گردد. در این روش با بهره‌گیری از اجتماعی از عامل‌ها که هر کدام دارای مجموعه‌ای از خصوصیات و منابع می‌باشند می‌توان راه‌حل‌هایی در محیط محاسباتی پویا بدست آورد.
1-2- نوآوریهای تحقیقدر این تحقیق با توجه به پیشینه تحقیقاتی که در زمینه حل مسئله برنامهریزی و زمانبندی کار کارگاهی منعطف صورت گرفته است، الگویی جدید و مؤثر برای مدلسازی فضای جواب مسئله مطرح میگردد. الگوی ارائه شده، دارای خصوصیات ویژهای است که از جمله مهمترین آنها میتوان به حل همزمان زیر مسئلههای برنامهریزی تخصیص وظایف به منابع و زمانبندی ترتیب اجرای وظایف، اشاره کرد. در ادامه پژوهش به معرفی الگوریتم بهینهسازی حرکت جمعی ذرات پرداخته میشود و شکل جدیدی از این الگوریتم برای حل مسائل بهینهسازی چندهدفه، معرفی میگردد که در آن انتخاب ذرات راهنما براساس چگالی ذرات در فضای اهداف صورت میگیرد، سپس الگوریتم ارائه شده با یکی از الگوریتمهای مشابه مقایسه میشود. بعد از آن، دو ایده ارائه شده، در حل مسئله زمانبندی کار کارگاهی منعطف بهکار گرفته شده و نتایج آن مورد بررسی قرار خواهند گرفت.
1-3- ساختار پایاننامهدر ادامه مطالب پایاننامه، در فصل دوم مفاهیم سفارشی‌سازی انبوه و سطوح پیاده‌سازی آن ارائه خواهد شد و فاکتورهایی که منجر به پیاده‌سازی موفق آن می‌شوند از دیدگاه نویسندگان و محققین مختلف مورد بررسی قرار می‌گیرند و مسئله برنامهریزی و زمانبندی تولید برای حصول به سفارشیسازی در تولید انبوه به مسئله برنامهریزی و زمانبندی کارگاه تولید منعطف با چند هدف، کاهش مییابد. از اینجا به بعد رویکرد پژوهش به سوی حل مسئله زمانبندی چندهدفه در کار کارگاهی منعطف، خواهد بود. در فصل سوم، مفاهیم زمانبندی کارگاهی مطرح شده و با استفاده از آنها یک مدل ریاضی مناسب برای مسئله زمانبندی کار کارگاهی منعطف بدست میآید. در ادامه پایاننامه در فصل چهارم مروری کوتاه به مفهوم فرااکتشاف و کاربرد آن در مسائل بهینهسازی انجام میگردد. در این فصل چند روش فرااکتشافی مهم که در بهینهسازی بهطور گستردهای مورد استفاده قرار میگیرند در قالب سه دسته معرفی میشوند. در فصل پنجم روشهای بهینهسازی چندهدفه با تکیه بر الگوریتم بهینهسازی حرکت جمعی ذرات بعنوان یک روش تکاملی چندعاملی مورد مطالعه قرار میگیرد و الگوریتم جدیدی مبتنی بر چگالی هسته ذرات در فضای اهداف، ارائه شده و با یکی از الگوریتمهای بهینهسازی چندهدفه مبتنی بر حرکت جمعی ذرات مقایسه میگردد. در فصل ششم، ابتدا نمایش جدیدی از فضای جستجوی مسئله زمانبندی کار کارگاهی منعطف معرفی میگردد که قابلیت حل زیرمسئلههای تخصیص عملیات به ماشینها و زمانبندی ترتیب اجرای عملیات را بطور همزمان بدست میدهد. سپس در ادامه این فصل، الگوریتم بهینهسازی که در فصل پنجم معرفی شده است برای حل مسئله زمانبندی کار کارگاهی منعطف مورد استفاده قرار گرفته و نتایج آن با روشهای دیگر مقایسه میشود. در نهایت در فصل هفتم به بحث و نتیجهگیری درباره نتایج تحقیق انجام شده در این پایاننامه پرداخته و پیشنهاداتی برای گسترش تحقیقات در این زمینه، ارائه میشود.
فصل 2سفارشی‌سازی در تولید انبوهMass Customization

2-1- مقدمهپیشرفت‌های اخیر در تولید منعطف و تکنولوژی اطلاعات، که سیستمهای تولید را قادر به ارائه طیف وسیعتری از محصولات با هزینه پایین‌تر می‌کنند، کوتاه شدن چرخه عمر محصول، و رقابت صنعتی فزاینده‌ای که نیاز به استراتژی‌های تولیدی که به نیازهای یکایک مشتریان توجه می‌کنند منجر به ظهور سفارشی‌سازی در تولید انبوه گردید.
یکی از اولین افرادی که صحبت از سفارشی‌سازی در تولید انبوه را مطرح کرد آلوین تافلر بود. آلوین تافلر کار خود را به عنوان یک روزنامه نگار شروع کرد ولی با انتشار اولین کتاب خود به نام “ضربه آینده” [1] در سال 1970 به شهرت بین‌المللی رسید. “موج سوم” [2] ده سال بعد و “انتقال قدرت” [3] ده سال پس از آن منتشر شدند. منظور از موج سوم که در عنوان کتاب به آن اشاره شده، جامعه فوق صنعتی است که در اواخر قرن بیستم ظهور کرده و هنوز هم در حال شکل‌گیری است. این جامعه بعد از موج دوم، یعنی جامعه صنعتی به وجود آمد که خود ناشی از انقلاب صنعتی بود. جامعه صنعتی هم بعد از مرحله کشاورزی به وجود آمد که به عنوان موج اول شناخته شده است. هر موج جدید توسط توسعه فنآوری جدیدی ظاهر شد. بالاخره فنآوری الکترونیک موج سوم را به وجود آورد. توجه اصلی تافلر انتقال از موج دوم به موج سوم در جوامع پیشرفته است، گو اینکه البته حوزه احتمالی اصطکاک بین انسان‌هایی که در مراحل مختلف پیشرفت (شرایط امواج مختلف) قرار دارند و با هم همزیستی می‌کنند را نیز مورد بررسی قرار می‌دهد. به نظر تافلر، صفت مشخصه موج سوم به جای تولید انبوه، سفارشی سازی انبوه است.
وقتی به تاریخچه یا سوابق شرکت‏های خودروساز مطرح نگاه می‏کنیم، می‏بینیم که آنها نیز همین راهبردها را به کار گرفته‏اند. آن‌ها در دوره‏ای، به تولید انبوه می‏پرداختند بعد از آن تولید ناب باب شد و اکنون در دوره‏ای هستیم که تولید انبوه براساس نیاز و سلیقه مردم یا سفارشیسازی در تولید انبوه اهمیت پیدا کرده است. انجام چنین کاری یعنی تولید براساس سفارش مشتری ـ آن هم با همه مزایای تولید انبوه ـ فقط زمانی ممکن است که ابزارهای آن فراهم باشد.
مفهوم سفارشی‌سازی در تولید انبوه بطور رسمی تقریباً از اواخر دهه 1980 معرفی گردید و ادامه منطقی توسعه و پیشرفت در زمینه‌های مختلف تولید مانند تولید منعطف و بهینه‌سازی شده براساس کیفیت و قیمت است. طبق تعریفی که دیویس در 1989 ارائه نمود [4]، سفارشی‌سازی در تولید انبوه عبارت از فراهمسازی محصولات یا سرویس‌های اختصاصی برای یک مشتری از طریق چابکی بالا در فرآیند، انعطاف‌پذیری و یکپارچگی در سیستم تولید است.
بسیاری از نویسندگان این مفهوم را بصورت باریک‌تر و عملی‌تری مورد توجه قرار داده‌اند و تعریف دیگری را ارائه کرده‌اند. آنان معتقدند که سفارشی‌سازی در تولید انبوه، استفاده از تکنولوژی اطلاعات، فرآیندهای انعطافپذیر و معماری سازمانی ویژه برای ارائه کردن طیف وسیعی از محصولات و سرویس‌هایی که به نیازهای مخصوص هر کدام از مشتریان پاسخ می‌دهد (اغلب از طریق مجموعه‌ای از انتخاب‌ها) با هزینه‌ای نزدیک به تولید انبوه است [5].
در هر دو این دیدگاه‌ها سفارشی‌سازی در تولید انبوه بعنوان یک ایده سیستماتیک، همه جنبه‌های فروش محصول، توسعه، تولید و ارائه آن و بطور کلی زنجیره کاملی از انتخاب مشتری تا تحویل محصول را در بر می‌گیرد.
با وجود مشکلات زیاد پیاده‌سازی سیستم‌های تولید مبتنی بر سفارشی‌سازی در تولید انبوه، مشکلات زیر بهنظر اساسی‌تر جلوه میکنند: الف) پایین نگه داشتن قیمت محصول سفارشی‌سازی شده متناسب با تولید انبوه محصول استاندارد. ب) دستیابی به کیفیت بالا برای طیف وسیعی از محصولات و پ) ارتقا و تولید کالاهای سفارشی بصورت دوره‌ای برای جلب رضایتمندی مشتری و تمایل او برای سفارش محصولات جدیدتر. بنابراین سازمان‌های تولیدی برای پیاده‌سازی سیستم‌های مبتنی بر سفارشی‌سازی در تولید انبوه باید توانایی انجام تغییراتی همچون موارد زیر را داشته باشند: الف) پیمانه‌ای‌سازی محصولات و فرآیندها برای ایجاد قابلیت مدیریت تنوع محصولات ب) استفاده از سیستم‌های نرم‌افزاری مبتنی بر دانش و پ) استفاده از سیستم‌های تولید و اتوماسیون منعطف.
بنابر موارد ذکر شده، تغییر سیستم تولیدی سازمان به سیستم مبتنی بر سفارشی‌سازی در تولید انبوه پیامدهای بسیاری را در توسعه محصول و چرخه تولید ایجاد خواهد نمود. این پیامدها را می‌توان در قالب توانمندی در حوزه‌های محاسباتی، ارتباطی و اطلاعاتی دسته‌بندی کرد که موجب بروز نوآوری‌هایی در اتوماسیون منعطف، شبکه‌های کامپیوتری صنعتی و طراحی محصول بصورت الکترونیکی می‌شوند.
2-2- سطوح سفارشی‌سازیتعیین سطح سفارشی‌سازی یکی از نکات اساسی در بحث‌ها و نظرات مربوط به تشخیص درست محصولات سازمان است. ممکن است کسانی باشند که بطور افراطی بر این باور باشند که باید تمام نیازمندی‌ها و سلایق یکایک مشتریان را تأمین کرد. یعنی به هر مشتری کالایی را باید عرضه کرد که دقیقاً و تمام و کمال همان است که می‌خواهد. از طرفی هم کسانی هستند که سفارشی‌سازی را صرفاً در ارائه محصول با امکان انتخاب برخی خصوصیات آن در نظر می‌گیرند. برخی دیگر نیز سفارشی‌سازی موفق را در توانایی ترکیب سفارشی‌سازی به همراه تنوع در اجزا و فرآیندهای استاندارد تولید میدانند.
محققین بسیاری با دیدگاه‌های مختلف، چارچوب‌های متنوعی را برای سطوح سفارشی‌سازی پیشنهاد کرده‌اند که در ادامه به برخی از آنها اشاره می‌شود.
پاین و گیلمور چهار سطح برای سفارشی‌سازی محصول بر اساس مشاهدات و تجربیات عملی خود ارائه داده‌اند که عبارتند از [6]:
سطح تعاملی: طراحان محصول با مشتریان گفتگو کرده و براساس نیاز و سلیقه مشتری محصول را طراحی می‌کنند
سطح وفق‌پذیری: محصولات استاندارد بهگونه‌ای طراحی می‌شوند که توسط مشتری قابل تغییر کاربری باشند و مشتری بتواند مطابق نیاز و سلیقه خود محصول خریداری شده را تغییر دهد.
سطح Cosmetic: محصولات استاندارد تولید می‌شوند ولی برای مشتریان مختلف بهگونه‌های متفاوتی بسته‌بندی می‌شوند یا بهگونه‌های متفاوتی به مشتری عرضه می‌شوند
سطح شفاف: محصولات براساس تنظیماتی که توسط مشتری روی آن‌ها انجام می‌شود خود را با نیازمندی‌های مشتری وفق می‌دهند.
پاین در مقاله دیگری چهار سطح سفارشی‌سازی را بصورت زیر مطرح کرد [7]:
سرویس‌های سفارشی‌سازی شده: محصولات استاندارد توسط افرادی در سیستم فروش متناسب با نیاز مشتری درآمده و سپس عرضه می‌شوند.
سفارشی‌سازی درونی: محصولات استاندارد در هنگام استفاده توسط مشتری متناسب با نیاز تغییر می‌کنند.
سفارشی‌سازی در نقطه تحویل: عملیات اضافی مخصوصی متناسب با نیاز مشتری در هنگام تحویل بر روی محصول انجام می‌شود.
تولید پیمانه‌ای: اجزاء استاندارد برای شکل دادن به نیاز مشتری با طیف وسیعی از پیکربندی‌ها و ترکیب‌ها می‌توانند محصولات متنوعی را بوجود آورند.
اسپیرا محقق دیگری است که مدل مشابهی را با چهار نوع سفارشی‌سازی مطرح کرده است [8]:
بسته‌بندی سفارشی‌سازی شده
سرویس‌های سفارشی شده
کار اضافی براساس سفارش مشتری
مونتاژ پیمانه‌ای
ترکیب چارچوب‌هایی که در بالا به آنها اشاره شده است ما را به سمت هشت سطح عام از سفارشی‌سازی هدایت می کند که در جدول 2-1 مشخص شده‌اند [5]:
در این جدول طراحی در بالاترین سطح (سطح هشتم) قرار گرفته است و اشاره به تعاملی بودن پروژه و تولید و ارائه محصول براساس اولویت‌های اختصاصی هر مشتری دارد.
سطح هفتم اشاره به تولید محصول متناسب با نیازهای خاص مشتری با تکیه بر برخی طراحی‌های پایه و استاندارد شده دارد.
سطح ششم اشاره به مونتاژ محصول با سرهم‌بندی اجزاء پیمانه‌ای با ترکیب‌ها و پیکربندی‌های متفاوت برای پاسخ به نیازهای اختصاصی هر مشتری دارد.
در سطوح چهارم و پنجم دستیابی به سفارشی‌سازی از طریق انجام کار اضافی روی محصول پس از تولید و قبل از ارائه به مشتری مورد توجه قرار می‌گیرد
Types of customization Stages of MC MC strategies MC approaches Generic levels
Pure customization Collaborative; transparent 8. Design
Tailored customization 7. Fabrication
Assembling standard components into unique configurations Modular production Customized standardization 6. Assembly
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+10×2)×1-x11+10×2α-x11+10x2sin2πqx2که در آن 0≤x1,x2≤1 و پارامترهای α و q به ترتیب برابر 2 و 4 انتخاب شده اند. در شکل های زیر نتایج شبیه سازی با استفاده از الگوریتم های NSGA-II، PAES، MOPSO و DbMOPSO آورده شده اند.

شکل 5-5: نتیجه حاصل از الگوریتم NSGA II در حل مسئله نمونه 1 [19]

شکل 5-6: نتیجه حاصل از الگوریتم PAES در حل مسئله نمونه 1 [19]

شکل 5-7: نتیجه حاصل از الگوریتم MOPSO در حل مسئله نمونه 1 [19]

شکل 5-8: نتیجه حاصل از الگوریتم DbMOPSO در حل مسئله نمونه 1
نتایج معیار M1* برای تابع تست 1:
DbMOPSO MOPSO [19] PAES [19] NSGA-II [19] 001656784/0 002173076/0 008877235/0 002235304/0 M1*00015154/0 00014726/0 015277404/0 000298614/0 S.DEV.
5-4-2- تابع تست 2
تابع تست دومی که در اینجا استفاده شده است بوسیله Schaffer در [22] ارائه شده است که روابط آن در زیر می آید:
minimize f1x=-x-2+x4-x-4+x x≤11<x≤33<x≤4x>4minimize f2x=x-52که در آن -5≤x≤10.

شکل 5-9: نتیجه حاصل از الگوریتم NSGA II در حل مسئله نمونه 2 [19]

شکل 5-10: نتیجه حاصل از الگوریتم PAES در حل مسئله نمونه 2 [19]

شکل 5-11: نتیجه حاصل از الگوریتم MOPSO در حل مسئله نمونه 2 [19]

شکل 5-12: نتیجه حاصل از الگوریتم DbMOPSO در حل مسئله نمونه 2
نتایج معیار M1* برای تابع تست 2:
DbMOPSO MOPSO [19] PAES [19] NSGA-II [19] 00086583/0 001275433/0 061678751/0 001829892/0 M1*0000967438/0 0001265695/0 116312867/0 000434949/0 S.DEV.
5-4-3- تابع تست 3
تابع تست سوم توسط Deb در [21] معرفی شده است و روابط ریاضی آن بصورت زیر میباشد
minimize f1x1,x2=x1minimize f2x1,x2= gx1,x2∙h(x1,x2)که در آن
gx1,x2=11+x22-10cos2πx2و
hx1,x2=1-f1(x1,x2)g(x1,x2) f1(x1,x2)≤g(x1,x2)0 otherwiseهمچنین
0≤x1≤1 , -30≤x2≤30
شکل 5-13: نتیجه حاصل از الگوریتم NSGA II در حل مسئله نمونه 3 [19]

شکل 5-14: نتیجه حاصل از الگوریتم PAES در حل مسئله نمونه 3 [19]

شکل 5-15: نتیجه حاصل از الگوریتم MOPSO در حل مسئله نمونه 3 [19]

شکل 5-16: نتیجه حاصل از الگوریتم DbMOPSO در حل مسئله نمونه 3
نتایج معیار M1* برای تابع تست 3:
DbMOPSO MOPSO [19] PAES [19] NSGA-II [19] 00059596/0 000782244/0 333610493/0 023737708/0 M1*000063738/0 000077611/0 598214005/0 099354268/0 S.DEV.
5-4-4- تابع تست 4
تابع تست چهارم نیز همانند توابع تست اول و سوم توسط Deb در [21] معرفی و بکار گرفته شده است
minimize f1x1,x2=x1minimize f2x1,x2=g(x2)x1که در آن
gx2=2-e-x2-0.20.0042-0.8e-x2-0.60.42و همچنین
0.1≤x1≤1.0, 0.1≤x2≤1.0
شکل 5-17: نتیجه حاصل از الگوریتم NSGA II در حل مسئله نمونه 4 [19]

شکل 5-18: نتیجه حاصل از الگوریتم PAES در حل مسئله نمونه 4 [19]

شکل 5-19: نتیجه حاصل از الگوریتم MOPSO در حل مسئله نمونه 4 [19]

شکل 5-20: نتیجه حاصل از الگوریتم DbMOPSO در حل مسئله نمونه 4
نتایج معیار M1* برای تابع تست 4:

این نوشته در مقالات ارسال شده است. افزودن پیوند یکتا به علاقه‌مندی‌ها.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *