بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
زمان بندی تولید کارگاهی در حالت پویا با هدف حداقل سازی هزینه های دیرکرد و فروش از دست رفته
چکیده
زمان بندی تولید کارگاهی یکی از پیچیده ترین مسائل زمان بندی است. در این مقاله، مسئله زمـان بنـدی تولیـد کارگـاهی در حالت پویا با هدف حداقل سازی مجموع هزینه های دیرکرد در تحویل و فروش از دست رفته ارائه می شود. در این محیط با رسـیدن هر سفارش جدید باید در مورد پذیرش یا رد آن تصمیم گرفته شود. از این رو هزینه های فروش از دست رفته سفارشـات جدیـد بـا افزایش هزینه دیرکرد در زمان بندی مجدد مقایسه می شود. در صورتی که سفارشات جدیدی پذیرفته شود، زمان بندی بـا در نظـر گرفتن این سفارشات ارائه می شود. به دلیل پیچیدگی زیاد این مسئله ، در ابعاد بزرگ نمی توان از الگوریتم های بهینه استفاده کرد.
لذا در این مقاله الگوریتم ﮊنتیک برای حل این مسئله مورد استفاده قرار می گیرد. در پایان نیز چند مثال عددی ارائه می شود.
کلمات کلیدی : زمان بندی تولید کارگاهی ، محیط پویا ، زمان بندی مجدد ، رد - قبول سفارشات ، هزینه دیرکرد
۱- مقدمه
در بیش از ۰۴ سال پیش مان ]۱[ و واگنر]۲[ مساله زمان بندی تولید کارگاهی را مطرح نمودند. از آن زمان تا کنون مقالات بـسیار زیـادی در این زمینه منتشر شده است . پان واکر و ایسکاندر ]۳[ بیش از ۰۰۱ قاعده زمان بندی تولید کارگاهی (Jobshop Scheduling) را گردآوری و ارائه کردند؛ لیکن قواعد مذکور بهینه بودن جواب را تضمین نمی کنند. از طرف دیگر حتی صورتهای ساده مسئله زمان بندی تولیـد کارگـاهی، -hard NP هستند ]۴.[ بنابراین استفاده از تکنیک های کلاسیک ( نظیر روش شاخه و مرز، برنامه ریزی پویا و ...) برای حل ایـن مـسائل در ابعـاد بـزرگ امکان پذیر نیست .
در سال های اخیر الگوریتم های فرابتکاری زیادی در زمان بندی تولیـد کارگـاهی بکـار گرفتـه شـده انـد. سـابونکوقلو و بـایز ]۵[ از الگـوریتم جستجوی شاخه (Beam search) برای زمان بندی مسئله تولید کارگاهی در دو حالت تابع هدف زمان اتمام کلیه کارهـا و متوسـط زمـان تـاخیر استفاده کردند. آرمنتانو و اسکریچ ]۶[ ، بارنز و چمبرز ]۷[ و لیو و همکارانش ]۸[ از الگوریتم جـستجوی ممنـوع بـرای حـل ایـن مـسئله اسـتفاده کردند. بوریزکا ]۹[ الگوریتم مورچگان را برای حل مسئله زمان بندی تولید کارگاهی مورد استفاده قرار داد. داویـس ]۰۱[ اولـین کـسی بـود کـه از الگوریتم ﮊنتیک برای حل مسئله زمان بندی تولید کارگاهی استفاده کرد.
بسیاری از محیط های صنعتی ذاتا پویا هستند و لذا زمان بندی های انجام شده باید بروزآوری شوند. این پویایی می تواند ناشی از وقـایع پـیش بینی نشده مختلفی باشد . به عنوان مثال، وقایع پیش بینی شده می توانـد تغییـر در زمـان پـردازش / راه انـدازی ، خرابـی دسـتگاهها ، تـاخیر در دریافت سفارشات ، دریافت تقاضاهای خارج از برنامه ، لغو تقاضاها ، تغییر در موعدهای تحویل و / یا اولویت مشتریان و ... باشد.
تعیین موعد زمان بندی مجدد می تواند به دو صورت انجام شود . در روش اول ، در فواصل زمانی ثابت، برنامه زمـانی بـروزآوری مـی شـود و در روش دوم هر وقت که شرایط سیستم تغییر کند و پویایی در سیستم رخ دهد برنامه ریزی بروزآوری می شود. اولین تحقیق در مـورد مـسئله زمـان بندی تولید کارگاهی در حالت پویا (Dinamic Jobshop Scheduling) توسط هالوی و نلسون ]۱۱[ انجـام شـد. آن هـا از تحقیـق خـود چنـین نتیجه گرفتند که رویکرد زمان بندی دوره ای (Scheduling/rescheduling) در محیط های تولید کارگاهی پویـا مـوثر اسـت. لیـو و همکـارانش]۲۱[ اولین کسانی بودند که از روش های فراابتکاری برای مسئله زمان بندی ترکیبی در حالت پویا استفاده کردند. در مسئله زمـان بنـدی ترکیبـی در حالت پویا فرآیند تولید برخی از محصولات از نوع تولید باز (open shop) و برخی از نوع تولید کارگاهی است. لیو و همکارانش ورود سفارشـات جدید و نیز خرابی ماشین آلات را به عنوان مشخصه های پویایی سیستم در نظر گرفتند. تیاگراجان و راجندران ]۳۱[ مسئله زمـان بنـدی ترکیبـی در حالت پویا را برای فرآیندهایی که شامل مونتاﮊ نیز می باشند، بررسی کردند. آن ها در تحلیل خود، هزینه های تحویل زودتر از موعد، دیرکـرد و زمان تکمیل پردازش هر محصول (Flow time) را در نظر گرفتند و کارایی قواعد مختلف زمان بندی را توسط مثال هـای عـددی بررسـی کردنـد.
پویایی سیستم مورد بررسی آن ها ناشی از ورود سفارشات برنامه ریزی نشده است.
در این مقاله ، مسئله تولید کارگاهی در حالت پویا را بررسی می کنیم . پویایی سیستم مورد بررسی ناشی از ورود تقاضاهای برنامه ریزی نـشده است . در این مسئله فرض می کنیم که هر ماشین در هر لحظه قادر است حداکثر یک محصول را پردازش کنـد ولـی انباشـته هـای مختلـف یـک محصول ممکن است روی ماشین های مختلف پردازش شوند . به عبارت دیگر به محض اینکه پردازش یک انباشته از محصولی روی یک ماشین بـه اتمام رسید ، آن انباشته می تواند از سایر انباشته های پردازش نشده آن محصول جدا شده و به ایستگاه بعد برود . هر گاه سفارش ( یا سفارشات )
جدیدی برسد ، زمان بندی مجدد به منظور تعیین قبول یا رد سفارشات جدید و نیـز بـروزآوری زمـان پـردازش محـصولات قبلـی و تعیـین زمـان پردازش محصولات جدید پذیرفته شده انجام می شود.
بخش های بعدی این مقاله به شرح زیر است: در بخش ۲ ، پس از ارائه فرضیات مسئله ، مدل ریاضـی مربوطـه ارائـه مـی شـود. در بخـش ۳ ، الگوریتم ﮊنتیک برای این مسئله NP-hard توسعه داده می شود و کارایی آن توسط چند مثال عددی بررسی می شود. بخش ۴ به نتیجه گیـری از مطالب ارائه شده می پردازد می پردازد.
۲- مدل ریاضی
۲-۱- فرضیات مدل
هر ماشین در هر لحظه می تواند حداکثر یک محصول را پردازش کند .
بین زمان شروع و اتمام کار یک محصول روی یک ماشین ، محصول دیگری نمیتواند روی آن ماشین پردازش شود (پـردازش به صورت Non-preemption است).
هر محصول پس از اتمام پردازش یک انباشته می تواند به ایستگاه بعد منتقل شود و نیازی بـه پـردازش کـل محـصول در آن مرحله نیست.
زمان های راه اندازی (setup time) مستقل از توالی است و لذا در زمان پردازش لحاظ شده اند.
از آنجا که پردازش به صورت Non-preemption روی هر ماشین انجام می شود ، کاری که زمان صفر (ابتـدای افـق برنامـه ریزی مجدد) در حال پردازش است باید به صورت کامل پردازش شود و ایستگاه مربوطه تا پایان این فرآیند، مـشغول (busy) است.
۲-۲- نمادها
تعداد کارها ( محصولات ) موجود n =
تعداد کارهای جدید n ' =
تعداد ماشین ها K=
تعداد مراحل کار موجود i ام mi=
تعداد مراحل کار جدید i ام m'i =
اندیس ماشین مرحله j ام کار موجود i ام sij=
اندیس ماشین مرحله j ام کار جدید i ام s'ij=
زمان پردازش مرحله j ام واحد کار موجود i ام tij=
زمان پردازش مرحله j ام واحد کار جدید i ام t'ij=
زمان شروع مرحله j ام کار موجود i ام bij=
زمان شروع مرحله j ام کار جدید i ام b'ij=
زمان پایان مرحله j ام کار موجود i ام eij=
زمان پایان مرحله j ام کار جدید i ام e'ij=
میزان تقاضای کار موجود i ام di=
میزان تقاضای کار جدید i ام d'i=
موعد تحویل (بروزآوری شده ) کار موجود i ام ddi=
موعد تحویل کار جدید i ام dd'i=
اندازه انباشته کار موجود i ام li=
اندازه انباشته کار جدید i ام l'i=
هزینه فروش از دست رفته کار جدید i ام lc'i=
متغیر صفر و یک مربوط به پذیرش/ رد هر یک از کارهای جدید a'i=
مدت زمانی که ماشینk در ابتدای دوره برنامه ریزی مجدد مشغول است busyk=
مدت زمان تاخیر در تحویل کالای موجود i ام tti=
مدت زمان تاخیر در تحویل کالای جدید i ام tt'i=
هزینه تاخیر در تحویل کالای موجود i در واحد زمان tci=
هزینه تاخیر در تحویل کالای جدید i در واحد زمان tc'i=
متغیر صفر و یک مربوط به مرحله j ام کار موجود i ام zij=
متغیر صفر و یک مربوط به مرحله j ام کار جدید i ام z'ij=
متغیر صفر و یک مربوط به کارهای موجود i و i' بر روی ماشین k y(0)ii'k=
متغیر صفر و یک مربوط به کار موجود i و کار جدید i' بر روی ماشین k y(1)ii'k=
متغیر صفر و یک مربوط به کارهای جدید i و i' بر روی ماشین k y(2)ii'k=
۲-۳ – تابع هدف و محدودیت ها
در این مسئله ابتدای دوره زمان بندی مجدد به عنوان مبدا زمان در نظر گرفته می شود و موعد تحویل و اندیس فرآیندهای باقیمانده کارهـای موجود مطابق این زمان بروزآوری می شوند. در این زمان تعدادی از فرآیندهای کارهای موجود به اتمام رسیده و تعدادی نیز در حـال انجـام اسـت.
بدیهی است فرآیندهای تکمیل شده نباید در مدل زمان بندی مجدد وارد شوند. همچنین به دلیل فرض غیرمنقطع بودن پـردازش ، فرآینـدهای در حال انجام نیز وارد مدل زمان بندی مجدد نمی شوند و در عوض ایستگاه های مربوطه تا تکمیل آن فرآیندها مشغول (busy) هستند.
تابع هدف این مسئله به صورت زیر است:
عبارت اول تابع هدف مجموع هزینه های دیرکرد کارهای موجود و عبارت دوم مجموع هزینه های تاخیر و فروش از دست رفته کارهـای جدیـد را محاسبه می نماید . برای خطی سازی باید تابع هدف به شکل عبارت ('۱) بازنویسی شود و محدودیت های (۲) و (۳ ) به مدل اضافه شوند:
زمان شروع هر یک از فرآیندها نامنفی و بزرگتر یا مساوی زمان مشغول بودن ماشین مربوطه است . همچنین هر فرآیند می تواند بلافاصله پس از تکمیل یک انباشته از فرآیند قبلی آغاز شود:
در محدودیت های (۷) و (۹) ضریب به خاطر جلوگیری از ایجاد هزینه تاخیر برای کارهای رد شده وارد شده است
زمان اتمام فرآیند اول هر کار توسط محدودیت های زیر مشخص می شود:
زمان اتمام سایر فرآیندهای هر کار موجود به صورت زیر است:
که برای خطی سازی مدل به جای عبارت (۴۱) محدودیت های (۱-۴۱) تا (۸-۴۱) به مدل افزوده میشوند.
زمان اتمام سایر فرآیندها برای کارهای جدید توسط رابطه زیر محاسبه می شـود کـه در آن ضـریب a'i از اشـغال منـابع (ماشـین هـا) توسـط کارهایی که سفارش آن ها رد شده است جلوگیری می کند:
خطی سازی عبارت (۵۱) دقیقا مشابه خطی سازی عبارت (۴۱) است، لذا از تکرار آن خودداری می شود.
در نهایت محدودیت های زیر تضمین می کنند که در هر لحظه حداکثر یک کار روی هر ماشین در حال پردازش باشد :
