ظرفیت ماشین­آلات

نامحدود

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

دسته بزرگتر و مهم­تری از مسائل بهینه­سازی که عمدتا مسائل زمان­بندی نیز در این دسته قرار می­گیرند دارای تابع زمانی غیر­ چند­جمله­ای هستند. چنین مسائلی را در علم پیچیدگی می­نامند. این دسته از مسائل با روش­های دقیق قابل حل نبوده و لذا از روش­های تقریبی جهت یافتن نزدیک­ترین جواب به بهینه کلی بهره گرفته می­ شود. در نتیجه شناخت مسئله از نقطه نظر پیچیدگی آن می ­تواند بر کیفیت جواب تاثیر مستقیم داشته باشد.
پیندو [۶] در کتاب مفصل خود پیرامون موضوع زمان­بندی سلسله مراتب مسائل پیچیدگی در مسائل زمان­بندی را در گراف­هایی تشریح می­ کند. این گراف­ها در شکل­های(۳-۳) و (۳-۴) آمده­اند.
شکل ۳ شکل ۳-۴. سلسله مراتب پیچیدگی در توابع هدف مسائل زمان­بندی [۶].
شکل ۴ شکل ۳-۳. سلسله مراتب پیچیدگی در مسائل کارگاهی زمان­بندی [۶].
همانطور که از این شکل­ها مشخص است میزان پیچدگی یک مسئله زمان­بندی به نحوه چیدمان ماشین­آلات و تابع هدف مسئله بستگی مستقیم دارد. نکته قابل تعمل در مسئله پیچیدگی آن است که پس از تشخیص میزان پیچیدگی یک مسئله به کمک این گراف­ها می­توان این میزان را به حالات خاص این مسائل نیز تعمیم داد. به عنوان مثال مقدار پیچیدگی مسئله که حالت خاصی از مسئله است را می­توان معادل مقدار پیچیدگی مسئله دانست. این مسئله را در علم پیچیدگی به صورت نشان می­ دهند.
در این تحقیق مسئله زمان­بندی تولید جریانی منعطف بدون انتظار با محدودیت ساعات کاری ماشین­آلات، زمان نصب وابسته به توالی کارها و استراتژی ترکیبی تولیید با هدف حداقل سازی هزینه­ها مورد بررسی قرار می­گیرد. راک^[۸۱] [۴۵] نشان داد که مسئله تولید جریانی بدون انتظار با تابع هدف بیشینه زمان­های تکمیل است. با توجه به نتایج مطرح شده در مورد میزان پیچیدگی مسئله پردازش بدون انتظار به یقین می­توان گفت که مسئله مورد بحث در این تحقیق نیز از میزان پیچیدگی برخوردار است لذا حل این مسئله در ابعاد بزرگ را نمی­ توان به طور کارایی با روش­های دقیق انجام داد. در فصل آینده روش­های حل کارایی با بهره گرفتن از رویکرد­های فراابتکاری ارائه می­گردند. ولید جریانی منعطف بدون انتظار با محدودیت ساعات کاری ماشین
۳-۶. جمع­بندی
در این فصل، پس از بیان تعریف مسئله مورد بررسی و تشریح ویژگی­های آن، مدل ریاضی عدد صحیح غیر خطی جدیدی برای حل آن ارائه گردید. در ادامه فصل نیز اعتبار مدل ریاضی ارائه شده با بهره گرفتن از دو رویکرد سنجیده شد. در پایان فصل نیز دلایلی مبنی بر ناکارامدی روش­های حل دقیق برای مسئله مذکور بیان شده و میزان پیچیدگی آن مورد بررسی قرار گرفت.
فصل چهارم
الگوریتم­های فراابتکاری پیشنهادی و نتایج محاسباتی
۴-۱. مقدمه
هدف از حل هر مسئله بهینه­سازی یافتن بهترین ترکیب ممکن از متغیرهای جواب برای آن مسئله است. مسائل بهینه­سازی از منظر ماهیت جواب شدنی برای آنها به دو دسته کلی مسائل پیوسته و مسائل گسسته تقسیم می­شوند. مسائل حوزه زمانبندی به عنوان دسته­ای مهم از مسائل بهینه­سازی ترکیبی یکی از شناخته شده ترین مسائل با ساختار گسسته هستند. فاکتورهای جواب این دسته از مسائل باید به صورت گسسته کدگذاری شوند. با توجه به اهمیت مسائل این حوزه تاکنون رویکرد­های جواب متنوعی برای حل این مسائل ارائه گردیده­اند. با نگاهی کلی، روش­های حل ارائه شده را می­توان در دو گروه کلی روش­های دقیق^[۸۲] و تقریبی^[۸۳] جای داد. ساختار رویکردهای دقیق به گونه ­ای است که عملکرد آنها را تنها به حل مسائل با پیچیدگی مشخص و ابعاد کوچک محدود می­ کند. این رویکردها برای مسائل با ابعاد بزرگ زمان­های حل بسیار ناکارامدی را ارائه می­ دهند. برهمین اساس، لزوم استفاده از رویکردهای تقریبی در حل مسائل پیچیده بدیهی به نظر می­رسد. این رویکردها بسته به نوع آنها می­توانند جواب­های با کیفیت قابل قبول را در زمان منطقی ارائه ­دهند.
روش­های فراابتکاری^[۸۴] دسته مهمی از روش­های تقریبی هستند که عموما با الگوبرداری از رفتار طبیعت تدوین گردیده­اند. وجه تمایز اصلی این روش­ها با روش­های تقریبی دیگر استفاده از متدهایی برای اجتناب از توقف فرایند جستجو در بهینه محلی^[۸۵] است. براساس استراتژی­ های بکار رفته در فرایند الگوریتم، امروزه طیف گسترده­ای از روش­های فراابتکاری به جامعه محققین ارائه شده است که برای مثال می­توان به الگوریتم­هایی نظیر ژنتیک^[۸۶]، جستجوی ممنوع^[۸۷]، مورچگان^[۸۸]، تبرید شبیه­سازی شده^[۸۹]، سیستم ایمنی مصنوعی^[۹۰] و … اشاره کرد.
در ادامه فصل پیش رو، الگوریتم­های فراابتکاری ارائه شده به منظور حل مسئله مورد بررسی شامل الگوریتم سیستم ایمنی مصنوعی و تبرید شبیه­سازی شده با رویکرد ابری به طور کامل تشریح می­گردند. پس از آن با بهره گرفتن از رویکرد تنظیم پارامترها به روش تاگوچی الگوریتم­های ارائه شده کالیبره شده و به وسیله آزمایشات طراحی شده مورد سنجش قرار می­گیرند. در نهایت نتایج استخراج شده از اجرای آزمایشات تشریح می­گردند.
۴-۲. الگوریتم سیستم ایمنی مصنوعی
الگوریتم سیستم ایمنی مصنوعی یکی از جدیدترین الگوریتم­های الگوبرداری شده از رفتارهای طبیعی پدیده ­ها است. همانگونه که از نام آن هویدا است، این الگوریتم از سیستم ایمنی بدن موجودات زنده و بالاخص پستانداران الگوبرداری شده است. روند کلی الگوریتم بسیار شبیه به الگوریتم ژنتیک بوده اما وجود تفاوت­هایی تاثیرگذار باعث برتری نسبی این الگوریتم نسبت به الگوریتم ژنتیک در برخی مسائل بهینه­سازی ترکیبی گردیده است.
سیستم ایمنی بدن انسان مجموعه ­ای پیچیده است که وظیفه حفاظت بدن در مقابل خطرات و حفظ سلامتی آن را به عهده دارد [۳۴]. این سیستم این وظیفه را با شناسایی عوامل مضر خارجی به نام پاتوژن­ها^[۹۱] و تلاش جهت نابود­سازی آنها انجام می­دهد. این عوامل عموما به کمک فاکتور پروتئینی موجود در ساختارشان که آنتی­ژن^[۹۲] نام دارد شناسایی می­شوند. پس از شناسایی آنتی­ژن، بدن فاکتور پروتئینی مناسب جهت نابود­سازی آنتی­ژن مربوطه را که آنتی­بادی^[۹۳] نام دارد ساخته و به جریان خون می­فرستد و از این طریق عامل خارجی مضر را نابود می­ کند این فرایند را پاسخ اولیه ایمنی^[۹۴] می­نامند. پس از رفع خطر، بدن بهترین آنتی­بادی ساخته شده را در حافظه خود نگه می­دارد تا چنانچه این آنتی­ژن بار دیگر وارد بدن شد بتواند عملکرد سریع­تری داشته باشد. دلیل علمی واکسیناسیون نیز همین است.
در کل سیستم ایمنی بدن انسان به زیر شاخه سیستم ایمنی ذاتی^[۹۵] و سیستم ایمنی قابل انطباق^[۹۶] تقسیم می­ شود [۳۴]. سیستم ایمنی ذاتی وظیفه دفاع عمومی بدن را برعهده داشته و تنها توانایی مبارزه با بیماری­های مشخصی را دارد، چیزی را به یاد نمی­سپارد و عملکرد خود را بهبود نمی­بخشد. اما سیستم ایمنی قابل انطباق توانایی مواجهه با عوامل بیماری­زای جدید را داشته و در هر زمان بهترین عملکرد خود را در مقابل پاتوژن­های جدید به خاطر می­سپارد. لازم به ذکر است که تمام الگوریتم­های ایجاد شده براساس سیستم ایمنی بدن براساس سیستم ایمنی قابل انطباق تدوین شده ­اند.
رویه جستجوی بهترین آنتی­بادی و نحوه به یاد سپاری آن برای تقریبا تمام عمر در بدن توجه بسیاری از پژوهشگران را جلب کرده است. به همین دلیل الگوریتم­های متعددی که هر کدام از بخشی از فرایند ایمنی الگوبرداری شده ­اند در طی سال­ها ایجاد شده است. در یک تقسیم ­بندی کلی الگوریتم­های ایمنی ارائه شده را می­توان در سه دسته الگوریتم ایمنی تولید انتخابی^[۹۷]، شبکه ایمنی^[۹۸] و جستجوی منفی^[۹۹] تقسیم کرد. الگوریتم ایمنی مصنوعی با رویکرد تولید انتخابی عموما در مسائل تعیین توالی بهینه و زمانبندی مورد استفاده قرار می­گیرد حال آنکه دو رویکرد بعدی عموما برای مسائل تشخیص عوامل مخرب و مسائل خوشه­بندی^[۱۰۰] یا جستجوی الگو^[۱۰۱] مورد استفاده قرار می­گیرند. در تحقیق پیش رو نیز رویکرد تولید انتخابی الگوریتم ایمنی مصنوعی مورد استفاده قرار گرفته است لذا از این پس عبارت الگوریتم سیستم ایمنی مصنوعی به اختصار به جای عبارت رویکرد تولید انتخابی الگوریتم سیستم ایمنی مصنوعی به کار می­رود.
الگوریتم سیستم ایمنی مصنوعی فرایند جستجوی خود را با جامعه­ای از آنتی­بادی­های تصادفی که در واقع نشان دهنده جواب­های شدنی هستند آغاز می­ کند. در الگوریتم ایمنی مصنوعی آنتی­ژن­ تابع هدف را نمایندگی می­ کند. لذا هر کدام از جواب­ها از نظر میزان تطابق^[۱۰۲] با تابع هدف مورد ارزیابی قرار می­گیرند و در نهایت جواب­ها براساس میزان تطابقشان با تابع هدف که همان میزان برازندگی^[۱۰۳] در الگوریتم ژنتیک است مرتب می­شوند. پس از آن تعدادی مشخص از بهترین جواب­ها انتخاب شده و براساس رابطه­ای که بسته به نوع مسئله تعریف می­ شود، از هر جواب بسته به میزان تطابق آن تکثیر^[۱۰۴] می­ شود. یعنی هرچه تطابق بیشتر باشد تعداد تکثیر نیز بیشتر می­ شود. در مرحله بعد هر جواب بسته به میزان تطابق خود تحت عملگر جهش^[۱۰۵] قرار می­گیرد، یعنی هر چه تطابق یک جواب بیشتر باشد میزان جهش کمتر خواهد بود. در نهایت میزان تطابق جواب­های جهش یافته بررسی شده و به تعدادی که در مراحل قبل بهترین جواب­ها برگزیده شده بودند، از بهترین جواب­های جهش یافته برداشته می­ شود و با همان تعداد از بدترین جواب­های جامعه مرجع جایگزین می­گردد. این رویه تا فرارسیدن شروط توقف^[۱۰۶] ادامه می­یابد.
الگوریتم سیستم ایمنی مصنوعی به دلیل ساختار خود نقاط قوتی را در مقابل سایر الگوریتم­ها دارا است. از آنجا که این الگوریتم همزمان دسته­ای از جواب­ها را مورد بررسی قرار می­دهد توانایی جستجوی همزمان نقاط متفاوتی از فضای حل را دارا می­باشد و این مسئله توانایی الگوریتم برای رسیدن به بهینه کلی را افزایش داده و از به دام افتادن الگوریتم در بهینه موضعی جلوگیری می­ کند. به علاوه از آنجا که این الگوریتم فاقد عملگر تقاطع^[۱۰۷] است در شرایط مساوی سرعت بالاتری نسبت به الگوریتم ژنتیک داشته و نیز از آنجا که عملگرهای بازتولید و جهش نیز در این الگوریتم تابعی از میزان تطابق جواب هستند سرعت همگرایی آن نسبت به الگوریتم ژنتیک بیشتر است.
۴-۲-۱. شمای کلی الگوریتم سیستم ایمنی مصنوعی
فرایند اجرای الگوریتم تولید انتخابی سیستم ایمنی مصنوعی مطابق شبه برنامه زیر است:
تولید جامعه اولیه آنتی­بادی­ها(جواب­ها) به صورت تصادفی.
محاسبه میزان تطابق جواب­های تولید شده با آنتی­بادی(تابع هدف) و مرتب کردن جامعه اولیه براساس میزان تطابق جواب­ها.
انتخاب تعدادی مشخص از بهترین جواب­ها.
تکثیر جواب­های انتخاب شده براساس میزان تطابق آنها.
اعمال جهش روی جواب­های تکثیر شده.
محاسبه میزان تطابق جواب­های جهش یافته با تابع هدف و مرتب­سازی آنها براساس میزان تطابق.
جایگزین کردن تعدادی مشخص از بهترین جواب­های تولید شده با بدترین جواب­های جامعه جاری.
بررسی شروط توقف. چنانچه شرط توقف برقرار نبود، مرحله ۲.
۴-۲-۲. مفاهیم الگوریتم تولید انتخابی سیستم ایمنی مصنوعی و نحوه بکارگیری آنها
هر رویه حل شامل اصول و مفاهیمی است که فرایند جستجو را تشکیل می­ دهند. مفاهیم پایه­ای الگوریتم سیستم ایمنی مصنوعی به شرح زیر است:
کدگذاری^[۱۰۸] جواب
تولید جامعه اولیه
تابع تطابق
عملگر تکثیر
عملگر جهش
شروط توقف
۴-۲-۲-۱. کد­گذاری جواب
به نحوه نمایش جواب در هر الگوریتم کد­گذاری جواب می­گویند. کد­گذاری باعث افزایش کارایی الگوریتم و امکان انجام روان­تر و کاراتر عملگرهای الگوریتم را بر جواب فراهم می­ کنند. معمولا کد­گذاری به یکی از روش­های ترتیبی، ارزشی و یا درختی انجام می­ شود که بسته به نوع مسئله هر یک می­توانند مزایا و معایب خود را داشته باشند. اما ممکن است روش­های جدید دیگری نیز برای کدگذاری در مسئله­ای خاص مورد استفاده قرار بگیرد. اصلی­ترین نکته در انتخاب یک روش کد­گذاری تولید جواب موجه^[۱۰۹] توسط آن روش کدگذاری است به طوریکه پس از اعمال عملگرها، جواب از حالت موجه خارج نشود. در صورتی که چنین چیزی امکان­ پذیر نباشد باید مرحله اصلاح جواب کدگذاری شده و برطرف کردن مسئله ناموجه بودن آن به فرایند الگوریتم اضافه شود. بدیهی است که افزودن چنین مرحله­ ای از کارایی الگوریتم خواهد کاست. در حالت کلی روش­های کدگذاری در الگوریتم سیستم ایمنی مصنوعی شبیه به الگوریتم ژنتیک است با این تفاوت که رشته جواب در الگوریتم ژنتیک کروموزوم^[۱۱۰] نامیده می­ شود در حالی که این رشته در الگوریتم سیستم ایمنی مصنوعی آنتی­بادی نام دارد.