زمان نصب ماشین نمایانگر عملیاتی میباشد که به منظور آمادهسازی یک ماشین برای پردازش کارها بر روی آن صورت میپذیرد. عملیاتی نظیر تنظیم و اصلاح ابزارها18، نصب جیگها19 و فیکسچرها20، تمیزکاری21 و … از این قبیل محسوب میشوند. در ادبیات تحقیق مسائل زمانبندی، زمان نصب ماشین برای مدتها نادیده و یا جزئی از زمان پردازش کارها در نظر گرفته میشد. این وضعیت شاید در برخی از موارد قابل توجیه باشد اما بسیاری از مسائل زمانبندی نیازمند در نظرگرفتن زمان نصب به صورت مجزا از زمان پردازش میباشند. به طور معمول، مسائل زمانبندی با در نظر گرفتن نصب ماشین به دو دسته کلی تقسیم میشوند: در دسته اول زمان نصب تنها به نوع کاری که بر روی ماشین پردازش میشود بستگی دارد که اصطلاحاً زمان نصب مستقل از توالی22 نامیده میشود و در دسته دوم زمان نصب علاوه بر نوع کاری که بر روی ماشین پردازش خواهد شد، به کار قبلی که بر روی آن ماشین پردازش شده نیز بستگی دارد و به آن زمان نصب وابسته به توالی23 اطلاق میشود.
اهمیت تلقی زمان نصب به صورت مجزا از زمانهای پردازش کارها در تحقیقات مختلفی بررسی شده است. الین [18] تأثیر فرآیندهای نصب وابسته به توالی را در افزایش تولید و ورتمن[66] اهمیت آنها را در مدیریت ظرفیت تولید بررسی نمودند. کراجفسکی وهمکارانش[40] فاکتورهایی را که در سیستمهای تولیدی دارای بیشترین تأثیر بر روی عملکرد هستند، بررسی نمودند. نتایج بدستآمده حاکی از آن بود که بدون توجه به نوع سیستم تولیدی مورد استفاده، کاهش همزمان زمانهای نصب و اندازههای انباشته مؤثرترین راه برای کاهش ذخیره انبار و بهبود خدمات مشتری میباشد.
ملاحظه عملیات نصب در صنایع مختلف تولیدی یا خدماتی نظیر الکترونیک، شیمیایی، نساجی، داروسازی، سرامیکسازی، پرردازش اطلاعات و … به چشم میخورد. برونو و داونی[12] یک سیستم کامپیوتری را شرح میدهند که در آن فعالیت کامپیوتری بعدی نیازمند کامپایلری غیر از کامپایلر موجود در حافظه میباشد، یک زمان نصب برای بارگذاری کامپایلر جدید در حافظه به سیستم تحمیل میشود. آندرس و همکارانش[6] یک مسأله تولید گروهی را در صنعت سرامیکسازی بررسی و آن را در سیستم زمانبندی جریان کارگاهی منعطف با محدودیت زمان نصب وابسته به توالی مدلسازی نمودند. آنها خاطرنشان مینمایند که هدف این نوع مسائل کاهش زمانهای نصب به منظور کاهش زمان تولید میباشد. مطالعات مشابهی[10,57,65] در تولید نیمههادیها، صنایع شیمیایی و داروسازی وجود دارد.
در ادامه مهمترین مطالعات صورت گرفته در زمینه مسائل زمانبندی با محدودیتهای زمان نصب وابسته به توالی در هر کدام از محیطهای کارگاهی تک ماشینه،جریان کارگاهی و ماشینهای موازی به طور جداگانه بررسی میشوند.
2-4-1. مسائل تکماشینه
انواع مدلها در دنیای واقعی در حیطه کار زمانبندی وجود دارد، که یکی از این مدلها، مدل برنامهریزی تولید تکماشینه است. در این مدل تنها یک ماشین (منبع سرویس دهنده) در دسترس است و کارها (محصولات) باید روی آن ماشین پردازش شوند. به عبارت دیگر، ماشین در هر لحظه قادر است تنها یکی از کارها را پردازش کند.
مسائل تک ماشینه با محدودیت زمان نصب ماشین وابسته به توالی کارها و تابع هدف کمینهسازی زمان تکمیل کار بیشینه، معادل کمینهسازی زمان نصب کل میباشند و معمولاً از این نوع مسائل با عنوان مسأله فروشنده دورهگرد 24یاد میشود. در یکی از اولین تحقیقات گلیمور و گوموری[25] مسأله تکماشینه را با تابع هدف هزینه نصب کل و محدودیت زمان نصب ماشین وابسته به توالی کارها مدلسازی و حل نمودند. بورستل[13] برای یک تابع هزینه شامل زمان نصب کل یک روش حل ابتکاری را بکار گرفتهاست که در آن از الگوریتم شاخه و کران25 به عنوان رویه جستجو استفاده شده است. بیانکو و همکارانش[10] در مسألهای با تابع هدف زمان تکمیل کار بیشینه و محدودیت زمان آزادسازی26 کارها و زمان نصب با استفاده از برنامهریزی خطی آمیخته27 فرمولسازی نموده و یک روش ابتکاری برای حل آن ارائه نمودند. کیم و همکاران[39] و تان و ناراسیمهان[59] به ترتیب یک روش ترکیبی با استفاده از شبکههای عصبی و تبرید شبیهسازی شده برای بهینهسازی زمان تأخیر کل وزنی ارائه نمودند که در آنها زمان محاسباتی سایر الگوریتمهای موجود در ادبیات تحقیق به چالش کشیده شدهاست.
روبین و راگتز [51] یک روش جستجو با استفاده از الگوریتم ژنتیک برای مسألهای با محدودیت زمان نصب و تابع هدف زمان دیرکرد کل ارائه نمودند. ونگ و ونگ[64] مسأله مشابهی را با اختصاص هزینه به زمان دیرکرد و زودکرد و همچنین زمان نصب مجموع، با استفاده از یک الگوریتم ژنتیک ترکیبی حل نمودند و به جوابهای بهینه با کیفیت بهتر نسبت به الگوریتمهای ژنتیک کلاسیک دست یافتند. ارن و گونر[17] مسأله را با تابع هدف زمان تکمیل کار وزنی کل به علاوه زمان دیرکرد کل بررسی نمودند. آنها برای مسأله یک مدل برنامهریزی عددصحیح طراحی نموده و با استفاده از یک روش ابتکاری ساده یک جواب اولیه برای الگوریتم جستجوی ممنوع خود تولید کردند.
در جدیدترین تحقیقات صورت گرفته در مسائل تکماشینه با محدودیت زمان نصب، آرویو و همکارانش[7] سه الگوریتم چندهدفه بر مبنای روش جستجوی همسایگی متغیر را برای حل مسألهای با تابع هدف زمانهای زودکرد و دیرکرد وزنی مقایسه نمودند. آنها دو رویه شمارشی برای بهبود روش جستجوی همسایگی متغیر ارائه نمودند و جوابهای بدستآمده از این روش را بهبود بخشیدند.
سیود و همکارانش[56] ترکیبی از الگوریتم ژنتیک، الگوریتمهای تکاملی چند هدفه و الگوریتم کلونی مورچگان را برای حل مسألهای با تابع هدف زمان تأخیر کل بکار گرفتند. نتایج محاسباتی در این تحقیق کارایی الگوریتم ترکیبی ارائه شده نسبت به بسیاری از روشهای موجود در تحقیقات دیگر را نشان میدهد.
در جدول(2-1) خلاصهای از مطالب ارائه شده در این بخش نمایش داده شده است.
جدول2-1. مسائل تکماشینه با محدودیت زمان نصب ماشین
رویکردهاتوابع ومحدودیتها نویسندگانبرنامهریزی عددصحیحTSTگیلمور و گوموری
روش ابتکاری بر مبنای الگوریتم شاخه و کرانTSTبروستلبرنامهریزی صفر و یک
TSC, TSTتاهابرنامهریزی عددصحیح آمیختهC_max (r_j)بیانکو و همکاران
الگوریتم شاخه و کرانL_max (Prec)اوزوی و همکاران
روش ترکیبی بر مبنای شبکههای عصبی مصنوعی و قواعد توزیع∑▒W_j T_jکیم و همکارانالگوریتم تبرید شبیه سازی شده∑▒W_j T_j, TSCتان و ناراسیمهان
الگوریتم ژنتیک
∑▒T_j روبین و راگتزبرنامهریزی عددصحیح آمیختهf(∑▒W_j T_j, ∑▒W_j E_j, TSC)
کیت و همکاران
الگوریتم ژنتیک ترکیبیf(∑▒T_j , ∑▒E_j , TST)ونگ و ونگالگوریتم جستجوی ممنوع
λ∑▒C_j +(1-λ)∑▒T_j ارن و گونرروش جستجوی همسایگی متغیر

∑▒〖W_j E_j 〗+∑▒〖〖W’〗_j T_j 〗آریو و همکارانترکیبی از الگوریتم ژنتیک، الگوریتمهای تکاملی چند هدفه و الگوریتم کلونی مورچگان
∑▒T_j سیو و همکاران 2-4-2. مسائل ماشینهای موازی
در ادبیات تحقیق زمانبندی ماشینهای موازی الگوریتمهای ابتکاری و فراابتکاری مختلفی به چشم میخورد که بخش زیادی از آن به ماشینهای موازی یکسان و یکنواخت مربوط میشود. گوینت و داساچوی[28] مسأله زمانبندی ماشینهای موازی یکسان با محدودیت زمان نصب وابسته به توالی با تابع هدف زمان پایان کار ماکسیمم با استفاده از یک روش ابتکاری بر مبنای روش مجارستانی28را بررسی نمودهاند.
کیم و شین[38] یک الگوریتم جستجوی ممنوع را برای مسأله مشابهی با تابع هدف زمان تأخیر ماکسیمم ارائه کردند. این الگوریتم تعداد جستجوها را بدون حذف جوابها به طور قابل ملاحظهای کاهش میدهد. همچین، فاولر و همکارانش[22] یک الگوریتم ژنتیک ترکیبی را در مسأله مشابهی برای توابع هدف مختلف شامل زمان پایان کار بیشینه، زمان تکمیل کار وزنی کل و زمان دیرکرد وزنی کل بکار گرفتند. این الگوریتم کارها را به ماشینها اختصاص میدهد و از قوانین توزیع برای زمانبندی ماشینها استفاده میکند. نتایج محاسباتی الگوریتم برای هر سه نوع معیار بهینهسازی ذکر شده، عملکرد بهتر آن را نسبت به الگوریتمهای قبلی نشان میدهد.
با وجود مطالعات فراوان صورت گرفته در زمینه ماشینهای موازی یکسان، مسائل زمانبندی ماشینهای موازی نامرتبط کمتر مورد توجه قرار گرفتهاند. این موضوع با در نظر گرفتن محدودیت زمان نصب ماشین بیش از پیش به چشم میآید. در ادامه تعدادی از مهمترین تحقیقات ارائه شده در این زمینه آدرسدهی میشوند:
ژو و هیدی[67] مسأله زمانبندی ماشینهای موازی نامرتبط را با محدودیت زمان نصب وابسته به توالی کارها و تابع هدف مجموع زمانهای دیرکرد و زودکرد وزنی ارائه کردند. آنها یک مدل برنامهریزی عددصحیح برای این مسأله پیشنهاد مینمایند که به اندازه نه کار و سه ماشین در زمان محسباتی معقول به جواب بهینه میرسد.

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

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

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

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

ونگ و همکاران[65] مسأله را با تابع هدف زمان پایان کار وزنی کل آدرسدهی نمودند. آنها هفت روش ابتکاری ساده را از طریق بررسی نتایج محاسباتی با یکدیگر مقایسه نموده و یکی از آنها را به عنوان بهترین روش انتخاب مینمایند. این روش هریک از کارها را بر اساس کوچکترین نرخ زمان پردازش به علاوه زمان نصب نسبت به وزن کار در تابع هدف به ماشینها اختصاص میدهد. آکیول و همکارانش[2] با استفاده از شبکههای عصبی مصنوعی و روش تابع جریمه به حل مسألهای با تابع هدف زمانهای زودکرد و دیرکرد وزنی پرداختند. نتایج بدستآمده نشان میدهد که این روش به یک جواب بهینه مناسب دست مییابد بطوریکه انگیزه کاربرد آن در مسائل با اندازه بزرگتر را ایجاد میکند.
در جدول(2-2) خلاصهای از مطالب ارائه شده در این بخش نمایش داده شده است.
جدول2-2. مسائل ماشینهای موازی با محدودیت زمان نصب ماشین
رویکردهاتوابع ومحدودیتهانویسندگانیک روش ابتکاری بر مبنای روش مجارستانیP| 〖ST〗_sd|C_maxگوینت و داساچویالگوریتم جستجوی ممنوعP| 〖ST〗_sd|L_maxکیم و شینالگوریتم ژنتیکP| 〖ST〗_sd , r_j|C_max ,∑▒〖W_j C_j 〗,∑▒〖W_j T_j 〗فاولر و همکارانبرنامهریزی عددصحیح آمیختهR | 〖ST〗_SD, r_j|∑▒〖W_j E_j 〗+∑▒〖W_j T_j 〗ژو و هیدیبرنامه ریزی خطیR| 〖ST〗_sd|∑▒〖W_j C_j 〗ونگ و همکارانشبکه عصبی مصنوعی R| 〖ST〗_sd|∑▒〖e_j E_j 〗+∑▒〖t_j T_j 〗آکیول و همکارانتبرید شبیهسازی شدهR| 〖ST〗_sd, d_j |∑▒T_j چن
2-4-3. مسائل جریان کارگاهی:
در یک مسأله جریان کارگاهی m ماشینه، تعداد m مرحله عملیات به صورت متوالی بر روی کارها صورت میگیرد. هر کدام از کارها بر روی همه ماشینها با توالی یکسان پردازش میشوند. در مسائل جریان کارگاهی منعطف حداقل در یکی از مراحل بیش از یک ماشین برای پردازش کارها وجود دارد و در واقع در این مرحله خاص، یکی از انواع مختلف مسائل ماشینهای موازی به وقوع میپیوندد.
مسأله جریان کارگاهی برای اولین بار توسط جانسون[36] با دو ماشین و تابع هدف زمان تکمیل کار بیشینه بررسی شد. تمامی مدلهای موجود در تحقیقات بعدی توسعه این مدل بشمار میآیند. در مسائل کلاسیک یک بافر نامحدود29 که کارها روی ماشینها یا در بین دو ماشین متوالی در حال انتظار باشند، مفروض است. با این وجود در مسائل جریان کارگاهی بدون انتظار30 این فرض منظور نمیشود و کارها بدون وقفه از ابتدا تا انتهای زمان پردازش خود بر روی ماشینها پردازش میشوند [30]. زمانیکه بافر واسطه بین ماشینها وجود ندارد، مسائل بدون بافر31 به وجود میآیند. مسائل بدون انتظار و مسائل بدون بافر با ماشین در حالتی که زمانهای نصب ماشین جزئی از زمان پردازش کارها هستند، معادل هم میباشند. برای حالت زمان نصب مجزا دو حالت مختلف برای مسائل بدون بافر وجود دارد: در حالت اول تا زمانی که کار جاری ماشین اول را ترک نکند، به کار بعدی اجازه نصب داده نمیشود و در حالت دوم به محض این که پردازش کار جاری بر روی ماشین اول به اتمام برسد، نصب کار بعدی آغاز میشود[3] .
کروین اسوگبو [16] مسأله جریان کارگاهی دو ماشینه را با توجه به معیار زمان تکمیل کار بیشینه و محدودیت زمان نصب وابسته به توالی بر روی ماشین اول و زمان نصب مستقل از توالی بر روی ماشین دوم و بالعکس،آدرسدهی نمودند.آنها با استفاده از زمانبندی جایگشتی به جواب بهینه دست یافتند و همچنین برای این مسأله یک مدل برنامهریزی پویا طراحی نمودند.گوپتا و دارو [29] مسأله مشابهی را با محدودیت زمان وابسته به توالی برای هر دو ماشین بررسی نمودند و خاطرنشان نمودند که مسأله حتی برای حالت یک ماشین با زمان نصب وابسته به توالی در کلاس مسائلStrongly NP-hard قرار میگیرد.ریوس مرکادو و بارد [50] برای مسأله جریان کارگاهی با m ماشین و تابع هدف زمان تکمیل کار بیشینه یک الگوریتم شاخه و کران به همراه حد بالا و پائین 32و معیار حذف مغلوب ارائه نمودند.
در دهههای اخیر مسائل زمانبندی جریان کارگاهی منعطف توجه بسیاری از محققان را به خود جلب نمودهاست. دلیل این امر را میتوان ماهیت نسبتاً پیچیده این مسائل و کاربرد فراوان آنها در محیط صنعتی دانست [49]. این نوع مسائل با محدودیت زمان نصب ماشین وابسته به توالی در کلاس Np-hard قرار میگیرند [41]. کرز و آسکین [42] با توجه به دشواری حل مسأله با استفاده از برنامهریزی عددصحیح، یک الگوریتم ژنتیک با کلیدهای تصادفی33 را برای حل مسأله توسعه دادند. آنها حدهای پایین را برای مسأله تولید و از آن برای ارزیابی الگوریتم استفاده نمودند. جانگواتاکی و همکارانش [37] مسأله را در حالت ماشینهای نامرتبط و با تابع هدف مجموع وزنی تعداد کارهای با تأخیر و زمان تکمیل کار بیشینه مورد توجه قرار دادند.آنها الگوریتمهای ژنتیک و تبرید شبیهسازی شده بکار رفته در مسائل جریان کارگاهی را برای حالت منعطف تطابق دادند و با ارائه نتایج محاسباتی خاطرنشان نمودند که الگوریتم ژنتیک عملکرد مناسبتری نسبت به الگوریتم تبرید شبیهسازی شده از خود نشان میدهد.
در یکی از آخرین تحقیقات صورت گرفته در مسائل جریان کارگاهی منعطف، بهنامیان و همکارانش [9] ترکیبی از الگوریتم ژنتیک و روش جستجوی همسایگی متغیر را برای یک تابع دو هدفه با معیارهای زمان تکمیل کار بیشینه و هزینههای تخصیص منابع بکار گرفتند و کارایی الگوریتم پیشنهادی خود را برای اندازههای بزرگ مسأله نشان دادند.
زندیه و غلامی [47] در زمانبندی جریان کارگاهی منعطف با زمان آمادهسازی وابسته به توالی به منظور کمینهسازی زمان پایان کار ماکسیمم،از الگوریتم ایمنی34 استفاده نمودهاند.بدین ترتیب که آنها یک الگوریتم فرا ابتکاری35 مبتنی بر سیستم ایمنی توسعه دادند و برای ارزیابی این الگوریتم، دادههایی مطابق با تحقیق کرز و آسکین [42] را تولید و نتایج را با الگوریتم پیشنهادی خود مقایسه نمودند. جدول (2-3) خلاصهای از آنچه که در این بخش عنوان شد را نمایش میدهد.
جدول2-3. مسائل جریان کارگاهی با محدودیت زمان نصب ماشین
رویکردهاتوابع و محدودیتهانویسندگانبرنامهریزی پویا و زمانبندی جایگشتیF_2| 〖ST〗_sd|C_maxکروین و اسوگبوبرنامهریزی عددصحیحF_2| 〖ST〗_sd|C_maxگوپتا و داروالگوریتم شاخه و کرانF_m| 〖ST〗_sd|C_maxمرکادو و بردالگوریتم ژنتیک با کلیدهای تصادفیFF_m| 〖ST〗_sd|C_maxکروز و آسکینالگوریتم سیستم ایمنیFF_m| 〖ST〗_sd|C_maxزندیه و همکارانالگوریتم ژنتیک و الگوریتم تبرید شبیهسازی شدهFF_m| 〖ST〗_sd|〖λC〗_max+(1-λ)∑▒U_j جانگواتانکیت و همکارانالگوریتم تبرید شبیهسازی شده و روش جستجوی محلیFF_m| 〖ST〗_sd|(∑▒C_j ,∑▒T_j )نادری وهمکارانالگوریتم ژنتیک و روش جستجوی همسایگی متغیرFF_m| 〖ST〗_sd|C_max,f(ST)بهنامیان و همکاران
2-5. دسترسی محدود به ماشینها
مسائل زمانبندی با محدودیت دسترسی محدود به ماشینها با عناوینی چون زمانبندی با محدودیت مجموعههای پردازشی36، محدودیت دسترسی37 و همچنین دسترسی محدود به ماشینها38 ارائه میشوند[44] . در این مسائل به هریک از کارها یک زیر مجموعه از مجموعه ماشینها با عنوان مجموعه پردازشی39 نسبت داده میشود بطوریکه هر کار تنها بر روی ماشینهای موجود در مجموعه پردازشی خود میتواند پردازش شود. در یک نگرش کلی به محدودیت دسترسی محدود به ماشینها، هر کدام از مجموعههای پردازشی مربوط به وضعیتی میباشد که در آن کارها دارای ویژگیهایی هستند که تنها بخشی از ماشینها قادر به پردازش آنها میباشند. وایراکتاراکیس[62] یکی از این نوع مسائل را به منظور مدیریت بازدهی اتاقهای عمل بیمارستان مدلسازی نمودند. یک اتاق عمل معمولاً با تجهیزات مدرنی با ارزش میلیونها دلار تجهیز میشود. با توجه به میزان تجهیزات موجود، هر اتاق تنها برای بخشی از بیماران قابل دسترسی است و کمینهسازی زمان پایان کار بیشینه بهرهوری اتاقهای عمل را بهبود میبخشد. گلاس و کلرر [26] مسأله تخصیص پردازندههای یک رایانه به برنامههای کاربردی را به صورت یک مدل زمانبندی با مجموعههای پردازشی ارائه نمودند.پردازندهها دارای سرعت یکسان و ظرفیت حافظه متفاوت هستند.هر کدام از برنامهها برای اجرا به میزان مشخصی از حافظه پردازنده نیاز دارند و بدین ترتیب تنها توسط پردازندههای محدودی میتوانند پردازش شوند.
لی و لیونگ [43] زمانبندی ماشینهای موازی نامرتبط را با محدودیت دسترسی محدود به ماشینها با تمرکز بر روی تابع هدف پایان کار بیشینه بررسی نمودند. لوگندران و سوبر [45] یک الگوریتم ابتکاری بر مبنای الگوریتم جستجوی ممنوع را در مسأله مشابهی با تابع هدف زمان دیرکرد وزنی کل بکارگیری و عملکرد آن را به صورت تجربی ارائه نمودند.
رویز و ماروتو [52] شکاف بین مفهوم تئوری و عملی مسأله زمانبندی جریان کارگاهی را تحلیل نموده و برای این مسأله با فرض ماشینهای موازی نامرتبط در هر مرحله، محدودیتهای زمان نصب وابسته به توالی و دسترسی محدود به ماشین، متاهیورستیکی به شکل الگوریتم ژنتیک ارائه کردند. رویز و استاتزل [53] یک مدل ریاضی و الگوریتمی ابتکاری برای جریان کارگاهی منعطف با تابع هدف زمان پایان کار ماکسیمم و زمان دیرکرد وزنی با فرض ماشینهای موازی نامرتبط در هر مرحله، محدودیتهای زمان دسترسی به ماشین و دسترسی محدود به ماشین ارائه کردند. شین و همکاران [55] مسأله زمانبندی n کار مستقل بر روی m ماشین یکسان با محدودیتهای زمان دسترسی و دسترسی محدود به ماشین با تابع هدف کمینهسازی ماکسیمم تأخیرها مورد بررسی قرار دادند که در آن ماشین ممکن است به دلیل خرابی در دسترس نباشد.
2-6. خرابی ماشین
علی اللهوردی و جان میتنتال [4] مسأله زمانبندی جریان کارگاهی دو ماشینه با هدف کمینهسازی زمان پایان کار کل و محدودیت خرابی تصادفی ماشین را بررسی کردند.آنها ابتدا نشان دادند که کارها باید با توالی یکسانی روی هر ماشین پردازش شوند و پس از ارائه یک معیار کاهش برای برای بهینهسازی تابع هدف با احتمال 1,نشان دادند که تحت شرایط مناسب الگوریتم جانسون به طور احتمالی زمان تکمیل کار کل را کمینه میکند.
جیان زیونگ و لی نینگ زینگ [34] زمانبندی قوی40 مسأله کارکارگاهی منعطف چند هدفه با خرابی ماشین تصادفی را مورد بررسی قرار دادند.آنها دو هدف زمان پایان کار و قوت41 را همزمان در نظر گرفتند و یک الگوریتم تکاملی چند هدفه ارائه دادند.جان برگ و کوین گلازبروک [35] تأثیرات خرابی ماشین روی زمانبندی احتمالی را بررسی نمودند و یک استراتژی برای ارزیابی این تأثیرات ارائه دادند.
علی اللهوردی [5] به بررسی مسأله زمانبندی جریان کارگاهی دو ماشینه با تابع هدف کمینهسازی ماکسیمم تأخیر و محدودیت خرابی تصادفی ماشین پرداخت و نشان داد که تحت شرایط مناسب سیاست بزرگترین زمان پردازش(LPT)وقتیکه فقط اولین ماشین دارای محدودیت خرابی باشد با احتمال 1 تابع هدف را کمینه میکند.همچنین نشان داد هنگامیکه فقط دومین ماشین دارای چنین محدودیتی باشد سیاست کمترین زمان پردازش (SPT) تابع هدف را بهینه میکند.
نصر الحینای و المکاوی [48] زمانبندی مسأله کار کارگاهی منعطف پایدار و نیرومند42 با خرابی ماشین تصادفی را بررسی کردند.آنها یک الگوریتم ژنتیک مختلط دو مرحلهای(HGA) برای تولید زمانبندی پیشگویانه ارائه دادند.
چانگ یی لی و چن سین لین [15] زمانبندی مسأله تک ماشینه را با فرض زمان پردازش قطعی و خرابی ماشین مطالعه کردند.آنها این مسأله را با تابع هدفهای متفاوتی مانند زمان پایان کار پیش بینی شده,زمان تکمیل پیشبینی شده کل,ماکسیمم تأخیر پیشبینی شده و تأخیر ماکسیمم پیشبینی شده را به ترتیب بررسی نمودند.
علی اللهوردی و جان میتنتال [1] مسأله زمانبندی جریان کارگاهی با تابع هدف کمینهسازی زمان پایان کار کل و میانگین زمان جریان و محدودیت خرابی ماشین را بررسی کردند و نشان دادند توالی بهینه برای تابع هدف زمان پایان کار کل هنگامی حاصل میشود که فقط یکی از دو ماشین دارای محدودیت خرابی باشد و برای تابع هدف میانگین زمان جریان وقتیکه هر دو ماشین دارای محدودیت خرابی تصادفی باشند,توالی بهینه بدست میآید.
احرام سفری و سید جعفر سجادی [20] یک روش مختلط43 برای زمانبندی جریانهای کارگاهی با هدف کمینه سازی زمان تکمیل کل پیشبینی شده با فرض خرابی ماشین و محدودیت نگهداری بر مبنای وضعیت ارائه کردند.آنها یک استراژی نگهداری بر مبنای وضعیت را در نظر گرفتند که میتواند در بیشتر صنایع استفاده شود و الگوریتمی ارائه کردند که برای حالت جریان کارگاهی جمعناپذیر طراحی شده,بطوریکه پردازش کارها بعد از نگهداری پیشگیرانه از ابتدا شروع میشود.آنها یک الگوریتم مختلط بر اساس الگوریتم ژنتیک و شبیهسازی تبرید ارائه دادند و از روش تاگوچی برای تنظیم پارامتر استفاده نمودند.
لیائو و چن [14] یک کارخانه نساجی که خرابی ماشین در آن بهکثرت اتفاق میافتد را مطالعه نمودند و هیوریستیکی برای ایجاد زمان راهاندازی طولانیتر(یا برابر,زمان بیکاری طولانیتر) برای کاهش نرخ خرابی ماشین توسعه دادند.آنها دادههای حقیقی کارخانه را برای اثبات اثربخشی هیوریستیک استفاده کردند و عملکرد آن را با الگوریتم شاخه و کران مقایسه نمودند.
2-7. زمانهای زودکرد و دیرکرد
با بکارگیری موفقیتآمیز مفاهیم تولید بهموقع در سیستمهای تولیدی، زمانهای زودکرد کارها همانند زمانهای دیرکرد در کانون توجه قرار گرفتند. در یک محیط زمانبندی بر مبنای تولید به موقع کارهایی که پردازش آنها زودتر از موعد تحویل به اتمام رسیده باشد، تا رسیدن موعد تحویل در انبار محصولات نهایی نگهداری میشوند، در حالی که کارهایی که پس از موعد تحویل به اتمام رسیدهاند، موجب عدم رضایت مشتری از تأخیر در تحویل میشوند. زودکرد و دیرکرد هر کدام از کارها میتواند میزان اهمیت متفاوتی نسبت به سایر کارها داشته باشد و با اختصاص ضرایب وزنی به زورکرد و دیرکرد کارها در معیارهای بهینهسازی این میزان اهمیت ملاحظه میشود.
در ادامه مهمترین تحقیقات صورت گرفته در زمینه زمانبندی ماشینهای موازی با معیار بهینهسازی زمانهای زودکرد و دیرکرد بررسی میشود:
در یکی از اولین تحقیقات، هال [31] معیار زمانهای زودکرد و دیرکرد را در مسأله ماشینهای موازی یکسان با موعد تحویل مشترک برای تمام کارها بکار برد. الگوریتم پیشنهادی وی ماشینی که پردازش کار را به اتمام رسانده انتخاب و کاری که بیشترین زمان پردازش را در بین کارهای باقیمانده دارد به آن اختصاص میدهد. با این روند تمامی کارها به ماشینها اختصاص مییابند. امونز [21] این رویکرد را در مسألهای با وزنهای متفاوت زمانهای زودکرد و دیرکرد ارائه نمودهاست. در این تحقیق یک وزن مشترک برای زمانهای دیرکرد و یک وزن مشترک برای زمانهای زودکرد تمامی کارها منظور شدهاست. ژو و هیدی [67] مسأله زمانبندی ماشینهای موازی نامرتبط با وزنهای زودکرد و دیرکرد و موعدهای تحویل متمایز را با روش برنامهریزی عددصحیح مدلسازی نمودند. مدل ارائه شده توسط آنها جوابهای بهینه لازم برای اعتبارسنجی الگوریتمهای تقریبی در مسائل مشابه را ارائه میکند. بهنامیان و همکارانش [9] یک الگوریتم ترکیبی را به منظور بهینهسازی یک تابع چندهدفه شامل زمان تکمیل بیشینه و مجموع زمانهای زودکرد و دیرکرد ارائه نمودند. نتایج محاسباتی الگوریتمهای پیشنهادی آنها حاکی از آن است که این الگوریتم جوابهای بهینه پارتو44 مناسبی تولید میکند. توکلیمقدم و همکارانش [61] یک الگوریتم ژنتیک را در مسألهای با تابع هدف چندمعیاره شامل زمانهای زودکرد و دیرکرد وزنی به علاوه هزینه نصب ماشینها بکار گرفتند و نتایج محاسباتی را برای تعدادی مسأله آزمایشی ارائه نمودند. لیتاو و همکارانش [60] مسأله ماشینهای موازی نامرتبط با آثار خرابی و فعالیتهای نگهداری را برای کمینهسازی مجموع هزینههای زودکردها و دیرکردها بطور همزمان بررسی کردند. هدف آنها تعیین همزمان موقعیت بهینه فعالیتهای نگهداری، موعد تحویل مشترک بهینه برای همه کارها و زمانبندی بهینه برای کمینهسازی مجموع هزینههای زودکردها و دیرکردها میباشد. برای تعداد ثابت ماشینها، یک الگوریتم با زمان حل چند جملهای ارائه کردند.
2-8. جمعبندی
در این فصل ابتدا مسائل زمانبندی با استفاده سیستم استاندارد سهنمادی طبقهبندی شدند. پس از آن به معرفی ادبیات تحقیق زمانبندی ماشینهای موازی پرداخته شد. در ادامه به منظور مرور ادبیات مرتبط با مسأله مورد بررسی این تحقیق، مطالعات صورت گرفته به تفکیک محدودیتها و تابع هدف مسأله در بخشهای جداگانهای بررسی شدند. با توجه به بررسی انجام شده، تحقیق حاضر از دو جنبه صورت مسأله و روش حل نسبت به تحقیقات پیشین دارای نوآوری میباشد.

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

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

پاسخ دهید