تحقیق رایگان درمورد الگوریتم ژنتیک، ادبیات تحقیق، جستجوی محلی

مطالعات فراوانی وجود دارند که بر مباحث تعیین اندازه های انباشته87 و دستهبندی کارها با هدف تعیین تعداد اقتصادی دستههای کاری تمرکز کردهاند. اکثر این مطالعات محیطهایی را بررسی میکنند که در آنها فرآیندهای کاری و فرآیندهای دوبارهکاری روی یک نوع ماشین انجام میگیرند ]34-28[. برای مثال، ایندرفورت و همکاران ]32[ مسئلهای را بررسی کردند که در آن محصولات یکسان در قالب دستههای کاری بر روی یک ماشین تولید میشوند. فرآیند پردازش هر دسته به دو مرحله تقسیم میشود. در مرحله اول، تمام کارهای یک دسته پردازش میشوند و محصولات با سطح کیفی قابل قبول وارد انبار میشوند. در مرحله دوم، محصولات معیوب متعلق به همان دسته، دوبارهکاری میشوند. آنها همچنین برای پردازش مجدد اقلام بی کیفیت یک محدودیت زمانی در نظر گرفتند. در مقابل، گریبکوفسکایا و همکاران ]34[ مسئله تولید محصولات مشابه بر روی دو ماشین را مورد بررسی قرار دادند. بدین صورت که فرآیندهای کاری88 روی ماشین اول صورت میپذیرد. سپس، محصولات تولیدی توسط ماشین اول در قالب دستههای متشکل از محصولات از لحاظ کیفیت کنترل میشوند. در نهایت اقلامی که سطح کیفی قابل قبولی نداشته باشند بر روی ماشین دوم دوبارهکاری میشوند.
2-8. زمان نصب وابسته به توالی کارها
بهعنوان یک تعریف کلی، زمان نصب برای هر ماشین به مفهوم زمان مورد نیاز برای آمادهسازی ماشین بهمنظور پردازش کارهای تخصیص یافته به آن میباشد. به طور معمول، مسائل زمانبندی با در نظر گرفتن زمانهای نصب ماشین در دو گروه کلی طبقهبندی میشوند. در گروه اول زمان نصب تنها به نوع کاری که روی ماشین پردازش میشود بستگی دارد و اصطلاحا به آن زمان نصب مستقل از توالی گفته میشود. در گروه دوم زمان نصب علاوه بر نوع کاری که بر روی ماشین پردازش میشود، به کار قبلی که بر روی ماشین پردازش شده است نیز بستگی دارد و از آن با عنوان زمان نصب وابسته به توالی یاد میشود. مسائل زمانبندی مربوط به گروه دوم خود به دو دسته تقسیم می شوند. دسته اول شامل مسائلی هستند که در آنها زمان نصب، وابسته به توالی کارها و مستقل از نوع ماشینآلات89 است و در دسته دوم زمان نصب، هم وابسته به توالی کارها و هم وابسته به نوع ماشینآلات90 میباشد.
در بسیاری از تحقیقات صورت گرفته در حیطه مسائل زمانبندی فرض بر این بوده است که نیازی به صرف زمان بهمنظور آمادهسازی ماشینها جهت پردازش کارها نیست و یا این زمان را به عنوان بخشی از زمان پردازش کارها در نظر گرفتهاند. اگرچه هر کدام از این فرضیات منجر به ساده شدن تحلیل و بررسی مسائل میشود، در بسیاری از موارد که نیاز است زمانهای آمادهسازی بهصورت جداگانه در نظر گرفته شوند، به شدت بر روی کیفیت جواب تاثیر منفی میگذارد و در عمل منجر به این میشود که مدل با بسیاری از محیطهای تولیدی غیر قابل تطبیق باشد. به عنوان مثال در بسیاری از صنایع همچون صنعت پلاستیک، صنعت تولید شیشه، صنعت نفت، تسهیلات مربوط به رنگآمیزی خوردو، صنعت چاپ، صنعت نساجی و بسیاری از صنایع دیگر نیاز است که زمان آمادهسازی ماشین بصورت جداگانه در مسئله لحاظشود ]37-35[. در رابطه با اهمیت این موضوع میتوان به تحقیقات صورت گرفته توسط برخی از محققین اشاره کرد. بر اساس گزارش پانوالکار ]38[ که در دهه هفتاد میلادی به چاپ رسید، نزدیک به 70% افراد شاغل در زمینه زمانبندی اذعان کردند که در حداقل یک چهارم کارهایی که توسط آنها زمانبندی میشوند، نمیتوان نقش زمانهای آمادهسازی برای ماشینها را نادیده گرفت. همچنین، فلین ]39[ تاثیر فرآیندهای نصب وابسته به توالی را در افزایش ظرفیت تولید و ورتمن ]40[ اهمیت آن ها را در مدیریت ظرفیت تولید بررسی نمودند.
در ادامه این بخش، تعدادی از مطالعات انجام گرفته در زمینه مسائل زمانبندی ماشینهای موازی که با فرض وجود زمان نصب وابسته به توالی کارها صورت پذیرفته است، مورد بررسی قرار میگیرند.
با وجود اهمیت زمانهای آمادهسازی وابسته به توالی در مسائل زمانبندی، در بسیاری از تحقیقات انجام گرفته این موضوع لحاظ نشده است و در تعداد کمی از مطالعات صورت گرفته در زمینه زمانبندی ماشینهای موازی، زمانهای نصب وابسته به توالی در نظر گرفته شده است. این نقیصه در رابطه با ماشینهای موازی نامرتبط بیشتر به چشم میآید.
دریزل و مانچ ]41[ مسئله زمانبندی ماشینهای موازی یکسان را با وجود محدودیتهای پیشنیازی و زمانهای نصب وابسته به توالی با هدف کمینهسازی مجموع وزنی زمان های دیرکرد مورد بررسی قرار دادند و برای حل آن از روش جستجوی همسایگی متغیر91 استفاده نمودند و عملکرد آن را از لحاظ کیفیت جواب تولیدی با یک روش ابتکاری که مبتنی بر رویه92ATCSR میباشد مقایسه نمودند. آن ها گزارش دادند که روش جستجوی همسایگی متغیر در بیشتر موارد کیفیت جواب بهتری نسبت به روش ابتکاری مبتنی بر رویه ATCSR برای مسائل آزمایشی مورد استفاده دارد. گوینت و داساچوی ]42[ مسئله زمانبندی ماشینهای موازی یکسان را با در نظر گرفتن زمانهای نصب وابسته به توالی با هدف کمینهسازی بیشینه زمان تکمیل کارها با استفاده از یک روش ابتکاری بر مبنای روش مجارستانی93 بررسی کردند. کیم و شین ]43[ مسئله مشابهی را با هدف کمینهسازی بیشترین زمان تاخیر کارها بررسی نموده و برای حل آن از الگوریتم جستجوی ممنوع بهره بردند. فاولر و همکارانش ]44[ یک الگوریتم ژنتیک ترکیبی را در مسئله مشابهی برای توابع هدف مختلف شامل بیشینه زمان تکمیل کارها، مجموع وزنی زمان تکمیل کارها
و مجموع وزنی زمان دیرکرد کارها مطالعه نمودند. این الگوریتم کارها را به ماشینها اختصاص میدهد و از قوانین توزیع برای زمانبندی ماشینها استفاده میکند. نتایج محاسباتی الگوریتم برای هر سه معیار ذکر شده، عملکرد بهتر آن را نسبت به الگوریتمهای قبلی نشان میدهد. ینگ و چنگ ]45[ از روش ابتکاری جستجوی مکرر حریصانه به منظور حل مسئله زمانبندی ماشینهای موازی پویا94 با فرض وجود زمانهای نصب وابسته به توالی استفاده کردند.
کیم و همکاران ]46[ مسئله زمانبندی ماشینهای موازی نامرتبط با فرض وجود زمانهای نصب وابسته به توالی و مستقل از نوع ماشین را با هدف کمینهسازی مجموع زمان دیر کرد کارها بررسی نمودند و برای حل این مسئله، تعدادی روش ابتکاری بر پایه الگوریتم شبیهسازی تبرید ارائه نمودند. کیم و همکاران ]47[ مسئله مشابهی را با هدف کمینهسازی مجموع وزنی زمان دیر کرد کارها که در آن، کارها در قالب دستههایی پردازش میشوند مورد بررسی قرار دادند. در این مسئله فرض بر این است که تمام کارهای موجود در قالب یک دسته، دارای زمان پردازش و موعد تحویل یکسان میباشند و زمانهای آمادهسازی ماشین، وابسته به توالی دستهها و مستقل از نوع ماشینآلات میباشد. آن ها در این تحقیق از چهار رویه جستجوی ابتکاری به نامهای زودترین موعد تحویل وزنی95، کوتاهترین زمان پردازش وزنی، روش ابتکاری زمانبندی دستهای دو سطحی96 و رویه شبیهسازی تبرید استفاده نمودند.
ونگ و همکاران ]48[ مسئله زمانبندی ماشینهای موازی نامرتبط را با فرض وجود زمانهای نصب وابسته به توالی و با هدف کمینهسازی مجموع وزنی زمان تکمیل کارها مطالعه نمودند. آن ها هفت روش ابتکاری ساده را از نظر نتایج محاسباتی با یکدیگر مقایسه نمودند و در نهایت یکی از آن ها را به عنوان بهترین روش انتخاب مینمایند. این روش هر یک از کارها را بر اساس کوچکترین نرخ زمان پردازش بعلاوه زمان نصب نسبت به وزن کار در تابع هدف به ماشینها اختصاص میدهد. لاگندارن و ساپوترا ]49[ مسئله را با تابع هدف مجموع وزنی دیرکرد کارها مورد بررسی قرار دادند. آنها در این تحقیق از الگوریتم جستجوی ممنوع استفاده کردند در شرایطی که یک جواب اولیه برای الگوریتم توسط یک قاعده توزیع ساده تولید میشود. ژو وهیدی ]50[ یک مدل برنامهریزی عدد صحیح برای مسئله مشابه با تابع هدف کمینهسازی زمانهای زودکرد و دیرکرد کارها ارائه نمودند. آن ها گزارش کردند که مدل پیشنهادی برای یک مسئله با اندازه نه کار و سه ماشین در زمان قابل قبول به جواب میرسد. روچا و همکاران ]51[ مسئله زمانبندی ماشینهای موازی نامرتبط را با فرض وجود زمانهای نصب وابسته به توالی و با هدف کمینهکردن بیشینه زمان تکمیل کارها و مجموع وزنی زمان های دیرکرد مورد بررسی قرار دادند. آنها برای این مسئله یک روش شاخه و حد استفاده نمودند و از روش فراابتکاری97GRASP بهمنظور تولید یک جواب به عنوان حد بالای مسئله استفاده نمودند. آنها همچنین برای این مسئله، دو مدل برنامه ریزی عدد صحیح آمیخته ارائه کردند و نشان دادند که روش شاخه و حد مورد استفاده، عملکرد بهتری نسبت به دو مدل یاد شده دارد. والادا و روئیز ]3[ برای مسئله زمانبندی ماشینهای موازی نامرتبط با فرض وجود زمانهای نصب وابسته به توالی و با تابع هدف بیشینه زمان تکمیل کارها یک الگوریتم ژنتیک به همراه یک الگوریتم جستجوی محلی ارائه کردند و آن را برای مسائلی با اندازههای متوسط و بزرگ آزمایش کردند. آنها ادعا کردند که این الگوریتم در مقایسه با سایر روشهای موجود در ادبیات تحقیق دارای بهترین عملکرد است.
توکلی مقدم و همکاران ]35[ مسئله زمانبندی دو هدفه ماشینهای موازی نامرتبط با فرض وجود محدودیتهای پیشنیازی بین کارها و زمان نصب وابسته به توالی با هدف کمینهکردن تعداد کارهای با تاخیر و مجموع زمان تکمیل کارها بصورت همزمان را بررسی نمودند. آن ها برای این مسئله یک مدل برنامهریزی عدد صحیح آمیخته ارائه کردند و با استناد براینکه بدست آوردن جوابهای بهینه در سایزهای کاربردی برای این مسئله توسط الگوریتمهای دقیق به علت ماهیت پیچیده آن کاری دشوار و زمانبر است، یک الگوریتم ژنتیک کارا برای آن پیشنهاد نمودند.
2-9. دسترسی محدود به ماشین ها
در بسیاری از تحقیقات صورت گرفته در حیطه مسائل زمانبندی، محیطهایی مورد مطالعه قرار میگیرند که در آنها فرض بر این است تمام کارها میتوانند بدون هیچ محدودیتی روی تمام ماشینهای موجود پردازش شوند. اما در بعضی مواقع این فرض با شرایط واقعی حاکم بر سیستمهای تولیدی و خدماتی در تضاد است و شرایطی وجود دارد که کارها دارای ویژگیهایی هستند که تنها بخشی از ماشینها قادر به پردازش آنها میباشند. بدین صورت که کار نوع j تنها روی تعدادی از ماشینها و نه تمام آنها قابل پردازش است. مجموعه ماشینهایی که قادرند کار نوع j را پردازش کنند، در قالب یک مجموعه بصورت M_j نمایش داده میشوند که زیرمجموعهای از تمام ماشینهای موجود میباشد. کاربرد مسائل زمانبندی با فرض دسترسی محدود به ماشینها در بسیاری از محیطهای تولیدی و خدماتی دیده میشود. به عنوان مثال، در محیطهای بیمارستان هزینههای هنگفتی بهمنظور تجهیز اتاقهای عمل صرف میشود و با توجه به محدودیتی که در میزان تجهیزات موجود در هر اتاق وجود دارد، هر اتاق تنها برای تعدادی از بیماران قابل دسترس است. وایراک تاراکیس و کای ]52[ این مسئله را با هدف کمینه کردن بیشینه زمان تکمیل کارها بهمنظور افزایش بهرهوری اتاقهای عمل بیمارستان مدلسازی نم
ودند. شبکههای ارتباط بیسیم98، صنایع تولید فولاد و صنایع تولید مواد غذایی از جمله دیگر کاربردهای این مسئله در سیستمهای تولیدی و خدماتی میباشند.
در ادبیات تحقیق مسائل زمانبندی از این محدودیت عموما با عنوان محدودیت مجموعه پردازشی99 یاد میشود. مسائل زمانبندی با فرض وجود محدودیت مجموعههای پردازشی با عناوین مختلفی همچون زمانبندی سیستمها بر اساس نوع عملکرد100 ]53و54[ ، زمانبندی ماشین چندمنظوره101 ]52و55[ ، محدودیت مجموعه پردازشی ]60-56[، محدودیت دسترسی102 ]63-61[و محدودیت دسترسی محدود به ماشینها103 ]64و65[ شناخته می شوند.
لیانگ و لی ]66[ تحقیقی جامع بر روی ماشینهای موازی شامل ماشینهای موازی یکسان، یکنواخت و نامرتبط با فرض وجود محدودیت دسترسی به ماشینها در دو حالت زمانبندی با فرض مجاز بودن شکست در کارها و غیر مجاز بودن شکست در کارها بررسی نمودند. معیارهای بیشینه زمان تکمیل، بیشینه زمان تاخیر، مجموع(وزنی) زمانهای تکمیل، مجموع(وزنی) تعداد کارهای با تاخیر و

پاسخی بگذارید

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