1-3- مفروضات عمومی مسئله
1. تمامی ماشینها در لحظه زمانی صفر آماده به کار میباشند.

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

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

2. تمامی ماشینها بطور مستمر در دسترس میباشند و امکان خرابی ماشینها وجود ندارد.
3. هر ماشین در هر لحظه قادر به پردازش تنها یک کار میباشد.

4. بیکاری ماشینها مجاز است.
5. زمان پردازش کارها روی ماشینهای مختلف یکسان نمیباشد.
6. کارها دارای زمان های آماده سازی وابسته به توالی پردازش کارها و نوع ماشین ها می باشند، بعلاوه کارها دارای زمان آماده سازی اولیه میباشند که بستگی به نوع ماشینها دارد.
7. هر کار در طول زمان پردازش خود تنها بر روی یک ماشین پردازش میشود و امکان شکست کارها وجو ندارد.
8. تمامی کارها در لحظه زمانی صفر آماده پردازش نمی باشند و زمان های آزاد سازی متفاوتی دارند.
9. کارها از هم مستقل نمیباشند و بین آنها روابط پیش نیازی و پس نیازی وجود دارد.
10. هر کار نمیتواند روی هر ماشینی پردازش شود و مجموعهای از ماشینها میتوانند یک کار بخصوص را پردازش کنند.
11. زمان آماده سازی مربوط به یک کار نمیتواند قبل از زمان آزادسازی مربوط به آن کار انجام شود.
12. زمان آماده سازی مربوط به پس نیاز یک کار میتواند قبل از پایان یافتن پیش نیاز آن کار انجام شود.
1-4- ضرورت و اهداف پژوهش:
مسئله زمانبندی ماشینهای موازی نامرتبط یکی از کاربردیترین مسائلی است که امروزه تعداد زیادی از سازمانهای تولیدی و خدماتی با آن روبرو هستند. این موضوع در حالیست که تا به امروز تعداد پژوهشهای کمی در زمینه زمانبندی ماشینهای موازی نامرتبط وجود دارند که چندین محدودیت عملیاتی را همزمان در پژوهش خود در نظر گرفته باشند که این حقیقت کاربرد آنها را در محیطهای تولیدی واقعی محدود میسازد. به همین دلیل ما در این تحقیق سعی کردهایم تا با در نظر گرفتن محدودیت های عملیاتی مختلف این شکاف موجود در بین تئوری و عملیاتی بودن این گونه تحقیق ها را کاهش دهیم. از طرفی دیگر اکثریت پژوهشهای انجام شده تنها به دنبال بهینه سازی زمانبندی بر مبنای یک هدف هستند، ولی همانطور که میدانید امروزه اکثر سازمانها با بیش از یک هدف روبرو هستند. از اینرو در این تحقیق به منظور پوشش این خلا با در نظر گرفتن همزمان دو تابع هدف میانگین وزنی زمان در جریان کارها و میانگین وزنی دیرکرد کارها، سعی شده تا هزینههای ناشی از دیرکرد و نگهداری موجودی حین تولید34 را کاهش دهیم. در این تحقیق با در نظر گرفتن محدودیت های عملیاتی کاربردی و توابع هدف متداول در صنعت، اولا به دنبال هر چه نزیک کردن مسئله زمانبندی ماشینهای موازی نامرتبط به مسائل دنیای واقعی و در پی آن استفاده کارآمد از منابع و زمان، کاهش هزینه های ناشی از تولید و خدمات، جلب رضایت مشتریان و حفظ آنها و بالا بردن بهرهوری و کارایی سیستم هستیم.

فصل دوم
ادبیات تحقیق
2-1- مقدمه
در این تحقیق، مسئله زمان بندی ماشین های موازی نامرتبط با فرض وجود محدودیت های پیش نیازی کارها، زمان آماده سازی وابسته به توالی کارها و نوع ماشین ها، زمان های آماده به کار متفاوت و دسترسی محدود به ماشین ها با اهداف میانگین وزنی زمان در جریان کارها و میانگین وزنی دیرکرد کارها مورد مطالعه قرار می گیرد. با توجه به مسئله در نظر گرفته شده، در ادامه این فصل برآنیم تا مروری بر ادبیات موضوع مطرح در زمینه هایی که در این پایان نامه به آنها پرداخته شده است، بپردازیم. ابتدا به بررسی تحقیقات صورت گرفته در زمینه ماشین های موازی نامرتبط و در ادامه به بررسی محدودیت ها می پردازیم. و سپس، به بررسی مسائل چندهدفه با تمرکز بر روی الگوریتم های تکاملی NSGA-Π و MOACO می پردازیم. بدلیل گستردگی مطالب در ادبیات موضوع، در این تحقیق سعی بر آن است که در بخش بررسی به محدودیت ها، تحقیقاتی مورد بررسی قرار می گیرند که در حیطه ی مسئله زمان بندی ماشین های موازی به ویژه ماشین های موازی نامرتبط و یکسان می باشند.
2-2- ماشین های موازی نامرتبط
در سال های اخیر تحقیقات زیادی در زمینه ماشین های موازی با محدودیت های گوناگون صورت گرفته است اما یکی از اولین تحقیقات صورت گرفته در زمینه ماشین های موازی یکسان توسط مک ناتن [11] در اواخر دهه پنجاه میلادی صورت گرفته است. همچنین محققان دیگری همچون موکوتف [12] ، لام و ژینگ [13] و چنگ و سینگ [14] بررسی و مطالعاتی در زمینه ماشین های موازی یکسان انجام داده اند. حال به بررسی تعدادی از تحقیقاتی که در زمینه ماشین های موازی نامرتبط صورت گرفته است می پردازیم.
مسئله زمانیندی ماشین های موازی نامرتبط با هدف کمینه سازی بیشینه زمان تکمیل کارها حجم گسترده ای از تحقیقات در زمینه مسائل ماشین های موازی نامرتبط را به خود اختصاص داده است. هاروویتز و ساهنی [15] از رویکرد برنامه ریزی پویا برای مسئله زمانبندی دو ماشین موازی نامرتبط به هدف کمینه سازی بیشینه زمان تکمیل کارها استفاده کردند. گلس و همکاران [16] مسئله زمانبندی ماشین های موازی نامرتبط با هدف کمینه سازی بیشینه زمان تکمیل را مورد مطالعه قرار دادند و از سه الگوریتم فراابتکاری ژنتیک35، شبیه سازی تبرید36 و جستجوی ممنوع37 برای این مسئله ارائه دادند. مارتلو و همکاران [17] برای مسئله مشابه حد پایینی با استفاده از تکنیک آزادسازی لاگرانژ38 بدست آوردند و برای بهبود این حد پایین یک الگوریتم برش ارائه دادند که قسمت های نشدنی را از فضای جواب بدست آمده حذف می کرد. آن ها همچنین یک الگوریتم تقریبی برای حل این مسئله ارائه دادند و نتایج بدست آمده از این الگوریتم را با حد پایین بدست آمده مورد مقایسه قرار دادند. آدام پولوس و پاپیس [18] مسئله زمانبندی ماشین های موازی نامرتبط با هدف تعیین یک زمان تحویل مشخص برای تمامی کارها بطوریکه مجموع هزینه های ناشی از زود کرد و دیر کرد کارها و همین طور هزینه ناشی از تعیین زمان تحویل معین کمینه شوند. هزینه ای که به زمان تحویل تخصیص داده شده مربوط به تمایل شرکت به تحویل هر چه زودتر محصول به مشتریان با در نظر گرفتن تمام فاکتورهای رضایت مندی مشتری می باشد. آن ها برای این مسئله یک الگوریتم ابتکاری که در یک زمان چند جمله ای39 اجرا می شود، پیشنهاد دادند. سریواستاوا [19] مسئله مشابهی را مورد بررسی قرار داد و برای حل آن از الگوریتم جستجوی ممنوع استفاده نمود و ادعا کرد که الگوریتم ارائه شده قادر است برای مسائلی در مقیاس های کاربردی، جواب هایی با کیفیت خوب در مدت زمانی قابل قبول محاسبه نماید. لانسیا [20] یک الگوریتم دقیق شاخه و حد40 برای مسئله زمانبندی دو ماشین موازی نامرتبط با این فرض که کارها در ابتدای افق زمانبندی در دسترس نیستند و با هدف کمینه سازی بیشینه زمان تکمیل کارها پیشنهاد کردند. بانک و ورنر [21] مسئله زمانبندی ماشین های موازی نامرتبط را با هدف حداقل کردن مجموع وزنی دیرکرد و زودکرد مورد بررسی قرار گرفته است. در مسئله مورد بررسی کارها دارای زمان تحویل مشترک می باشند و همچنین تمامی کارها در زمان صفر در دسترس نیستند، به عبارت دیگر مسئله در محیط پویا مورد بررسی قرار گرفته است. در این پژوهش ابتدا چندین خصوصیت ساختاری توسعه پیدا کرده اند و سپس با توجه به ویژگی های حاصل شده الگوریتم های فرا ابتکاری برای حل مسئله پیشنهاد شده اند. لی آ او و همکاران [22] مسئله زمانبندی ماشین های موازی نامرتبط با هدف کمینه سازی مجموع وزنی دیرکرد کارها را در نظر گرفتند. آن ها یک حد پایین و یک حد بالا و همچنین یک الگوریتم شاخه و کران برای غلبه کردن بر این مسئله ارائه دادند. قیرادی و پاتز [23] برای مسئله مشابه یک الگوریتم ابتکاری ارائه نمودند که توانایی بدست آوردن پاسخ هایی با کیفیت خوب برای مسائلی با ابعاد بزرگ را دارد. لاگندران و سوبور [24] مسئله زمانبندی ماشین های موازی نامرتبط را مورد توجه قرار دادند. در مسئله در نظر گرفته شده، کارها و ماشین ها دارای زمان های آماده به کار متفاوت می باشند. در مسئله مذکور، تمهیداتی برای مجموعه ای از کارها در نظر گرفته شده است، بر این اساس کارها به دلیل داشتن اولویت بالا، موعد تحویل تنگ یا میزان بار کاری بالا می توانند شکسته شوند و بر روی چندین ماشین بصورت موازی پردازش شوند. در مطالعه انجام شده، زمان های آماده سازی به صورت مستقل از توالی در نظر گرفته شده بودند که در آن زمان آماده سازی کار بر روی ماشین با زمان پردازش کار بر روی همان ماشین مورد نظر گرفته شده است. کوا و همکاران [25] به طور همزمان مسئله انتخاب و زمانبندی ماشین های موازی نامرتبط را به منظور حداقل کردن هزینه های نگهداری41 ماشین ها و هزینه دیرکرد کارها مورد بررسی قرار دادند. آن ها برای غلبه بر این مسئله یک مدل ریاضی ترکیبی ارائه دادند. از آنجا که حل این مسئله با ابعاد بزرگ توسط این مدل امکان پذیر نمی باشد، آن ها یک الگوریتم جستجوی ابتکاری مبتنی بر الگوریتم جستجوی ممنوع برای یافتن پاسخ های بهینه و یا نزدیک به بهینه پیشنهاد کردند.
2-3- محدودیت پیش نیازی کارها
از جمله اولین تحقیقاتی که در زمینه ماشینهای موازی یکسان با محدودیت های پیشنیازی کارها انجام شده میتوان به هو [26] اشاره نمود. این محقق با ساده سازی مسئله بدین صورت که کارها دارای زمان پردازش واحد میباشند و گراف پیشنیازی کارها بصورت یک درخت42 می باشد، الگوریتمی بهنام مسیر بحرانیCP 43 پیشنهاد دادند که توانایی بدست آوردن جواب بهینه را برای مسائل P_m |P_j=1,outtree|Cmax┤ و P_m |P_j=1,intree|Cmax┤ دارند. این قانون بالاترین اولویت را به کاری میدهد که در راس طولانیترین رشته کارها در گراف پیش نیازی باشد. یولمن [27] اثبات کرد که مسئله زمان بندی کارها روی ماشین های موازی یکسان با روابط پیش نیازی دلخواه و زمان های پردازشی واحد بطور کامل غیر چند جملهای میباشد. بعد ها گراهام [28] الگوریتم تقریبی44 خوبی با نسبت عملکردی 2-1/m برای حل مسئله P_m |prec|Cmax┤ پیشنهاد کرد. دو و همکاران [29] اثبات کردند که که مسئله زمانبندی کارها روی دو ماشین موازی یکسان با روابط پیش نیازی بصورت درخت و زمان های پردازشی کاملاً دلخواه بطور قویاً غیر چندجملهای میباشد. بروکر و همکارانش با توسعه الگوریتم مسیر بحرانی توانستند الگوریتمی برای حل بهینه مساله P_m |P_j=1,intree|Lmax┤ پیشنهاد کنند و همین طور اثبات کردند که مساله P_m |P_j=1,outtree|Lmax┤ قویاً NP-hard است. هویت مونت و همکاران [30] یک تکنیک آزادسازی لاگرانژ برای حل مساله زمانبندی ماشین های موازی یکسان با محدودیت های پیش نیازی ساده با هدف کمینه سازی مجموع دیکرد به توان دو کارها45 پیشنهاد کردند. با توجه به مرور ادبیات انجام تا سال 1997 میلادی هیچ گونه تحقیقی روی زمان بندی ماشین های موازی نامرتبط که محدودیت های پیش نیازی را در نظر گرفته باشند صورت نگرفته است. هرمن و همکارانشان [31] اولین کسانی بودند که به بررسی مساله R_m |chain|Cmax┤ پرداختند. آنها سه الگوریتم ابتکاری و یک الگوریتم بر مبنای شبیه سازی تبرید برای بهبود حل ها، ارائه کردند. آنها برای ارزیابی عملکرد الگوریتم های پیشنهادی خودشان، سه حد پایین برای این مساله ارائه کردند که نتایج بدست آمده حاکی از کارا بودن الگوریتم های پیشنهادی آنها بوده است.

دسته بندی : پایان نامه ارشد

پاسخ دهید