بخشی از مقاله
چکیده:
زمانبندی، یک نقش مهم را در برنامهریزی ایفا میکند و زمان برنامهریزی شده در هنگام کار روی ماشین نشان میدهد. زمانبندی کارگاه جریانی با تعیین ترتیب بهینهی کارهایی که بر روی تعدادی ماشین در یک ترتیب ثابت پردازش میشوند سروکار پیدا میکند. در حالت کلی نشان داده شده است که مسألهی زمانبندی کارگاه جریانیNP-Hard است.
این تحقیق با مسأله زمانبندی جریان درون کارگاهی و پیمانکاری با اهداف حداقل کردن زمان تکمیل کارها و مجموع هزینه های برون سپاری سروکاردارد. مدلی که در این تحقیق پیشنهاد می شود با در نظر گرفتن تصمیم گیری همزمان در تولید درون کارگاهی و برون سپاری و در نظر گرفتن چندین پیمانکار در دسترس به همراه اعمال موعد زمان تحویل کار سعی کرده است مسأله مورد نظر خود را در حد امکان با شرایط واقعی تطبیق دهد. به منظور مواجهه با عدم قطعیت در زمان های پردازش، یک رویکرد بهینه سازی استوار بر مبنای روش برتسیماس و سیم ارائه می شود. نتایح حاصل از تحقیق، کارایی رویکرد استوار در بهینه سازی این مسئله را نشان می دهد
1 مقدمه
جریان کارگاهی یک سیستم تولیدی است به نحوی که همه ماشینها بر اساس اجرای عملیات روی کارها مرتب میشوند. مسأله زمانبندی جریان کارگاهی که شامل تعیین یک زمانبندی بهینه برای کارها روی ماشینها است، سالها یک معیار تحقیقات بوده است. بهینهسازی الگوریتمها برای مسائل جریان کارگاهی دو و سه ماشینه در رابطه با اهداف مختلف گسترش یافته بود. مسائل زمانبندی مختلف بطور گسترده در ادبیات موضوع مورد بررسی قرار میگیرد. همانطور که اکثریت مسائل زمانبندی جریان کارگاهی جز مسائل سخت1 هستند، همه روشهای ابتکاری و فراابتکاری به دنبال حداقل رساندن Make Span هستند.
مسأله جریان کارگاهی سنتی دارای فرضیات مشخصی است که در تمامی سیستمهای جریان کارگاهی توجه میشود. این فرضیات عبارتند از:
-1 هر کار i در هر بازه زمانی تنها توسط یک ماشین بایستی انجام شود،
-2 هر ماشین j تنها برای یک کار i در هر زمانی مورد پردازش قرار گیرد،
-3 قطعه قطعه نمودن کارها مجاز دانسته نمیشود - پردازش یک کار بر روی یک ماشین نبایستی به بازههای زمانی تقسیم شود - ،
-4 همه کارها مستقل از هم و در زمان صفر برای پردازش دسترس میباشند،
-5 زمان راه اندازی کارها برروی ماشینها در توالی مستقل از هم و دارای زمانی برای پردازش این عمل هستند،
-6 سیستم تولید به صورت پیوسته میباشد.
سه نوع گروه بندی توابع هدف برای مسائل زمانبندی در سیستم جریان کارگاهی وجود دارد :
الف - اهداف بر اساس زمان تکمیل کارها
ب - اهداف بر اساس زمان تحویل
ج - اهداف بر اساس موجودی و هزینه بکارگیری
در مبحث زمان تکمیل کارها دسته بندی های گوناگونی از جمله زمان تکمیل کلیه کارها، میانگین زمان تکمیل2، زمان تکمیل وزندار3، میانگین زمان تکمیل وزندار4 وجود دارد.
توابع هدف دیگری نیز در سالهای اخیر مورد بررسی قرار گرفتهاند از جمله زمان جریان کل5، زمان جریان میانگین6، زمان جریان وزندار کل7، زمان جریان وزندار میانگین8، حداکثر دیرکرد9، دیرکرد کل10، میانگین دیرکرد11، حداکثر زودکرد12، زودکرد کل13، میانگین زودکرد14، میانگین وزنی دیرکرد15 و واریانس زمان تکمیل16 که در فصل ادبیات موضوع مورد بررسی قرار میگیرند.
یکی از مسائل مهم در برنامه ریزی تولید، استفاده بهینه ازمنابع تولیدی می باشد، دسته ای از این منابع ماشین آلات تولیدی هستند که باید به صورت کارا و موثر مورد بهره برداری قرار گیرند از سوی دیگر باید همواره حجم اندکی از محصولات و قطعات در داخل سیستم تولیدی وجود داشته باشد. مسأله تعیین اندازه دسته در جریان کارگاهی بدون توقف17 یکی از مسائلی است که قادر است هر دو خواسته فوق را برآورده نماید . در یک محیط جریان کارگاهی تعدادی ماشین وجود دارد که هر یک بایستی عملی را بر روی محصول انجام دهند. بدیهی است که شکستن اندازه یک دسته به تعدادی زیردسته میتواند موجب کاهش زمان تولید دسته مورد نظر گردد.
با توجه به اهمیت موضوع، در این تحقیق تلاش شده است تا با لحاظ کردن شرایط و مفروضات جدید به مسئله، به بررسی و تحلیل آن پرداخته شود.
2 بهینه سازی استوار
در مقابل رویکردهای ذکر شده، رویکرد دیگری که در سالهای اخیر برای مقابله با عدم قطعیت دادهها بسط داده شده است، بهینهسازی استوار است. در این رویکرد به دنبال جوابهای نزدیک به بهینه هستیم که با احتمال بالایی موجه باشند. به عبارت دیگر بتوانیم با کمی صرف نظرکردن از تابع هدف، موجهبودن جواب بدستآمده را تضمین کنیم. در بهینه سازی استوار هدف یافتن راه حلی است که در مقابل عدم قطعیت کمترین تغییرات را نشان دهد
به طورکلی مدل های استواری موجود را می توان به دو گروه تقسیم نمود :
- 1 گروه اول به دنبال راه حلی است که تابع هدف را برای بدترین سناریو بهینه کند.
- 2 گروه دوم شرایطی را به راه حل ها تحمیل می کنند . دراین حالت راه حلی به عنوان یک حل استوار در نظر گرفته می شود که بتواند شرایط تحمیل شده را برقرار نماید.
رویکرد بهینه سازی استوار رویکرد مناسبی در مواجهه با عدم قطعیت داده ها می باشد. با استفاده از رویکرد بهینه سازی استوار می توان برنامه اولیه را به نحوی ایجاد کرد که تغییر داده ها حین اجرای برنامه تا حد ممکن کمترین تغییرات را در برنامه اولیه سبب شود.
مالوی و همکاران [3] رویکردی ارائه کردند که فرمولبندیهای برنامهریزی آرمانی را با سناریوهای دادههای مسأله ترکیب میکند. در اوایل دهه 1970 سویستر[4] یک مدل بهینهسازی خطی ارائه کرد که بهترین جواب موجه برای همه دادههای ورودی را به ما میدهد به طوری که هر داده ورودی میتواند هر مقداری را از یک بازه بگیرد. این رویکرد تمایل به یافتن جوابهایی دارد که بسیار محافظهکارانه18 باشد.
بدین معنی که برای اطمینان از استوار بودن جواب در این رویکرد به مقدار زیادی از بهینگی مسأله اسمی دور میشویم. بن-تال و نیمروفسکی و ال- قائویی و لبرت [5] با فرض اینکه دادهها در مجموعههای بیضوی دارای عدم قطعیت هستند الگویتمهای کارایی برای حل مسائل بهینهسازی محدب تحت عدم قطعیت دادهها ارائه نمودهاند. با این وجود با توجه به اینکه فرمولبندیهای استوار بدستآمده از مسائل درجه دو مخروطی19 میباشند، این روشها نمیتوانند به طور مستقیم برای مسائل بهینهسازی گسسته مورد استفاده قرار گیرند. برتسیماس و سیم [6] رویکرد متفاوتی را برای کنترل سطح محافظهکاری20 معرفی کردهاند. این رویکرد از این مزیت برخوردار است که منجر به یک مدل بهینهسازی خطی میگردد. و بنابراین قابل اعمال بر روی مدلهای بهینهسازی گسسته نیز میباشند.
جهت فرمولهکردن مسائل بهینهسازی خطی به صورت روشهای استوار میتوان از چندین مدل متفاوت که تاکنون توسعه داده شدهاند، استفاده نمود. سه مدل اصلی و مبنا در روشهای استوار بر اساس عدم قطعیت بازهای؛ مدل استوار سویستر[4]، مدل استوار بن-تال و نیمروفسکی[7 7] و مدل استوار برتسیماس و سیم [6] است. در این پژوهش از مدل برتسیماس برای فرمولهکردن مسأله خود استفاده کردهایم.
در ادامه، ابتدا شرح مختصری از سه مدل فوق ذکرگشته وسپس دلایل استفاده از روش برتسیماس توضیح داده میشود. در انتها نیز همتای استوار21 مدل مسأله بر اساس مدل برتسیماس توسعه داده شده است.
مدل استوار برتسیماس و سیم
مدل برتسیماس و سیم [6] را برای مسأله بهینهسازی خطی در حالتی که تابع هدف کمینهسازی است و ضرایب عدم قطعیت هم در تابع هدف و هم در محدودیتها وجود دارند، شرح بیشتری خواهیم داد، سپس به بررسی مدل اصلی پژوهش جهت تطابق مدل برتسیماس و سیم میپردازیم.
بازههای عدم قطعیت به صورت زیر تعریف میشوند:
هر کدام از ضرایب محدودیتها , ∈ = {1,2, … , } به صورت یک متغیر تصادفی مستقل، با توزیع متقارن ولی ناشناخته ̃ , ∈ مدل میشودکه در بازه [ − ̂ , + ̂ ] مقدار میگیردکه ̂ نشاندهنده انحراف از ضریب اسمی است.
هر کدام از ضرایب تابع هدف به صورت , ∈ در بازه [ − , + ] مقدار میگیرد که نشاندهنده انحراف از ضریب اسمی است. قابل ذکر است که از آنجا که تابع هدف کمینهسازی است و هدف مدلهای استوار بدست آوردن ماکزیمم تاسف22 است، تنها یک طرف بازه مذکور مورد استفاده قرار میگیرد یعنی فرض میشود که در بازه [ , + ] مقدار میگیرد.
برای فرمولبندی همتای استوار مسأله، به صورت زیر تعریف میگردد:
محدودیت i ام مسأله را به صورت ≤ در نظر بگیرید. به صورت مجموعه ضرایب غیر قطعی در سطر i تعریف میشود. برای هر سطر i پارامتر که لزوما عدد صحیح نیست را تعریف میکنیم، بطوریکه . ∈ [0, | |] در واقع نقش ها در محدودیتها تنظیم نمودن میزان استواری23 روش پیشنهادی در مقابل سطح محافظهکاری جواب است.
برتسیماس و سیم نشان دادند که با احتمال کمی ممکن است تمامی ضرایب با هم دچار عدم قطعیت شوند. لذا فرض میکنیم حداکثر ⌊ ⌋ عدد از این ضرایب اجازه تغییر دارند و یک ضریب نیز میتواند حداکثر به مقدار - -⌊ ⌋ - ̂ تغییر کند. به عبارت دیگر ما فرض میکنیم فقط یک زیرمجموعه از ضرایب مجاز خواهند بود که در حل ما تاثیر ناخوشایند بگذارند. با این فرض تضمین میکنیم اگر در حالت واقعی همین اتفاق روی دهد جواب بهینه استوار ما بطور قطعی موجه خواهد بود. همچنین با توجه به توزیع متقارن متغیرها، حتی در صورت آنکه تعداد ضرایبی که تغییر میکنند از ⌊ ⌋ نیز بیشتر شود، جواب بهینه با احتمالی خیلی بالایی موجه خواهد ماند. لذا را سطح حفاظت24 برای محدودیت ام مینامیم.
پارامتر 0 سطح استواری در تابع هدف را کنترل میکند. بنابراین میخواهیم مقدار جواب بهینه را در حالتهایی پیدا کنیم که 0 تا از ضرایب تابع هدف تغییر میکند و بیشترین تاثیر را روی جواب میگذارد.
در حالتهای کلی مقادیر بالاتر 0 سطح محافظهکاری را در مقابل هزینه بیشتری که به ازای آن باید در تابع هدف پرداخت کنیم بالا میبرد. 0 لزوما باید عدد صحیح و سایر ها میتوانند صحیح یا غیر صحیح باشند.
