کارگاه گردش کاری ترکیبی27
در این مساله در هر مرحله تعدادی ماشین به صورت موازی قرار دارند که تعداد آنها میتواند یکسان یا متفاوت باشد. به علاوه، هر کار میتواند همه مراحل را برای پردازش طی نکند، یعنی بیشترین تعداد عملیات هر کار برابر با تعداد مراحل باشد.
محیط کارگاهی
این محیط شامل ماشین است که در آن هر کار دارای مسیر مخصوصی است. دو حالت مهم در این محیط قابل تصور است. حالت اول اینکه هر کار روی هر ماشین حداکثر یک بار پردازش شود، در صورتی که در حالت دوم امکان دارد یک کار بیش از یک بار روی یک ماشین پردازش شود که اصطلاحا آن را گردش دوباره میگوییم28.
محیط کارگاهی انعطافپذیر29
مساله کارگاهی انعطافپذیر، حالت کلی و تعمیمیافته مساله زمانبندی کارگاهی کلاسیک است به طوری که در آن هر یک از عملیات میتواند توسط هر یک از مجموعه ماشینهای در دسترس برای عملیات، که زیرمجموعهای از ماشینآلات موجود است، پردازش شود.
محیط کارگاه باز
در این محیط ماشین وجود دارند و هر یک از کارها میتواند روی هر یک از ماشین پردازش شود. علاوه بر این، ممکن است که زمان بعضی از فرایندها برابر با صفر باشد. در این محیط، هیچ محدودیتی از نظر مسیر کارها در میان ماشینها وجود ندارد و مدیر برنامهریزی تعیین کننده مسیر کارهاست.
کارگاه باز با ماشینهای موازی (کارگاه عمومی ترکیبی30) به صورت ترکیبی از محیط مورد نظر و ماشینهای موازی تعریف میشود]7[.
1-4-2- خصوصیات کار و محدودیتهایی که بر محیط اعمال میشود
محدودیتهای مختلفی وجود دارند که محیطهای معرفی شده را از حالت عمومی آنها در میآورند و مسایل مختلف و محیطهای جدید زمانبندی را ایجاد میکنند. در ادامه به برخی از آنها اشاره میکنیم:
عدم انتظار31(): در این محدودیت، کارها مجاز به انتظار بین دو ماشین متوالی نیستند.
محدودیت تقدم32() :در این محدودیت شروع یک فرایند یک کار بستگی به اتمام فرایندی از کار یا کارهای دیگر دارد.

زمان آزادسازی33(): در این حالت ممکن است که کار ام در لحظهی صفر آماده به پردازش نباشد و بعد از زمان که زمان آزادسازی نامیده می شود، امکان پردازش بر روی آن فراهم میشود.

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

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

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

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

زمانهای آمادهسازی34 : در مدلهای کلاسیک زمانبندی تولید، زمانهای آمادهسازی بخشی از زمان پردازش کارها در نظر گرفته میشوند، اما در برخی شرایط واقعی، زمان آمادهسازی تاثیر بهسزایی دارد و نمیتوان به سادگی آن را نادیده گرفت. زمانهای آمادهسازی به دو حالت مستقل و وابسته به توالی در مسایل زمانبندی تولید بررسی شدهاند. در حالت اول، زمان آمادهسازی یک کار بر روی یک ماشین کاملا مستقل است، ولی در حالت دوم، این زمان وابسته به کاری است که پیش از این کار روی ماشین پردازش شده است.
زمان فرایند وابسته به وضعیت35 : در این حالت، زمان فرایند یک عملیات وابسته به مدت زمان انتظار کار پس از اتمام عملیات پیشین است. برای مثال، در فرایندهایی که حرارت از اهمیت خاصی برخوردار است و توقف کار بین ماشینها مجاز است، ولی در عین حال باعث از دست رفتن حرارت میشود،این وضعیت پدیدار میشود.
بلوکه شدن36 : این محدودیت در محیط کارگاه گردش کاری اتفاق میافتد. اگر انبار بین دو ماشین متوالی محدود پر شود، ماشین قبلی نمیتواند کار تکمیل شده را آزاد کند، لذا به بلوکه شدن ماشین میانجامد. عمومیترین حالت زمانی است که انبار بین دو ماشین متوالی برابر با صفر باشد.
در ادامه به معرفی دو محدودیت رد یا پذیرش سفارشات و تعمیرات پیشگیرانه میپردازیم.
1-4-2-1- محدودیت رد یا پذیرش سفارشات37
در اکثر مواقع زمانبندی هنگامی مطرح میشود که مسایل اصلی در خصوص برنامهریزی حل شده باشد به عبارت دیگر، زمانبندی در درجه دوم برای اتخاذ تصمیمات قرار دارد. از آنجا که به علت محدودیتهای عملیاتی و محدودیتهای تجهیزات نمیتوان همه سفارشات را قبول کرد بحث رد یا قبول سفارشات مطرح میشود.
در مسایل با محدودیت رد یا قبول سفارشات، دو تصمیم لازم و ملزم یکدیگر باید گرفته شوند، اول اینکه کدام یک از سفارشها برای تولید پذیرفته شوند و دوم ترتیب پردازش آنها به چه صورت باشد. به عبارت دیگر، با این سوال مواجه هستیم که کدام کارها پذیرفته و با چه توالی محصولات تولید شوند؟ برای پاسخ به این سوالها باید مطالعات بازار و تجزیه و تحلیلهای اقتصادی انجام شوند. در مساله زمانبندی با محدودیت پذیرش سفارشات، کارها با توجه به درآمد حاصل از پردازش هر سفارش و هزینههای عملیاتی آنها مانند هزینههای دیرکرد، هزینههای زودکرد، تأثیرات هر کار بر روی تجهیزات و غیره ارزیابی میشوند.
1-4-2-2- محدودیت دسترسی به ماشینها
در بیشتر پژوهشهای مربوط به زمانبندی فرض میشود که همه ماشینها به طور پیوسته در افق برنامهریزی برای پردازش کارها در دسترس هستند. اما در واقع عواملی همچون خرابی ماشینآلات، انجام فعالیتهای نگهداری و تعمیرات،تعطیلات و غیره در بازههایی از زمان میتوانند ماشینها را از دسترس خارج کنند. انجام فعالیتهای نگهداری و تعمیرات از دلایل عمده محدودیت دسترسی ماشینها هستند.
عملیات نگهداری به دو دسته کلی تقسیم می شوند: نگهداری اصلاح کننده38 و نگهداری پیشگیرانه39. نگهداری اصلاح کننده وقتی انجام میشود که خرابی قبلا رخ داده باشد، ولی در نگهداری پیشگیرانه، برای نگه داشتن ماشین در یک سطح مطلوب، اگرچه ماشین هنوز میتواند عملیات پردازش را انجام دهد، عملیات تعمیرات پیشگیرانه انجام میشوند]11[.
زمانبندی تولید و زمانبندی فعالیتهای نگهداری و تعمیرات از مسایل مهم مدیریت تولید به شمار میآیند، که غالبا به صورت جداگانه بررسی میشوند. انجام فعالیتهای نگهداری تعمیرات به ظاهر سبب هدر رفتن زمان تولید و در نتیجه تولید کمتر یا عدم تحویل به موقع سفارشات میشود، اما عدم انجام آنها باعث افزایش نرخ خرابی خواهد شد که به فرسوده شدن ماشینآلات، افزایش خرابی و در نتیجه عدم تحویل به موقع کارها، عدم برآورد تقاضای مشتریان، بیکاری مستقیم و نا مستقیم نیروی کار، افزایش هزینههای مربوط به تعمیر و تعویض ماشینها و در مجموع ضررهای کمی و کیفی منجر میشود.
زمانبندی با محدودیت دسترسی ماشینها شرایط واقعیتر و جامعتری از محیطهای تولیدی را در نظر میگیرد که در نهایت به یک زمانبندی مناسبتر با هزینههای کمتر میانجامد.به همین دلیل، این موضوع به یکی از موضوعات جذاب برای پژوهشگران در دهه اخیر تبدیل شده است. محدودیت دسترسی ماشینها اولین بار توسط آدیری و همکاران ]8[ در سال 1989 در مساله زمانبندی تکی با یک بازه عدم دسترسی معلوم، بررسی شد. مرورهای جامعی از پژوهشهای انجام شده در این زمینه توسط اسمیت]9[ و ما و همکاران ]10[ گردآوری شدهاند.
در ادامه، به برخی از مفروضات و ویژگیهای موثر در مسایل زمانبندی با محدودیت دسترسی ماشینها اشاره میکنیم.
با توجه به قطع پردازش عملیات، کارها به سه دسته از سر گرفتنی40(اگر پردازش کاری قطع شود، ادامه کار پس از دسترسی ماشین قابل انجام است)، بدون از سرگیری41(اگر پردازش کاری قطع شود، پس از دسترسی ماشین کار از ابتدا پردازش میشود) و نیمه از سر گرفتنی42(اگر پردازش کاری قطع شود، پس از دسترسی ماشین بخشی از کار دوباره پردازش می شود) تقسیم میشوند]12[.

بازههای عدم دسترسی : ویژگیهای مربوط به بازههای عدم دسترسی، موجب تنوع زیادی در مدل های زمانبندی با محدودیت دسترسی ماشینها شدهاند. بازههای عدم دسترسی میتوانند ثابت یا از پیش تعیین شده باشند، یا اینکه نامعین باشند و به عنوان متغیرهای تصمیم در مدل تعیین شوند]13[.
همچنین، تعداد بازههای عدم دسترسی در برخی مسایل، یک بازه عدم دسترسی یا چند بازه عدم دسترسی است. طول بازههای عدم دسترسی نیز میتواند ثابت یا متغیر باشد.
1-4-3- توابع هدف و ویژگیهای آنها
هدف در مسایل زمانبندی معمولا کمینهسازی تابعی از زمانهای تکمیل کارهاست که البته این مقادیر به زمانبندی بستگی دارد. در ادامه به معرفی برخی از توابع می پردازیم.
بیشترین زمان تکمیل کارها43
این مقدار که به صورت تعیین می شود ( زمان تکمیل کار ام است)، معادل است با زمان تکمیل آخرین کاری که سیستم را ترک میکند.
مجموع وزنی زمانهای تکمیل44
این مقدار به صورت () تعیین میشود ( وزن یا اهمیت کار است). اگر وزن مقدار هزینه یا اجاره انبار باشد، آنگاه این هدف نشانگر مجموع هزینههای اجاره یا انبار است که توسط برنامه زمانبندی ایجاد میشود.
بیشترین زمان در جریان ساخت45
این مقدار به صورت تعریف میشود که زمان در جریان ساخت کار ام است و از رابطه به دست میآید.
بیشترین تاخیر46
این هدف به صورت تعریف می شود ( میزان تاخیر کار ام است و به صورت محاسبه می شود که موعد تحویل کار ام است).
مجموع دیرکردها47
تاخیرات مثبت که از رابطه به دست میآیند، دیرکرد نامیده میشوند (میزان دیرکرد کار ام است). مجموع دیرکردها به صورت تعریف میشود. مجموع وزنی دیرکردها به صورت تعریف می شود که ضریب هزینه دیرکرد کار است.
میانگین دیرکردها
به صورت تعریف میشود.
مجموع زودکردها48
تاخیرات منفی که از رابطه به دست میآیند، زودکرد نامیده میشوند (میزان زودکرد کار ام است). مجموع زودکردها به صورت تعریف میشود. مجموع وزنی زودکردها به صورت تعریف میشود که ضریب هزینه زودکرد کار است. هزینه زودکرد میتواند به صورت هزینههای موجودی تعریف شود (اجاره انبار برای کالای ساخته شده).
میانگین زودکردها
به صورت تعریف میشود.
تعداد کارهای دارای دیرکرد49
معمولا تعداد کارهایی که دچار دیرکرد میشوند نیز دارای اهمیت است که از رابطه زیر محاسبه میشود:
(1-1)
(1-2)
1-4-3-1- نظام تولید بهنگام50
نظام تولید بهنگام تفکر و نگرشی نوین در اداره سازمانهای صنعتی است که با استفاده از تکنیکها و روشهای برخاسته از آن، حذف کامل و جامع اتلاف و افزایش بهرهوری در همه فعالیتها اعم از داخل و خارج سازمان تعقیب میشود.
ظهور در واقع انقلابی در دنیای تولید بود. در واقع، به معنی تولید محصولات مورد نیاز به مقدار مورد نیاز و در زمان مورد نیاز است؛ به عبارت دیگر، اگر مشتری و تولیدکننده زمان تحویل کالا را در یک زمان معین توافق کنند، تولید کننده باید تولیدات خود را طوری برنامهریزی کند که کالا را در صورت امکان در زمان مناسب تولید و در زمان مقرر به دست مشتری برساند. اگر کالا دیرتر از موعد تحویل آماده شود، آنگاه تولیدکننده متحمل جریمهای به عنوان جریمه تاخیر (مثل تخفیف به مشتری) خواهد بود. همچنین، اگر کالا زودتر از موعد تحویل تولید شود، آنگاه باید تا زمان تحویل در انبارنگهداری شود که در این صورت نیز متحمل هزینه (مثل هزینه اجاره انبار) خواهد شد.
برای این منظور، توابع هدفهای مختلفی بررسی شدهاند که از آن جمله میتوان به توابع زیر اشاره کرد:
(1-3)(1-4)(1-5)(1-6)(1-7)
1-5- بیان مساله جریان کارگاهی در نظر گرفتهشده در این مطالعه
در این پایاننامه، حالت جامعتری از مساله زمانبندی کارگاه گردش کاری با در نظر گرفتن محدودیت نگهداری و تعمیرات و محدودیت رد یا پذیرش سفارشات بررسی میشود.
در مساله کارگاه گردش کاری، مجموعه ای از کار که باید بر روی مجموعهای از ماشین پردازش شوند، موجود میباشد. هر یک از کارها شامل توالی عملیات است که به ترتیب بر روی ماشین اول تا ماشین ام پردازش میشوند. زمانی که کاری ماشین ام را ترک کند، تکمیل میشود. سیستم تولیدی گردش کاری در صنایع مختلفی چون خودروسازی، کولرسازی، یخچال سازی، نساجی و غیره کاربردهای فراوانی دارد.
در این پایاننامه، برخلاف تعاریف زمانبندی، ماشینها همیشه در دسترس نیستند و این عدم دسترسی به علت وجود فعالیتهای نگهداری و تعمیرات پیشگیرانه است.. علاوه بر این، محدودیت رد یا پذیرش سفارشات وجود دارد، به این معنی که همهی سفارشات رسیده پذیرش نمیشوند و با توجه به درآمد و سهم آنها در سود خالص شرکت تصمیم به پذیرش یا رد آنها گرفته میشود.
مشخصات مساله فلوشاپ مورد بررسی:
زمانهای پردازش و تحویل قطعی هستند.
هر قطعه باید به ترتیب بر روی تمام ماشینها پردازش شود.
هر قطعه در هر زمان تنها بر روی یک ماشین پردازش میشود.
در هر زمان، هر ماشین تنها بر روی یک قطعه میتواند پردازش انجام دهد.
عملیات هر قطعه بر روی هر ماشین به صورت کامل انجام میشوند و قطعی در کارها صورت نمیگیرد.
توالی مورد نظر برای انجام پردازش بر روی قطعات از ابتدا تا انتهای همه پردازشها ثابت میماند.
زمان آمادهسازی ماشینها و زمان حرکت قطعات بین ماشینها نادیده گرفته میشوند.
ماشینها به صورت مستقل از هم کار میکنند.
قطعات از هم مستقل هستند.
ظرفیت بافر میان ماشینها نامحدود در نظر گرفته میشود.
همه قطعات و ماشینها در زمان صفر در کارگاه موجود و در دسترس هستند.
نگهداری پیشگیرانهی ماشینآلات در نظر گرفته میشود.
زمان عملیات نگهداری پیشگیرانه با زمان پردازش کارها تداخل ندارد.
محدودیت رد یا پذیرش سفارشات در نظر گرفته میشود.
1-6- روش حل
تاکنون رویکردهای زیادی برای حل مسایل زمانبندی جریان کارگاهی توسعه یافتهاند، مانند روشهای دقیق51، ابتکاری52 و فراابتکاری53. اگر بخواهیم بهصورت بهینه مساله زمانبندی جریان کارگاهی را حل کنیم، بهترین تکنیک استفاده از روش شاخه و کران54 است. اما روشهای دقیق موفقیت نسبی در حل مسایل با مقیاس کوچک دارند، ولی و برای حل بهینه مسایل پیچیده در دنیای واقعی که شامل مسایل با اندازههای متوسط و بزرگ هستند، مناسب نیستند.
در ادبیات موضوع روشهای ابتکاری و فراابتکاری متنوعی برای حل این مسایل مطرح شدهاند. با توجه به اینکه مسایل زمانبندی عموما NP-سخت هستند و زمان محاسباتی نیز با توجه به اندازه مساله به صورت نمایی افزایش مییابد، از روشهای فراابتکاری برای حل مساله زمانبندی جریان کارگاهی استفاده میشود.
در این مطالعه، برای مسایل با اندازههای کوچک یک مدل ریاضی ارایه میشود و برای مسایل با اندازههای متوسط و بزرگ از روشهای فراابتکاری شبیهسازی تبرید و الگوریتم ژنتیک استفاده میشود.
تحقیق موجود از دو جنبه صورت مسئله و روش حل نسبت به تحقیقات پیشین دارای نوآوری میباشد.
1-7- اهداف تحقیق
هدفهای این مطالعه را میتوان به صورت زیر برشمرد:
مروری بر مطالعات صورت گرفته در محیط جریان کارگاهی.
توجه به اهمیت تولید بهنگام و تحویل به موقع سفارش به مشتری.
بررسی و مدلسازی مسالهی زمانبندی بهنگام در سیستم تولید جریانی با فرض رد یا قبول سفارشات با هدف کمینهسازی جریمههای ناشی از زودکرد و دیرکرد و رسیدن به بیشترین سود خالص.
نزدیک شدن به دنیای واقعی تولید با در نظر گرفتن نگهداری پیشگیرانه ماشین آلات.
توسعه روشهای فراابتکاری برای حل مساله مورد نظر.
مقایسه عملکرد و کارایی روشهای حل ارایه شده با کمک آزمونهای عددی.
1-8- نتیجه گیری
مسایل زمانبندی عموما به عنوان یکی از مسایل با درجه NP-سخت شناخته میشوند. پیچیدگی مطرح شده در محیط زمانبندی جریان کارگاهی با در نظر گرفتن محدودیت رد یا پذیرش سفارشات و کمینه سازی هزینههای مربوط به زودکرد و دیرکرد و در نظر گرفتن فعالیت نگهداری و تعمیرات از پیچیدگیهای بیشتری برخوردار است. با توجه به محدودیت منابع و ظرفیت تولیدی در بسیاری از صنایع و وجود جریمههای دیرکرد و زودکرد، تولیدکننده نمیتواند همه سفارشات رسیده را بپذیرد، بنابراین، موضوع پذیرش سفارشات مطرح میشود و تولیدکننده باید موازنهایی بین درآمد حاصل از قبول سفارشات و هزینههای حاصل از پردازش کارها ایجاد کند.
این پایان نامه دارای ساختار زیر است. در فصل دوم، برای آشنایی خواننده مروری تقریبا جامع بر ادبیات موضوع در بخشهای مختلف اعم از ادبیات موضوع سیستم جریان کاری و زمانبندی این سیستمها با توجه به فعالیتهای نگهداری و تعمیرات پیشگیرانه و محدودیت رد یا پذیرش سفارشات صورت میگیرد. در فصل سوم، یک مدل ریاضی و دو روش فراابتکاری برای مساله مورد نظر توسعه مییابد. در فصل چهارم، پس از بیان نحوه تولید مسایل نمونه، به تنظیم پارامترهای الگوریتمها با استفاده از روش سعی و خطا و به صورت تجربی و روش تاگوچی میپردازیم و در پایان، در فصل پنجم نتیجهگیری کلی ارایه و چند زمینه پژوهش برای مطالعات آتی پیشنهاد میشوند.
فصل دوم
ادبیات تحقیق
2-1- مقدمه
در این فصل به تشریح ادبیات تحقیق در سه بخش پرداخته میشود. در بخش اول مروری بر ادبیات کارگاه گردش کاری مطرح میشود، در بخش دوم محدودیت دسترسی به ماشینها در محیط جریان کارگاهی مورد توجه قرار گرفته است. بخش سوم به مروری بر ادبیات محدودیت پذیرش سفارشات میپردازد.
2-2. مروری بر ادبیات کارگاه گردش کاری
از زمانی که جانسون55 ]14[ در سال 1954 مقاله خود را در مورد مساله زمانبندی کارگاه گردش کاری ارایه نمود این موضوع مورد توجه بسیاری از محققین قرار گرفت به طوری که تاکنون بیش از 3000 مقاله در زمینههای مختلف این مساله ارایه شده است. جانسون قانون سادهای را برای زمانبندی کارها در مساله کارگاه گردش کاری دو ماشینه و سه ماشینه ارایه کرد. تحقیقات برجسته و نوعآوریهای صورت گرفته در طول 6 دهه از پیدایش این مساله را میتوان به صورت ذیل خلاصه نمود:
دهه اول: مطالعات و تحقیقات دهه اول، بر مساله زمانبندی کارگاه گردش کاری ماشینه با هدف حداقل نمودن دوره زمانی ساخت متمرکز بود. مدلهای ارایه شده طی این سالها، تئوریک و ریاضی بوده و بیشتر به سمت تکنیکهای بهینه سازی چون برنامهریزی ریاضی حرکت کرده است]15[.
دودک56 ]16[ در سال 1964 قانون جانسون برای دو ماشینه را برای مسئله ماشینه بسط داد. هرچند بعدا نشان داده شد که این روش نادرست است اما این خود زمینه شروع ارایه راه حلهای متنوع دیگر شد.
دهه دوم: در دهه دوم علاوه بر ظهور روشهای متعدد زمانبندی، تابع هدفهای متنوعی نیز در مساله کارگاه گردش کاری در نظر گرفته شد. در این دهه روش ارایه شده دودک توسعه داده شد. تلاش برای توسعه الگوریتمهای بهینهسازی مساله کارگاه گردش کاری منجر به پیدایش الگوریتمهای ابتکاری شد. این الگوریتمها جوابهای نزدیک به بهینه را برای مسایل کوچک و بزرگ کارگاه گردش کاری تولید میکردند. مساله کارگاه گردش کاری بدون توقف نیز برای اولین بار در این دهه توسط ردی و رامامورسی]17[ ارایه شد.
دهه سوم: در دهه سوم با پیدایش نظریه پیچیدگی، پیچیدگی مرتبط با مساله کارگاه گردش کاری به صورت گسترده مورد توجه قرار گرفت و NP-سخت بودن این مساله اثبات شد]18[.مساله کارگاه گردش کاری احتمالی57 در این دهه برای اولین بار توسط پیندو58 ]19[ مطرح شد.
دهه چهارم: در دهه چهارم روش های حل ابتکاری و فراابتکاری زیادی برای حل مساله کارگاه گردش کاری توسعه یافت که از آن جمله میتوان به الگوریتم ژنتیک59() توسط ریوز60 ]20[، جستجو ممنوعه61() توسط تیلارد62 ]21[ و تبرید شبیهسازی شده63() توسط عثمان و پاتس64 ]22[ اشاره کرد. همچنین مساله کارگاه گردش کاری ترکیبی و در نظرگیری توابع هدف چندگانه برای اولین بار در این دهه مطرح شد.
دهه پنجم: در دهه پنجم مساله کارگاه گردش کاری عمومیتر شد و مفروضاتی همچون پردازش دستهایی65 کارها، زمان های آمادهسازی وابسته به توالی در نظر گرفته شد. در این دهه بهبودهایی در الگوریتمهای فراابتکاری در نظر گرفته شده در دهه قبلی ایجاد گردید و ترکیب نمودن الگوریتمهای حل مختلف با یکدیگر جهت افزایش کارایی آنها مورد توجه قرار گرفت. همچنین در این دهه محدودیت دسترسی ماشینها توسط لی66 ]23[ در مساله کارگاه گردش کاری برای اولین بار مطرح شد.
دهه ششم: دهه ششم را میتوان نقطه اوج تحقیقات در زمینه مساله کارگاه گردش کاری عنوان نمود. در این دهه رشد کمی و کیفی بالایی در همه زمینههای مطرح در این حوزه صورت پذیرفت و رویکردهای حل دقیق، ابتکاری و فراابتکاری فراوانی توسعه داده شد. همچنین در این دهه بررسی محدودیت دسترسی ماشینها از استقبال بالایی برخوردار شد.
2-3- زمانبندی و محدودیت دسترسی به ماشینها
محدودیت دسترسی ماشینها اولین بار توسط آدیری67 و همکارانش]8[ در سال 1989 در مساله زمانبندی ماشین تکی با یک بازه عدم دسترسی معلوم، مورد بررسی قرار گرفت. از آن زمان تاکنون مطالعات گستردهای در این زمینه انجام گرفته است که در چند سال اخیر رشد چشمگیری داشته است. مروری جامعی از این مطالعات توسط اسمیت68 ]9[ و ما69 و همکاران]10[ گردآوری شده است.
در یک دستهبندی کلی مسایل زمانبندی با محدودیت دسترسی به ماشینها به دو دسته اصلی قابل تفکیک میباشند: مسایل تصادفی70 و مسایل قطعی71، که بیشتر تحقیقات بر روی مسایل قطعی متمرکز شده است. مسایل تصادفی حالاتی را بررسی می کند که محدودیت دسترسی ماشین، از قبل مشخص و معلوم نمیباشد و ماهیت تصادفی دارد. این حالت بیشتر به خرابیهای تصادفی ماشین، رسیدن سفارش فوری که از قبل برنامهریزی شده نمیباشد و یا عدم خدمتدهی سیستمهای پشتیبان مانند سیستمهای انرژی و غیره برمیگردد.
مدلهای قطعی حالاتی را در برمیگیرند که عدم دسترسی ماشین از قبل معلوم و برنامهریزی شده میباشد. که این حالات به نگهداری و تعمیرات پیشگیرانه، بازرسیها72، انجام اقدامات اصلاحی، تعطیلات و تغییر شیفتهای کاری برمیگردد]10[.
2-3-1- مروری بر ادبیات مساله کارگاه گردش کاری با محدودیت دسترسی ماشینها
لی]23[ برای اولین بار فرض محدودیت دسترسی ماشینها را وارد مسایل کارگاه گردش کاری نمود. او مساله کارگاه گردش کاری دو ماشینه را با فرض یک بازه عدم دسترسی معلوم بر روی ماشین اول یا دوم، با تابع هدف دوره زمانی ساخت مورد بررسی قرار داد. او ثابت کرد که این مساله NP-سخت میباشد و برای حل آن از روش برنامهریزی پویا73 و روش ابتکاری استفاده نمود. اسپینوس74 و همکاران]24[ ثابت نمودن که مساله کارگاه گردش کاری دو ماشینه با چند بازه عدم دسترسی معلوم و پردازش بدون توقف کارها به شدت NP-سخت میباشد و برای حل آن یک روش ابتکاری ارایه نمودند.
آژگون75 ]25[ مساله کارگاه گردش کاری ماشینه را با چند بازه عدم دسترسی معلوم یا منعطف با تابع هدف دوره زمانی ساخت در نظر گرفتند.آنها برای حل این مساله از یک روش ابتکاری بهبود دهنده استفاده نمودند که جوابهای اولیه تولیدشده با الگوریتم ژنتیک و جستجوی ممنوعه را بهبود میداد. بریت76 ]26[ مسئله کارگاه گردش کاری دو ماشینه را با تابع هدف دوره زمانی ساخت و فرض از سرگرفتنی بودن کارها بررسی نموده و برای آن یک روش حل تقریبی ارایه نمود. آژگون]27[ از یک روش ابتکاری مبتنی بر روش هندسی برای حل مساله کارگاه گردش کاری ماشینه با تابع هدف دوره زمانی ساخت و چند بازه عدم دسترسی معلوم بر روی هر ماشین استفاده نمود.رویز77 و همکاران]28[ مساله کارگاه گردش کاری ماشینه را با فعالیتهای نگهداری و تعمیرات پیشگیرانه و با تابع هدف دوره زمانی ساخت در نظر گرفتند و با استفاده از الگوریتم ژنتیک، کلونی مورچگان و روش ابتکاری آن را حل نمودند.
یانگ78 و همکاران]29[ نوع جدیدی از محدودیت دسترسی که بعد از پردازش تعداد مشخصی از کارها ایجاد میشود را در مساله کارگاه گردش کاری دو ماشینه و با تابع هدف دوره زمانی ساخت در نظر گرفتند و با استفاده از روشهای ابتکاری آن را حل نمودند. لیائو و تیسای79 ]30[ یک مدل ریاضی برای مساله کارگاه گردش کاری دو ماشینه با تابع هدف دوره زمانی ساخت و محدودیتهای دسترسی که بعد از پردازش تعداد مشخصی از کارها ایجاد میشود، ارایه نمودند و با استفاده از روش شاخه و کران و ابتکاری آن را حل نمودند.
یااوریما80 و همکاران]31[ محیط کارگاه گردش کاری ترکیبی با تابع هدف دوره زمانی ساخت و فرضیات زمان آمادهسازی وابسته به توالی، محدودیت انبار میانی و نگهداری و تعمیرات پیشگیرانه در نظر گرفته و با استفاده از الگوریتم ژنتیک حل نمودند. جباری زاده و همکاران]11[ نیز برای حل این مساله از الگوریتم ژنتیک و انجماد تدریجی استفاده نمودند.واحدی نوری و همکاران]32[ مساله کارگاه کردش کاری غیرجایگشتی با درنظر گرفتن همزمان تاثیرات یادگیری و محدودیت دسترسی ماشینها را مورد بررسی قرار دادند و برای آن یک مدل ریاضی ارایه نمودند و از روشهای ابتکاری و از یک الگوریتم فراابتکاری تلفیقی بر مبنای الگوریتم شبیه سازی تبرید و الگوریتم کرم شب تاب81 استفاده نمودند.
گنزالز و فرامینان82 ]33[ فرض عدم دسترسی ماشینها در ابتدای دوره را در مساله کارگاه گردش کاری ماشینه در نظر گرفته و برای آن روشهای حل ابتکاری ارایه نمودند. لیو و همکاران]34[ محیط کارگاه گردش کاری ترکیبی دو مرحله ای با ماشین در مرحله اول و یک ماشین در مرحله دوم را با تابع هدف دوره زمانی ساخت و زمان آماده سازی وابسته به توالی، انبار میانی صفر و یک بازه عدم دسترسی بر روی ماشین مرحله دوم بررسی نموده و از الگوریتم ژنتیک برای حل آن استفاده نمودند. صفری و همکاران]35[ نگهداری و تعمیرات مبتنی بر وضعیت را در زمانبندی کارگاه گردش کاری ماشینه با تابع هدف مقدار انتظاری دوره زمانی ساخت بررسی نموده و یک الگوریتم ترکیبی مبتنی بر الگوریتم ژنتیک و الگوریتم و جستجوی ممنوعه برای حل آن ارایه نمودند. چایهائوی83 و همکاران]36[ یک روش شاخه و کران برای حل مساله کارگاه گردش کاری دو ماشینه با تابع هدف دوره زمانی ساخت، یک بازه عدم دسترسی بر روی هر ماشین و وجود زمان آزادسازی کارها ارایه نمودند.
2-4- مروری بر ادبیات محدودیت رد یا پذیرش سفارشات
در ابتدا پوربابایی]37[ یک مدل انتخاب کار در محیط تک ماشین برای تعیین اینکه چه تعداد و کدام کارها پذیرش شوند به طوریکه سود خالص با توجه به جریمه دیرکرد ماکزیمم شود ارایه نمود. گوپتا84 و همکاران]38[ مسئله انتخاب یک زیر مجموعه از پروژه و تعیین توالی بهینه برای آنها، برای دستیابی به ماکزیمم سود خالص را مورد مطالعه قرار دادند. استاجه85 ]39[ مساله زمانبندی ماشین تکی با فرض انتخاب کارها و توالی آنها را مورد مطالعه قرار داد، که در آن فرض شد ماشین با احتمال قابل پیشبینی دچار خرابی شده و غیر قابل تعمیر است. اسلوتنیک و مورتون86 ]40[ مدل پذیرش سفارش تک دورهای برای یک سیستم تک مرحلهایی را در نظر گرفتند، هدف در این مدل ماکزیمم نمودن سود خالص بوده که تاخیر در تحویل منجر به جریمه شده و تحویل زودتر از موعد منجر به سود بوده است. برای حل این مدل از الگوریتم دقیق شاخه و کران و دو الگوریتم ابتکاری استفاده شد. لویس و اسلوتنیک87 ]41[ مدل چند دورهایی با رویکرد دیرکرد وزنی را در نظر گرفتند، آنها فرض کردند که انتخاب کارها روی سفارشات آینده تاثیر میگذارد؛ به عبارت دیگر مشتری ردشده دیگر باز نمیگردد.اسلوتنیک و مورتون88 ]42[ این مدل را با در نظر گرفتن جریمه دیرکرد و اینکه زودکرد پاداشی در بر ندارد مورد مطالعه قرار دادند. اوز89 و همکاران]43[ مدل قبلی را با فرض زمانهای آمادهسازی وابسته به توالی مورد مطالعه قرار دادند و برای حل آن از الگوریتمهای فراابتکاری استفاده نمودند.
مدلهای پذیرش سفارش در محیطهای دیگر نیز مورد مطالعه قرار گرفته است؛ آیوانسکو90 و همکاران]44، 45[ مساله پذیرش سفارشات را در محیط پردازش دستهایی در نظرگرفتند. آنها یک سیاست ترکیبی با استفاده از تکنیکهای شبیهسازی تبرید به منظور بررسی تأثیر مستقیم پذیرش یک کار بر روی بهرهوری منابع را ارایه نمودند.مارتینز و اردوندو91 ]47[ مدل مدیریت درآمد با پذیرش سفارشات را برای ماکزیمم نمودن سود بطوریکه محدودیت ظرفیت وجود دارد و دیرکرد مجاز نیست ارایه دادند.
از آنجا که اغلب مسایل بهینه سازی در کلاس مسایلNP-سخت قرار میگیرند، استفاده از روشهای دقیق برای حل آنها در یک زمان معقول مناسب نمیباشد.با توجه به محدودیت زمانی و پیچیدگی زیاد این مسایل، استفاده از روشهای فراابتکاری در این مسایل مناسب میباشد. روم و اسلوتنیک]48[ الگوریتم ژنتیک را برای محیط ماشین تکی با محدودیت پذیرش سفارشها به کار بردند. در مقالات ]43، 44، 45، 46[ از الگوریتم تبرید شبیهسازی شده استفاده نمودند. سیزارت92 ]49[ الگوریتم جستجوی ممنوع را برای مساله تک ماشینه به کار برده است.
فصل سوم
روشهای حل
3-1- مقدمه
رویکرد برنامهریزی عددصحیح93 به عنوان یک روش دقیق ظرفیت عملکرد محدودی در بهینهسازی مسایل زمانبندی در زمان محاسباتی معقول دارد. از سوی دیگر، بیشتر مسایل موجود در محیطهای صنعتی اندازه بزرگتری نسبت به ظرفیت محاسباتی مدلهای برنامهریزی عددصحیح دارند. با این وجود، این مدلها جوابهای بهینه لازم برای توسعه و اعتبارسنجی عملکرد رویکردهای ابتکاری و فراابتکاری گوناگون را فراهم میکنند.

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

پاسخ دهید