راه‌حل‌های موجود، به یافتن حل نزدیک به بهینه می‌پردازد که از جمله آنها روش‌های فرا ابتکاری و تجزیه مسائل می‌باشند که در بسیاری از تحقیقات جدید از روش‌های فرا ابتکاری مانند الگوریتم جستجوی ممنوع13، شبیه‌سازی تبرید14، الگوریتم ژنتیک، کلنی مورچه‌ها15، جستجوی پراکنده16 و… جهت حل مسائل زمانبندی استفاده شده است. در بسیاری از این تحقیقات کارایی روش‌های مذکور به اثبات رسیده و می‌توان نتیجه گرفت که به شرط طراحی صحیح یک الگوریتم فرا ابتکاری می‌توان به نتایج قابل توجهی جهت حل مسائل با ابعاد بالا دست یافت
مسئله جریان کارگاهی انعطاف پذیر دو مرحله ای بدون وقفه
به طور کلی این مدل حالت خاصی از مسئله جریان کارگاهی است. مسئله مورد مطالعه به شرح زیر می باشد. یک مجموعه شامل n کار است که قرار است پردازش شوند. هر کار نیاز به دو عملیات دارد که باید در دو مرحله متوالی و و بدون وقفه پردازش شوند. مرحله اول شامل ماشین یکسان و مشابه آن مرحله دو شامل ماشین یکسان است. اولین و دومین عملیات مربوط به کار باید به ترتیب روی ماشین های مرحله اول و دوم با زمان های پردازش و و به ترتیب و بدون وقفه انجام شوند. این مسئله را می توانیم به صورت نمایش دهیم. مسئله مورد مطالعه در این تحقیق به صورت شماتیک در شکل (1-2) نمایش داده شده است. همانطور که در شکل نیز میبینیم هر کار حالت ممکن برای قرار گرفتن روی ماشین های مرحله اول و دوم دارد و همچنین n کار موجود حالت ممکن برای توالی دارند. به این ترتیب در این مسئله با توجه به ابعاد مسئله برنامه زمانی مختلف می توانیم داشته باشیم که تست کردن کلیه این برنامه ها بسیار سخت و پیچیده است. بنابراین هدف ما در گام اول ارائه یکی از برنامه های زمانی در بینحالت مختلف است که کارایی مناسبی نیز نسبت به سایر الگوریتم های هیوریستیک موجود داشته باشد. و در گام دوم ارائه جواب های پارتو به این منظور که تصمیم گیرنده گزینه های بیشتری برای زمان بندی در اختیار داشته باشد.

نمای شماتیک مسئله
کاربردهای مدل
مسائل زمان‌بندی بدون انتظار در آن دسته از محیط‌های تولیدی رخ می‌دهد که در آن یک کار می‌بایست از آغاز تا پایان بر روی یک ماشین یا در بین ماشینها بدون وقفه مورد پردازش قرار گیرد. علت وقوع چنین محیطهایی نوع فن‌آوری و یا فقدان توانایی ذخیره‌سازی بین ماشینها و ایستگاههای کاری است. بطور نمونه عامل دما، غلظت و یا دیگر عوامل باعث می‌شود هر عملیاتی، عملیات پیش از خود را بلافاصله دنبال کند. در تولید فولاد، هنگامی که فولاد مذاب در برابر یکسری عملیات متوالی مانند ریخته‌گری، ذوب و نورد قرار می‌گیرد. چنین وضعیتی رخ می‌دهد،. همچنین در صنایع غذایی، عملیات قرار دادن محصولات غذایی داخل قوطی های کنسرو باید بلافاصله بعد از پخت انجام شود تا از تازه بودن این محصولات اطمینان حاصل نمائیم. در صنایع دارویی، شیمیایی، پتروشیمی و صنایع خدماتی و… چنین مواردی رخ می‌دهد. محیط‌های تولیدی جدید مانند تولید به هنگام17، سیستمهای تولیدی انعطاف‌پذیر18 و سلولهای روباتیک فرآیند تولیدی منطبق با مسایل زمان‌بندی بدون انتظار را فراهم می‌کنند.
بیان مسئله و سوال تحقیق
در این تحقیق، مسئله جریان کارگاهی دو مرحله ای انعطاف پذیر بدون وقفه با هدف تعیین توالی تولید بهینه (نزدیک بهینه) با توجه به اهداف کمینه سازی و بیشینه سازی مورد بررسی قرار می گیرد. هم چنین، ارائه الگوریتم های کارا و مبتنی بر رویکرد های ابتکاری و فراابتکاری در دستور کار قرار گرفته است که با استفاده از آن بتوان به مجموعه جواب های مناسب رسید.
ضرورت انجام تحقیق و اهمیت تحقیق
با توجه به کاربردهای عنوان شده برای مسئله برنامه زمان بندی جریان کارگاهی دو مرحله ای انعطاف پذیر بدون وقفه از یک طرف و تحقیقات بسیار محدود انجام شده در این زمینه از طرف دیگر، ضروری است تحقیقات بیش تری با هدف ارائه روش های کاراتر انجام پذیرد. از این رو، این موضوع به عنوان موضوع تحقیقی مورد نظر این پایان نامه در نظر گرفته شده است.
اهداف تحقیق
به طور کلی اهداف اصلی این تحقیق به شرح زیر می باشد:
گسترش مدل و سازگار نمودن هرچه بیش تر آن با مسائل دنیای واقعی با درنظر گرفتن چندین تابع هدف و در نظر گرفتن محدودیت زمان در دسترس بودن کارها
ارائه الگوریتم های ابتکاری برای مسئله جریان کارگاهی دو مرحله ای انعطاف پذیر بدون وقفه
اتخاذ رویکردی فراابتکاری در حل مسئله جریان کارگاهی دو مرحله ای انعطاف پذیر بدون وقفه
پیش بینی ماکزیمم زمان انجام کارها در مسئله جریان کارگاهی دو مرحله ای انعطاف پذیر بدون وقفه به منظور تخصیص منطقی زمان های موعد تحویل توسط شبکه عصبی فازی تطبیق پذیر
حل مسئله چند هدفه جریان کارگاهی دو مرحله ای انعطاف پذیر بدون وقفه
ساختار انجام تحقیق
این پایان نامه، با بررسی پیشینه و مطالعات صورت گرفته در رابطه مدل تحقیق، به تعیین خلاء های موجود در این زمینه پرداخته و مسئله توسط روش های ابتکاری با در نظر گرفتن چندین تابع هدف (به صورت تک هدفه) و اضافه نمودن محدودیت زمان آماده به کار حل می شود. در ادامه مسئله توسط روش های فراابتکاری الگوریتم ژنتیک هیبریدی و الگوریتم شبیه سازی تبرید هیبریدی حل می شود. نتایج حاصله از الگوریتم ابتکاری و فرا ابتکاری با الگوریتم های ارائه شده در مطالعات قبلی مقایسه می شود.. شکل (1-3) ساختار تحقیق را به صورت شماتیک نش
ان می دهد.

ساختار تحقیق به صورت شماتیک

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

این مطلب رو هم توصیه می کنم بخونین:   سرویس، حاکمیت، معماری، فناوری

مرور ادبیات و پیشینه تحقیق

مقدمه
در این فصل به مرور ادبیات و بررسی پیشینه تحقیق، پرداخته می شود. تحقیقات انجام شده پیرامون مسئله تحقیق بررسی شده و خلاء تحقیقاتی موجود معرفی می گردد.
مساله تک هدفه جریان کارگاهی بدون وقفه
مسائل زمان‌بندی جریان کارگاهی
در این بخش تاریخچه خلاصه‌ای از کارهای صورت گرفته مسائل در زمان‌بندی جریان کارگاهی و همچنین تاریخچه‌ای از تحقیقات صورت گرفته در مسائل جریان کارگاهی انعطاف‌پذیر و روشهایی که برای حل این مسائل به کار رفته است، مرور خواهیم کرد.

مسئله جریان کارگاهی ساده
این مسئله یکی از رایج‌ترین انواع مسائل جریان کارگاهی است که در مرور ادبیات موضوع جریان کارگاهی به وفور دیده می‌شود. در سال 1954 جانسون [8] یک الگوریتم برای حل مسئله دو ماشینه جریان کارگاهی که بدون هیچ‌گونه محدودیتی بوده ارائه نمود. از آن موقع به بعد کارهای زیادی در این حوزه انجام گرفته و که شامل الگوریتم‌های ابتکاری، الگوریتم‌های دقیق برای چندین مسئله با ابعاد گوناگون و محدودیت‌های متنوع می‌باشند. ثابت شده است که مسئله با تعدناد ماشین‌های بیشتر یا مساوی با 3 یک مسئله Np-hard می‌باشد. کارهای بسیار زیادی در این حوزه صورت گرفته ولی با توجه به اینکه تحقیق انجام شده از طرف ما بصورت مستقیم به این مسئله مربوط نمی‌شود مرور ادبیات موضوع مربوط به مسائل جریان کارگاهی را به خوانندگان این پژوهش‌ واگذار می‌نمائیم. برای مطالعه بیشتر در این خصوص به منبع [9] مراجعه فرمائید.
مسئله جریان کارگاهی انعطاف‌پذیر
این مسئله در ادبیات موضوع معمولاً تحت عنوان مسئله جریان کارگاهی با ماشین‌های موازی و یا مسئله جریان کارگاهی هیبریدی نیز شناخته می‌شود. مسئله جریان کارگاهی انعطاف پذیر در واقع حالت عمومی مسئله جریان کارگاهی است با این تفاوت که m ماشین به صورت موازی تبدیل به S مرحله به صورت موازی می شود که در هر مرحله تعدادی ماشین به صورت موازی موجود است. مرور ادبیات موضوع مربوط به مسائل جریان کارگاهی انعطاف پذیر در منبع [11،10] به طور مفصل شرح داده شده است. خلاصه‌ای کارهای انجام شده با استفاده از روشهای حل متعدد در ادامه ارائه شده است.
الف ) مسئله جریان کارگاهی انعطاف‌پذیر دو مرحله‌ای
آرتاناری و راماسوامی 19[12] اولین بار مسئله جریان کارگاهی انعطاف‌پذیر دو مرحله‌ای را معرفی نمودند. آنها حالت خاصی از این مسئله را که در مرحله اول و در مرحله دوم بود برای 10 کار با استفاده از روش شاخه و کران حل نمودند. این مسئله توسط محققان دیگری نیز مورد مطالعه قرار گرفته است. [14،13]
گوپتا20 [13] استفاده از قاعده جانسون را برای تخصیص دادن کار به ترتیب در مرحله‌ اول و بعد از انجام مرحله اول آن در مرحله دوم پیشنهاد داد. بلازویچ و همکاران21 [14] نشان دادند که می‌توان اثبات کرد که استفاده از قاعده جانسون و یا قاعده بزرگترین زمان پردازش به طی منجر می‌شود که یا جواب بهینه است و یا نزدیک به جواب بهینه می‌باشد.
ناراسیمهان و پانواکر22 [15] حالتی که در آن چندین ماشین موازی در مرحله اول و چندین ماشین با سرعت‌های متفاوت در مرحله دوم وجود دارند را مورد بررسی قرار دادند. آنها یک الگوریتم ابتکاری ارائه دادند که
در هر تکرار از میان کارهای زمان‌بندی نشده، کارهایی که افزایش مجموع زمان‌های بیکاری و انتظار میان مراحل را مینیمم می‌کند، یکی را انتخاب می‌کنند.
وس23 [16] یک متدلوژی برای حل مسئله جریان کارگاهی دو مرحله‌ای با زمان‌های آماده‌سازی وابسته ارائه داد که در تحقیق وی تعداد ماشین‌های مرحله دوم یک عدد بود. او از الگوریتم جستجوی ممنوع برای بهبود جواب‌ها استفاده نمود. جاینت و همکاران24 [17] مسئله جریان کارگاهی انعطاف‌پذیر دو مرحله‌ای را بصورت یک مسئله برنامه‌ریزی اعداد صحیح مختلط فرمول‌بندی کردند و سه حد پائین برای پیش‌بینی جواب بهینه ارائه دادند. در روش آنها ابتدا توالی به دست آمده و سپس عمل تخصیص به ماشین‌ها صورت می‌گیرد.
ب ) مسئله جریان کارگاهی انعطاف‌پذیر چند مرحله‌ای

مسئله جریان کارگاهی چند مرحله‌ای انعطاف‌پذیر شامل تعدادی مرحله‌ است که در هر مرحله 1 یا بیشتر از 1 ماشین موازی وجود دارند (حداقل یکی از مراحل باید بیشتر از یک ماشین داشته باشد) از انجائی که در اکثر حالت‌های دنیای واقعی با اینگونه مسائل روبرو هستیم این مسئله مورد توجه بسیاری از محققان قرار گرفته است. با توجه به اینکه این مسئله جزو مسائل NP-hard در حوزه مسائل زمان‌بندی است تکنیکهای تقریبی و روشهای حل فراوانی برای اینگونه مسائل ارائه شده است.
براه و هانساکر25 [18] و راجندران و چادهوری26 [19] الگوریتم‌های شاخه و کران برای مسئله ارائه دادند. هر دو تحقیق فقط قادر به حل مسائل با سایز کوچک هستند. پورتمن و همکاران27 [20] هم روی همین مسئله مطالعه نمودند. آنها حد پائین ارائه شده توسط براه و هانساکر را بهبود دارند و تعداد شاخه‌هایی که در درخت جستجو استفاده می‌شد را کاهش دادند. آنها همچنین از الگوریتم ژنتیک برای بهبود فرایند جستجو استفاده نمودند. نتایج محاسباتی آنها نشان داد که جواب بهینه‌ای که از الگوریتم شاخه و کران بدست می‌آمد در اکثر حالات الگوریتم ژنتیک نیز به آن می‌رسد. به طوری که فقط در %3 نتایج با روش شاخه و‌کران اختلاف داشت.
مدل‌های زمان‌بندی جریان کارگاهی بدون وقفه
جریان کارگاهی بدون وقفه
در سالهای اخیر علاقه بسیاری از محققان به سوی مسائل بدون وقفه معطوف شده است.این علاقه بیشتر از کاربردهای این مسائل در صنعت ناشی می‌شود. یک مسئله زمان‌بندی بدون وقفه، در محیط‌های تولیدی اتفاق می‌افتد که یک کار از ابتدا تا انتهای مراحل پردازش باید بدون وقفه روی ماشین‌ها قرار بگیرد و مراحل پردازش آن پشت سرهم و بدون هیچ‌گونه تاخیری انجام گیرد. به عبارت دیگر تفاوت میان زمان اتمام هر کار و زمان شروع هر کار در محیط‌های تولیدی بدون وقفه برابر مجموع زمان‌های پردازش می‌باشد.
در بسیاری از صنایع برای مثال در صنایع شیمیایی و پتروشیمی، صنایع فولاد، صنعت شیشه و صنایع مرتبط با کاغذ در فرآیند تولید یک محدودیت وجود دارد. هنگامی که زمان پردازش یک کار شروع می‌شود فرآیندهای بعدی باید بدون تاخیر از یک ماشین به ماشین بعد انجام شوند. حتی در صورت لزوم شروع کار در مرحله قبل باید به اندازه‌ای به تاخیر بیفتد که فرآیندهای بعدی بدون تاخیر آغاز شوند. این نوع از مسائل به اصطلاح، جریان کارگاهی بدون وقفه28 و یا جریان کارگاهی انتظار صفر29 نامیده می شوند. یکی از دو دلیل اصلی بروز این گونه مسائل (بدون وقفه) در محیط‌های تولیدی به ماهیت فرایندها و ماهیت تکنولوژی به کار گرفته شده، باز می‌گردد. در بعضی از فرایندها، برای جلوگیری از تغییرات نامطلوب در مواد دما یا خصوصیات دیگر مواد (مثلا چسبندگی) نیاز به انجام کارها به صور


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