نشریه تخصصی مهندسی صنایع، دوره 48، شماره 2، مهر ماه 1393، از صفحه 189 تا 200
ارائه مدل دوهدفه برای م ئلة زمان بندی جریان کارگاهی با محدودیت دسترسی به ماشی ها

محمد رضایی ملک1، رضا توکلی مقدم2 * و فرشید عوضآبادیان3
دانشجوی دکتری مهندسی صنایع پردیم دانشکده های فنی دانشگاه تهران
استاد دانشکدة مهندسی صنایع پردیم دانشکده های فنی دانشگاه تهران
کارشناس ارشد مهندسی صنایع پردیم دانشکدههای فنی دانشگاه تهران

)تاریخ دریافت 29/4/92 ـ تاریخ دریافت روایت اصلاحشده 20/2/93 ـ تاریخ تصویب 24/3/93( چکیده
در این مقاله یک مدب ریاضی دوهدفة جدید برای مسسلة زمان بندی جریان کارگاهی جای گشتی در حالـت بـدون ایسـت بـا فـرض عـدمدسترسی به ماشین ها، به دلیل عملیات نگهداری و تعمیرات )نت( پیشگیرانه، ارائه می شود. این مدب شامل دو هدا حـداقل سـازی دامنـةعملیات و حداقلسازی مجموع زودکرد و دیرکرد است. عملیات نت درنظرگرفتهشده در این مقاله مدت زمـان ثابـت دارد و مـ ی توانـد هـرلحظه روی ماشین ها شروع شود. اما زمان بین دو عملیات نت متوالی نباید از یـک مـدت زمـان مشـخص بیشـتر باشـد. بـرای حـل مـدبپیشنهادی از روش وبیشف سطح اخیره استفاده و نتایج عددی به دست آمده از اجرای مدب به کمک این روش گزارش شد. مقایسة نتـایجاین روش با روش محدودیت اپسیلون کارآمدی روش وبیشف سطح اخیره را نشان می دهد.

واژه های کلیدی: بهینه سازی دوهدفه، دامنة عملیات، زمان بندی جریان کارگاهی جای گشتی، مجموع زودکـرد
و دیرکرد، نت پیشگیرانه

مقدمه
مسسلة زمان بندی به معنـای تعیـین تـوالی انجـام دادن کارها به گونه ای است که هـدا معینـی را در سیسـتمیمفروض برآورده کند. در این مسسله تعـدادی کـار وجـوددارد. در هر لحظه هر ماشین حداکثر می تواند یک کـار راپ ردازش کن د و ه ر ک ار را بای د تع دادی از ماش ین ه ا پردازش کنند. زمان پردازش کار i بر ماشین j به صـورتpij نمایش داده مـی شـود. بـر حسـب تعـداد ماشـین هـا،سیستم ها به دو نوع تک ماشـینه 1 و وندماشـینه تقسـیممی شوند. سـه مـدب از مـدب هـای مشـهور بـرای حالـتوندماشــینه عبــارت انــد از جریــان کارگــاهی2، کــار کارگارهی3، و کارگاه باز4. در جریان کارگاهی هر کـار بـهm عملیات نیاز دارد که اولین عمل آن باید روی ماشـین1m، دومین عمل آن روی ماشین 2m، و به همین ترتیـبروی بقیة ماشین ها انجـام شـود ]1[. در مسـسلة جریـان

نویسندة مسسوب: تلفن: 82084183
کارگاهی جای گشتی ترتیب پردازش کارها روی ماشین ها برای هر مرحلة بعدی پردازش یکسان است ]1[.
هر یک از مدب های اشاره شده می توانند مفروضات و محدودیت هایی داشته باشند .زمان دسترسی بـه کـار5، زمـان راه ان دازی6، قابلی ت انقط اع7، پ یش نی ازی8، و دردسترس بودن9 از این مفروضـات و محـدودیت هاسـت]1[. در بیشتر تحقیق هایی کـه در زمینـة زمـان بنـدیکارها صورت گرفته، فرض شده ماشین ها همـواره بـرایپردازش در دسترس اند. ولی این فرض در فضای واقعـیصنعت در بیشتر موارد درست نیست. زیرا ممکن اسـتیک ماشین ی دورة زمانی خاصی، به دلایلی همچـونخرابی ماشین10 یا عملیات نگهداری و تعمیـرات )نـت(پیشگیرانه11، در دسترس نباشـد. در صـورتی کـه عـدمدسترسی به ماشین ها به دلیل عملیات نـت پیشـگیرانه Email: [email protected]
باشد، دو حالـت ممکـن اسـت رخ دهـد. حالـت اوب آناست که زمان عملیات نت مشـخص باشـد و در حالـتدیگر ممکن است زمـان شـروع عملیـات نـت از پـیشتعیین نشده و به متلیر تصمیم وابسته باشد؛ وری که این عملیات می تواند در هر لحظه روی ماشین ها شـروعشود، ولی زمان بین دو عمل نت متوالی نباید از مقـدارمشخصی بیشتر باشد. این پژوهش به بررسی مسسله در حالت دوم پرداخت.
ه ر دورة ع دم دسترس ی ب ه ی ک ماش ین را ی ک حفره12 مینامند. بسته به عملکرد ماشین ها روی کارها ،می توان سه سناریو13 برای عملی کـه بخشـی از آن بـهعلت عدم دسترسی ناتمام مانده اسـت در نظـر گرفـت؛ســناریوی قابــل ادامــه دهــی14، ســناریوی ییــر قابــلادامه دهی15، سناریوی شـبه قابـل ادامـه دهـی16]1[. در سناریوی ییر قابل ادامه دهی، بعد از حفره، زمـان عمـلبرابر کل زمان عمل اصلی است. به عبارت دیگر، در این حالت، در صورت وقوع خرابی، عمل باید از سـر گرفتـهشود. در این پژوهش سناریوی ییر قابل ادامـه دهـی درنظر گرفته شد.
اهداا متفاوتی در توالی کارها در مسسلة زمان بندی دنب اب م یش وند؛ از جمل ه ]1[: ح داقل س ازی دامن ة عملیات17، حداقل سازی حداکثر دیرکرد18 )فاصلة زمانی بین زمان موعد تحویل یـک کـار و زمـان تکمیـل آن(،حداقل سازی مجمـوع زمـانهـای تکمیـل19 )وزنـی (20، حـــداقل ســـازی مجمـــوع دیرکـــرد 21 )وزنـــی(22، و حداقل سازی مجموع زودکرد و دیرکرد23. حداقل سـازیدامنة عملیات عبارت است از حداقل سازی زمان تکمیل همة کارهایی که باید در برنامـه ریـزی انجـام شـود. بـهعبارت دیگر، زمانی را که آخـرین کـار تمـام مـی شـودحداقل می کند. حداقل سازی مجموع زودکرد و دیرکـردعبارت است از حداقل سازی مجموع زودکـرد و دیرکـرداز زمان موعد تحویل کارها.
پیشینة تحقیق
مطالع ات بس یاری در زمین ة بررس ی عملی ات ن ت در سیستم جریان کارگاهی صـورت گرفتـه اسـت. در ایـنمی ان سیس تم جری ان کارگ اهی ب ا دو ماش ین توج ه بیشتری به خود معطوا کرده است [2].
مسئلة دوم شینه
اولین مسسلة دوماشینة جریان کارگاهی با درنظرگیـریمحدودیت دسترسـی را لـی ]3[ بررسـی کـرد. اگروـهمســسلة دوماشــینة ســاده، بــدون وجــود حفــره رویماشین ها، قابل حل با روش قانون جانسـون 24 در زمـانخطی بود، او با درنظرگرفتن یک حفره روی ماشین اوب ثابت کرد که این مسسله NP-hard25 است و یـک روشبرنامه ریزی پویـا 26 بـرای حـل بهینـة آن ارائـه کـرد. اوهمچنین دو روش ابتکاری27، یکی در صورتی کـه یـکحفره روی ماشین اوب رخ دهد و دیگری بـرای حـالتیکه حفره روی ماشین دوم رخ دهد، ارائه داد. آلایـوی وهمکاران ]4[ اعلام کردند در صـورتی کـه زمـان حفـرةاوب به ور دقیـق برابـر باشـد بـا زمـان پـردازش کـلکارهای مجموعه ای که قبـل از حفـره واقـع مـیشـود،آن گ اه الگ وریتم جانس ون28 ب ه ج واب بهین ه منج ر میشود. آن ها این موضـوع را بـا مقایسـة زوجـی ثابـتکردنــد. بریــت ]5[ و انجــی و کوالیــوا ]6[ مســسلة دوماشینه با وجود یک حفره روی ماشین اوب را مطالعه کردند. آن ها ابتدا خصوصیت هایی را برای تـوالی بهینـهبیان کردند و روشی ابتکاری با بدترین خطای نسـبی29 2/3 ب رای مس سله ارائ ه دادن د. ل ی ]3[ نش ان داد در صورتی یک توالی بهینه برای مسسله وجـود دارد کـه درآن مجموع ه کاره ایی ک ه بع د از ماش ین دوم انج ام میشود و سایر کارهـای بـاقی مانـده بـر اسـاس قـانونجانسون مرتب شده باشد. ان جی و کوالیـوا ]6[ ثابـتکردند جواب بهینه ای وجود دارد که در آن کارهایی که روی ماشین دوم بعد از حفـره رخ مـیدهـد بـر اسـاسقانون جانسون مرتب شده است. وانگ و ونگ ]7[ برای همین مسـسله، در صـورتی کـه زمـان آمـاده سـازی بـهفرضیات اضافه شود، روشی ابتکاری بـا بـدترین خطـاینسبی 3/2 ارائه کردند.
مسائل زمان بندی به وسیلة سهگانـةα|β|γ توصـیفمی شوند .α محیو کاری را توصیف می کند و شامل یک نهاده می شود .β ویژگی ها و محـدودیت هـای فرآینـد راتوصیف می کند و ممکن است هی ویژگـی خاصـی بـهوسیلة آن بیان نشود )بدون نهاده( .γ بـه هـدفی اشـارهمی کند که حداقل سازی مـی شـود و فقـو شـامل یـکنهاده می شود ]1[.
با توجه به فرض های قابل ادامـه دهـی و شـبه قابـلادامه دهی و ییر قابل ادامه دهی بودن کارها، تحقیق های زیادی انجام شده است. لـی ]8[ مسـسله هـای -F2,h11|sr
F2,h21|sr-a|Cmax ،a|Cmax، و F2,hj1|sr-a|Cmax را بررسی کــرد .Fm سیســتم mماشــینه را نشــان مــی دهــد .hji بیان کنندة تعداد حفرههایی) i( است که روی ماشـینj اتفا می افتد .sr نشان دهندة قابلیت شبه ادامه دهی کار است. و a محدودیت دسترسی بـه ماشـین هـا را نشـانمی دهد. لی در پژوهش خود] 8[ از پارامتر αای استفاده کرد که نشان دهندة درصد کـاری اسـت کـه بعـد از دردسترس قرار گرفتن ماشین باید دوبـاره پـردازش شـود)α≤1(. او نش ان داد الگ وریتم جانس ون ب رای مس سلة F2,hj1|sr-a|Cmax به جواب بهینـه منجـر خواهـد شـد وبرای مسسلة قابل ادامـه دهـی ) F2,hj1|r-a|Cmax,α=0 ،)r، درنظرگرفتن فـرض تـوالی ثابـت مناسـب اسـت. بـرایمس سلة F2,h11|sr-a|Cmax او ی ک الگـوریتم ب ر مبن ایبرنامه ریزی پویا ارائه کرد و نشان داد الگوریتم جانسـونبه جوابی با شعاع خطای کووک تر از 1 منتهی می شود .ل ی ]8[ ب رای مس سلة F2,h21|sr-a|Cmax نش ان داد ک ه الگوریتم جانسون به جوابی بـا محـدودة خطـای ≤RJAmax{1/2,α} منتهــی مـی ش ود. همچن ین نشــان دادمسسلة F2,hj1|sr-a|Cmax، با فرض α>0، مسسلة NP-hard است و الگوریتم جانسون برای این مسسله به جوابی بـاشعاع خطایα منجر می شود) RJA≤α(. ونـگ و وانـگ]9[ حالت خاصی از مسسلة F2,h21|sr-a|Cmax را در نظـرگرفتنـ د و راهحلـ ی ابتکـ اری، بـ ا بـ دترین حالـ تنسبی 3/2≤RH، برای حالت شبه قابل ادامـه دهـی ارائـهکردند. در حالت ییر قابـل ادامـهدهـی ) nr(، آلایـوی و
همک اران ]4[ مس سله را ب رای ح التی ک ه فق و ی ک مح دودیت دسترس ی روی ماش ین اوب داش ته باش یم )F2,h11|nr-a|Cmax( مطالع ه کردن د. آنهـا ی ک م دب برنامهریزی پویا بق آنچه لی ]3[ گفته بود ارائه کردند که مستقل از زمان پـردازش کارهـا بـود. ایـن موضـوعموجب شد حجم محاسبات جهت جست وجـوی جـواببهینه کاهش یابد. آنهـا همچنـین شـرایطی را مطـرحکردند که در آن قانون جانسون به جواب بهینـه منجـرمی شود و ثابت کردند در سـایر شـرایو بـدترین حالـتخطای نسبی قانون جانسون کمتر یـا مسـاوی 1 اسـت.
آلایوی و آرتیبا ]10[ مسسلة جریان کارگاهی ترکیبی با محدودیت دسترسی را به منظور حـداقل سـازی دامنـةعملی ات در حال ت دوماش ینه در نظ ر گرفتن د. آن ه ا برنامه ریزی پویایی برای مسـسله ارائـه دادنـد و آن را بـاالگوریتم شاخه و کران حل کردند.
در مسسلة جریان کارگاهی دوماشینه بـا محـدودیتاخیره، اگر کاری روی ماشین اوب تمام شد ولی ماشین دوم همچنــان مشــلوب کــار بــود، کــار بــدون هــی محدودیتی می توانـد اخیـره شـود تـا ماشـین دوم آزادشود. اما در مسسلة جریان کارگاهی دوماشینه، در حالت بدون ایست، امکان توقف کار بین ماشین ها وجود ندارد .
زمان شروع پردازش کار روی ماشین دوم برابر اسـت بـازمان تکمیل کار روی ماشین اوب. همة کارهـا بایـد بـه ور پیوسته، بدون تأمل بین ماشین ها، انجام شـود. درادامه، مسسلة دوماشینة جریان کارگاهی بدون ایست، بـادرنظرگرفتن محدودیت دسترسی، بررسی می شود.
این مسسله با درنظرگرفتن فقو یک حفره روی یک ماشینNP-hard خواهد بود و در صـورتی کـه بـیش ازیک حفره روی یکی از ماشین ها داشته باشـیم، مسـسلهبه شدتNP-hard خواهـد شـد. اسـنینوس و همکـاران]11، 12[ روشی ابتکاری بـر پایـة الگـوریتم گیلمـور وگومری30 با بدترین حالت نسبی 1≤RH، برای حالتی که فقو یک حفره روی ماشین اوب باشد، ارائه دادند؛ بـرایدو حالت قابل ادامه دهی و ییر قابل ادامـه دهـی. آن هـاهمچنین روش ابتکاری دیگری برای این مسسله با یـکحفره روی ماشین دوم، برای دو حالت قابل ادامه دهی و ییر قابل ادامه دهی، ایجـاد کردنـد کـه خطـای نسـبی آن1≤RH است. وانگ و ونگ ]13[ دو الگـوریتم بهبودیافتـه برای دو مـدب ییـر قابـل ادامـه دهـی ارائـه دادنـد کـهاسنینوس و همکاران ]11[ آن را مطالعـه کـرده بودنـد.آن ها در الگوریتم خود 3 تا 5 توالی برای مسـسله ایجـادمی کردند و سنم کووک ترین عدد را از میـان مقـادیردامنة عملیات بـه منزلـة الگـوریتم بهبودیافتـه معرفـیمی کردند. آن ها نشان دادند الگوریتم بهبودیافتة جدیـددارای بدترین حالت نسبی 3/1 است. ونـگ و لیـو ]9[ یـکPTAS 31 ب رای حال ت ییـر قاب ل ادام ه ده ی، در صورتی که یک حفره روی فقو یک ماشین رخ دهـد ودردسترس نبودن دو ماشین با هم تداخل نداشته باشـد،ارائه دادنـد. کـوبزین و استراسـوی ]14[ مسـسله را بـاوجود یک حفره روی ماشین دوم مطالعه کردنـد. آن هـاسه حالت )قابل ادامه دهی، ییر قابل ادامـه دهـی، شـبهقابل ادامه دهی( را در نظر گرفتنـد و نشـان دادنـد کـهمسسله با وجود یـک حفـره روی ماشـین اوب NP-hard است و این نتیجه به راحتی برای یک حفره روی ماشین دوم قابل تعمیم خواهد بود. آن ها برای مسـسله بـا یـکحفره روی ماشین دوم الگوریتمی تقریبی برای هر سـهحالت با بدترین حالت نسبی 2/1 و الگوریتمی با بدترین
حالت نسبی 3/4 برای مسـسلةF2,h21|r-a,no-wait|Cmax ارائه دادند.
مسئلة چندم شینه
آگون ]15[ مسـسله ای را بـا وجـود ونـدین دوره عـدمدسترسی بـرای هـر ماشـین در نظـر گرفـت) -Fm,hjk|ra,no-wait|Cmax(. از آنجا که این مسـسله بـهشـدت -NPhard است، او در تعریف مسسلة خـود بـرای هـر حفـره یک پنجرة زمانی32 در نظر گرفت که عملیات نـت بایـددر آن صورت می گرفت. او ابتدا ثابت کرد فرضیة تـوالییکسان کارها برای همة ماشین ها در حالت جدید برقرار نیست و اگر یک کار در ماشین اوب زودتر از کار دیگری انجام شده باشد، می تواند در ماشین دوم بعد از کار دوم انجام شود تا جواب بهینـه شـود. او همچنـین دو روشفراابتکاری33، یکی بر پایة الگوریتم ژنتیـک 34 و دیگـریبر اساس جسـت وجـوی ممنـوع35، بـرای حـل مسـسلهپیشنهاد کرد. آگون و پورتمن ]16[ روشی ابتکـاری بـرپایة روش هندسی36 برای حل این مسسله ارائـه کردنـد.در روش آنها کارها به صـورت زوجـی انتخـاب و روشهندسی برای آن ها اجرا می شود. بر پایة ایـن الگـوریتم،آن ها روشی ابتکاری برای حل تقریبی مسسله با بیش از دو ماشین ارائه کردند.
مینلا و همکاران ]17[ مقالات ارائه شـده در زمینـةالگوریتم های زمان بندی کارگاهی وندهدفـه را مـرور وارزیابی کردنـد. مختـاری و همکـاران ]18[ یـک مـدبدوهدفه برای زمان بندی کارگـاهی بـا فـرض وابسـتگیزمان پردازش به منابع در دسترس ارائه دادند. آن هـا دوهدا حداقل سازی زمان تکمیل نهایی و حـداقل سـازیک ل هزین ة من ابع را ب رای مس سله در نظ ر گرفتن د.
فرانســولینی و همکــاران ]19[ الگ وریتم اصــلاح شــدة جست وجوی هارمونی37 برای مسسلة زمان بندی جریـانکارگ اهی وندهدفــه ارائــه دادن د. آن هــا ســه هــداحداقل سازی حداکثر دیرکرد، زمان جریـان، و حـداکثرمدت تکمیل کـل کارهـا را در نظـر گرفتنـد. خلیلـی وت وکلی مق دم ]20[ ی ک الگ وریتم الکتروملن ا یم38 دوهدفه برای مسسله ارائه دادند. آن ها دو هدا حـداکثرمدت تکمیل کارها و مجموع دیرکـرد وزنـی را در نظـرگرفتند. در پژوهش حاضر دو هدا حداقل سازی دامنـةعملیات و مجموع زودکرد و دیرکرد، بـه منزلـة اهـداامسسله، در نظر گرفته شد.
مرور پیشینة تحقیق نشان داد تحقیقات بسیاری در زمین ة مس سلة زم ان بن دی کاره ا در سیس تم جری ان کارگاهی با درنظرگـرفتن عملیـات نـت صـورت گرفتـهاس ت. در ای ن پ ژوهش ه ا ایل ب بهینگ ی مس سله وخصوصیات جواب بهینه در حالت دوماشینه بررسی شده و مطالعات بسیار کمی در زمینـة مسـسلة وندماشـینه درسیستم جریـان کارگـاهی انجـام شـده اسـت. تحقیقـاتانجام شده در این حوزه فقو مطالعات آگون ]15[ و آگون و پورتمن ]16[ اسـت. آگـون ]15[ روشـ ی ترکیبـی از الگوریتم ژنیک و جست وجوی ممنوع برای رسـ یدن بـهجوابی تقریبی در حالت تک هدفه )حداقل سـاز ی دامنـ ة عملیات( ارائه کرد. او برای عملیات نـت پنجـرة زمـان ی مشخص کرد؛ به گونه ای که زمان مجاز شـروع و پا یـان عملیات نت مشخص است. نیز، آگـون و پـورتمن] 16[ یک الگوریتم تقریبی ابتکاری برای زمان بندی دوبه دوی کارها، مبتنی بر روش هندسی، با هـدا حـداقل سـاز ی دامنة عملیات، ارائه کردند. تفاوت پژوهش حاضـر بـا دو پژوهش یادشده عبارت اسـت از الـف( ارائـ ة یـک مـدبریاضــی عــدد صــحیح مخــتلو بــرا ی مســسله؛ ب( حداقل سازی هم زمان دو هدا دامنة عملیات و مجموع زودکرد و دیرکرد؛ ا( درنظرگرفتن پنجرة زمـان ی بـرا ی عملیات نت، به گونه ای که فاصلة بین دو عملیـات نـتمتوالی از یک مدت زمان مشخص بیشتر نباشد .مزیـت اصلی درنظرگرفتن پنجرة زمانی بدین گونـه ، نسـبت بـهآنچه آگون] 15[ انجـام داده اسـت، ایـن اسـت کـه درواقعیتْ حضور تجهیزات و افراد لازم برای عملیـات نـتدر بازه های زمانی مشخص همیشه امکان پـا یر نیسـت؛ در حالی که پنجرة زمانی تعریف شـده در ایـ ن پـژوهش اجباری به انجام دادن عملیات در بازه ای مشخص ندارد، بلکه فراینـد را ملـزم بـه عملیـات هـای نـت متـوالی در حداکثر فاصلة مجاز مـ ی کنـد ، ـور ی کـه ایـن فـرضانعطاا پایری بیشتری را برای برنامه ریزی تسهیلات در محیو کار فراهم می آورد.
به ور خلاصه، پژوهش حاضـر بـه مطالعـة جریـانکارگاهی جای گشتی وندماشینه در حالت بدون ایست ،با درنظرگرفتن محدودیت دسترسی بـه ماشـین هـا، بـهدلیل عملیات نت پیشـگیرانه، مـی پـردا زد و یـک مـدبریاضی جدید برای مسسله ارائه می دهد. دو تـابع هـداحداقل سـازی دامنـة عملیـات) Cmax( و حـداقل سـازیمجمــوع زودکــرد و دیرکــرد در قالــب مــدب ریاضــیوندهدفه در نظر گرفته شد.
توصی مسئله
در این قسمت فرضیه هـای مسـسله تشـریح و در ادامـهمدلی ریاضی برای مسسله ارائه می شود.
مف وض ت
تعداد n کار و m ماشین وجـود دارد. ترتیـب و تـوالیماشین ها ثابت است و هر یک از کارها باید توسـو هـریک از ماشین ها پردازش شود. اما زمان پـردازش کارهـا)pij( )زمان پردازش کار i روی ماشین j( متفاوت اسـت .
برای هر یک از ماشین ها دوره هـایی وجـود دارد کـه درآن ها ماشین ها در دسترس نیستند و تحت عملیات نت پیشگیرانه قرار می گیرند. زمان شروع عملیات نت ثابـتنیست؛ ولی زمان بین دو عمل نت نباید از مـدت زمـانمشخصی) q j ( بیشتر باشد. همچنین در هر عمل نـتپیشگیرانه برای هر ماشین زمـان مشـخص) wj( صـرامی شود.
در این پژوهش سناریوی ییـر قابـل ادامـه دهـی درنظر گرفته شد و مسسلة جریان کارگاهی جای گشتی بـافرض بدون ایست بررسی شد.
متغی ه مسئله
xit در صورتی که کار iام) i=1,…,n( به عنوانt امـین)t=1,…,n( کار توالی پردازش شود برابر 1 و در ییر این صورت 0 خواهد بود.
cijt زمـان تکمی ل ک ارi ام روی jامـین) j=1,…,m( ماشین، اگر کار i به منزلة tامین کار وارد ورخة کـاریشود؛ در ییر این صورت برابر 0 است.
rjt زمان تمامشدن کار ماشینj ام روی کاری کـه بـهعنوان کارt ام وارد ورخة کاری می شود.
kijt حــداکثر مقــدار بــین دو مقــدار 1-rjt و cij-1t، در صورتی که مقدار xit برابر 1 باشد.
mkj زمان پایان یافتن عمـل نـتk ام) k=1,…,S( روی ماشینj ام.
sjt زمان تکمیل کار توالیt ام روی ماشین jام.
ykjt اگرk امین عمل نت روی ماشینj ام درست بعد از عمل پردازش رویt امین کار ورودی صورت گیرد برابـر1 است؛ در ییر این صورت برابر 0 است.
Ψi تفاوت بین زمان تکمیل کـارi ام و موعـد تحویـلآن.
M عدد بزرگ.
مدل ضظ
با توجه به فرضیه های یادشـده، روابـو 1 تـا 17 بـرایمسسله ارائه می شود:
n min z1  cimn )1(
i1
n
min z2  i )2(
i1
s.t.
cijt  kijt  pij  xit , ,i j t )3(
kijt  rjt1  0 i j t, , )4(
kijt cij1t   M1 xit i j t, , )5(
n
 xit  1  t )6( i1
n
 xit  1  i )7( t1
ns
rjt  cijt   ykjt  wj j t,
i1k1 )8(
m
 cijt  M  xit i t, j1 )9(
n
 ykjt  1 j k,
t1 )10(
nn
t  yk1jt  t  ykjt k j,
t1t1 )11(
mkj  sjt   M1 ykjt k j t, , )12(
mk1j  mkj  qj k j, )13(
S
 ykj10  0 j k1 )14(
S
 ykjt  1 j t,
k1 )15(
290263-14647

824621-14647

n
i cimtdi i
t1 )16(
x y, 0,1 s c r k m, , , ,  0 )17(

رابطة 1 هدا حداقل سازی دامنة عملیات را نشـانمی دهد. در این رابطه m آخرین ماشین و n آخرین کـاراست. رابطة 2 هدا حداقل سازی برای مجموع زودکـردو دیرکرد را نشان می دهد. رابطة 3 بیـان کننـدة رابطـةبازگشتی بین انجام دادن کارهاسـت. رابطـه هـای 4 و 5 مشخص می کنند منظور از kijt حـداکثر مقـدار بـین دومقدار 1-rjt و cij-1t است، در صورتی که مقدار xit برابر 1 باشد. به عبارت دیگر، زمان شروع کـار ماشـینj ام روی قطعه ای که به منزلة t امین کار وارد ورخه شـده برابـراست با حداکثر مقـدار بـین اتمـام کـار قطعـةt ام روی ماشین 1-j و زمان اتمام کـار ماشـینj ام روی قطعـهای که در توالی 1-tام وارد ورخه شده است. دو رابطـة 6 و 7 بیان می کند که هر یک از کار ها بایـد در یـک نوبـتوارد شود و هر یک از نوبتهـا بایـد بـه یکـی از کارهـااختصاد پیدا کند. محدودیت 8 زمان تمـامشـدن کـارماشین jام را روی کاری نشان می دهد که به منزلة کـارtام وارد ورخة کاری میشود. محدودیت شمارة 9 بیـانمی کند در صورتی که کار i به منزلة tامـین کـار تـوالی
نباش د، حتم اً هم ة مق ادیر cijt برابـر 0 خواه د ب ود .محدودیت 10 بیانگر این موضوع است که عمل نت kام هر ماشین باید قبل از یکی از ماشین های توالی 1 تـا n انجام بنایرد. محدودیت 11 نشان دهندة این اسـت کـهشمارة کـاری )تـوالی( کـه عمـل نـتk روی آن انجـامگرفته باید از شمارة کاری )تـوالی( کـه عمـل نـت 1+k روی آن انجام شده بزرگ تر باشد. محـدودیت 12 و 13 تضمین می کند فاصلة زمانی بین دو عملیات نـت بایـد کووکتر یا مساوی qj باشد. وـون ممکـن اسـت همـةعم ل ه ای ن ت بع د از عم ل دََه م رخ دهن د. ب رایجلوگیری از این مشکل رابطة 14 را اضافه مـی کنـیم ووون ممکن است دو عملیات نت بعد از یک ماشین رخ دهن د، ب رای ح ل ای ن مش کل رابط ة 15 را در نظ ر می گیریم. محدودیت 16 تفاوت بین زمان تکمیل کارها و موعد تحویلشان) di( را نشان می دهد که محـدودیتیییر خطی است؛ بنابراین به صورت رابطه های 18 و 19 بازنویسی می شود:
n cimt  di i i )18(
t1
n cimt  di i i )19(
t1
وش حل
در حل مسـائل وندهدفـه دسـتیابی بـه جـواب بهینـهامکان پایر نیست .فقو می توان به مجموعة جـواب هـاینزدیک به بهینه رسید )مرز پارتو(39. در ونین شرایطی ،در این پژوهش، با درنظرگرفتن ویژگی مطالعـة مـوردیمطرح شده، تصمیم گرفته شد تصمیم گیرنـده یـا کـاربرسیستم بتواند ترجیحات خود را با توجه به جـواب هـایبه دست آمده و محدودیت های فنی مطرح کند.
در شرایو حضـور ونـدین جـواب از یـک ـرا وترجیحات تصمیم گیرنده از را دیگـر، بـرای ورود بـهفاز عملیاتی نیاز به روشی که بتوانـد یـک جـواب را بـهمثابة جواب نهایی مطرح کند احساس می شود. با توجه به شرایو مطرح شده، روش های تعـاملی 40 برنامـه ریـزیوندهدفه از سایر روش های موجود در حوزة برنامه ریزی وندهدف ه مناس ب ترن د. یک ی از ای ن روش هـا روش RLTP41 است. در این روش ،از سازوکاری ساختاریافته برای کاهش جواب هـای ییرمللـوب42 اسـتفاده شـد تـامرجح ترین جواب مدنظر تصمیم گیرنده بـه دسـت آیـد.
این روش سطوح اخیـره 43)RLs( را بـا توجـه بـه نظـر تصمیم گیرنده برای کاهش فضای هدا به کار می گیرد.
روش محدودیت اپسیلون44 مشابه RLTP از سطوح اخیره برای حل مسـائل وندهدفـه اسـتفاده مـی کنـد.
بن ابراین، در ای ن پ ژوهش روش RLTP و محـدودیت اپسیلون برای حل مسسلة زمانبندی بـه کـار رفـت. درادام ه دو روش RLTP و مح دودیت اپس یلون توض یح داده خواهد شد.
RLTP وش
روش RLTP شامل وهار گام برای اجراست ]21[:
مقداردهی اولیه
تعیین تعداد جواب هایی) N( که در هر مرحله بایـدبه تصمیم گیرنده ارائه شود؛ وری که P( N ≥ P تعـداداهداا مسسله( است. سنم محاسبة بردار مرجع) yI( بـاحل P مسسلة تک هدفه به صورت زیر صورت می پایرد:
 1 , 2I ,, yIp, yI y yI
Iyk  min fk( )x x X;    k 0 and  k 1 to p εk یک عدد مثبت کووک است که در دسـتور کـارروش وبیشف استفاده می شود. مقدار RLkها یا سـطوحاخیره، ـوری کـهk=1, …, p اسـت، برابـر ∞+ قـرارمی گیرد. حداکثر تعداد تکرارها45 نیز باید مشخص شود.
نمونه گیری
با اسـتفاده از رابطـة 20 گروهـی شـاملN 2 بـردارمتمایز از هم تولید می شود.
614971-111812

Λ  Rpk0,1 ,  pk1 )20(
k1
حل
در این مرحله مدب وبیشف )رابطه های 21 تـا 25( برای هر λ، که در گـام 2 بـه دسـت آمـده اسـت، حـلمی شود:
 p  min  fkx )21(  k1 
:وری که x X , )22(
  k  fkxykI    k 1, , p )23( fk x  RLk   k 1, , p )24(
بق نظر استییور ]22[، ρ عددی مثبت و کووـکاست که پیشنهاد می شود عددی بین 0001/0 تـا 01/0 انتخاب شود. در این پژوهش عدد 0001/0 انتخاب شده است. حاب N جواب، که به صورت حداکثری متمـایز ازهم46 هستند، به شیوة ارائهشده در مقالة استییور ]22[ انتخ اب م یش ود. س نم N ج واب انتخ ابش ده ب ه تص میم گیرن ده ارائ ه م ی ش ود. اگ ر تص میم گیرن ده جواب های بهتری را مدنظر دارد، به گام 4 میرویـم. درییر این صورت، تصمیمگیرنده مرجح ترین جـواب خـودرا انتخاب می کند و بدین ترتیب حل پایان می پایرد.
4. تنظیم و تعدیل
بق نظر تصمیم گیرنده، جواب های به دست آمده به دو مجموعه تقسیم مـی شـوند؛ جـواب هـای بـا تـرجیحبیشتر و جوابهای با ترجیح کمتر. سنم RLkها دوباره به ریق زیر تنظیم می شوند و به گام 2 بـازمیگـردیم.اگر تصمیم گیرنـده نظـری نداشـته باشـد، مـی تـوان بـااستفاده از فرایندی خودکار توسو RLTP، با استفاده از رابطة 25، RLkهای جدید تنظیمشده را به دست آورد:
RLk  MPWVk  r MPWVkCSWVk )25(
جایی که CSWVk بدترین مقـدار در کـل مجموعـة جوابهای فعلی و MPWVk بدترین مقـدار در مجموعـة جوابهای با ترجیح بیشتر است. همچنین r بـه منزلـةفاکتور کاهش عددی بین 0 و 1 خواهد بود؛ وری کـههر قدر به 1 نزدیکتـر باشـد فضـای اهـداا سـریع تـرکووک می شود. پم از تنظیم RLkهای جدید دوباره به گام 2 بازمیگردیم. این رونـد ادامـه پیـدا مـی کنـد تـاتصمیم گیرنده جواب های مورد نظر خود را انتخاب کند.
وش محدود اپسیلون
هیم ز و همک اران ]23[ روش مح دودیت اپس یلون را برای اولین بار مطرح کردند. در این روش یکی از توابـعه دا ب رای بهین هس ازی انتخ اب و تواب ع دیگ ر ب ه محدودیت تبدیل می شوند. این محدودیت ها حد بالایی دارند) εi( که می توان آن ها را مقادیر RLkها فرض کـرد.
یالب مسسله به روش محدودیت اپسیلون به شـکل زیـر است:
Min fj(x) s.t.
(fi(x) ≤ εi For all i=1, 2; j≠i (εi =RLkحاب، با استفاده از روش های ارائه شده در بخش بعد ،نتایج حل مسسله ارائه می شود.
مط لعة مو د
بــرای نشــا ن دادن قابلیــت اجــرا و ســودمندی مــدبپیشنهادی و روش حل به کارگرفته شده، روش RLTP و محدودیت اپسیلون در نرم افزار GAMS47 کد شـد و بـا دادههای مطالعة موردی در جدوب 1 حـل شـد. مقـادیرزمان های بین دو عملیات نت متوالی کمتـر یـا مسـاویمقدار ثابت 30 دقیقـه در نظـر گرفتـه شـد. در ادامـه،نتایج، به تفکیک هر روش، گزارش میشود.
RLTP وش
در اولین مرحله، تصمیم گرفته شـد در هـر تکـرار سـهجواب به تصمیم گیرنده ارائه شـود ) 3=N(. جـواب هـایحاصل از حل مسائل تکهدفه در جدوب 2 مـی آیـد . در مرحلة دوم، شش بردار وزنی متمایز از هم، با توجـه بـهمقالة استییور ]22[، به صورت تصادفی تولید می شـود.در مرحلة سوم مدب وبیشف مربو ه بـرای هـر λ حـل میشود و نتایج در جدوب 3 می آید. در جدوب 3 آنچه با علامت * مشخص شده نشان دهندة حلهای با بیشـینةتمایزند که با روش پایشی که استییور ]22[ ارائه کـردهبه دست آمدهاند. اگر این نتایج رضایت تصمیمگیرنده را در بر داشـته باشـد، او بایـد مـرجح تـرین جـواب مـوردنظرش را انتخاب کند و بدین ترتیب حل پایان می یابد. در این مسسله تصـمیم گیرنـده جـواب پـنجم را بـهمنزلة مرجح ترین جواب انتخاب می کند. در ایـن جـوابتوالی کارها بـه ترتیـب 2، 10، 4، 8، 5، 9، 1، 3، 6، 7 است. مقدار Cmax و مجموع زودکرد و دیرکرد برای ایـنمسسله به ترتیـب برابـر 548/650 و 355/955 اسـت وتصمیم گیرنده امیدوار است در جسـت وجوهـای بعـدیجواب بهتری پیدا شود .RLkهای جدیـد بـا اسـتفاده ازرابطة 25 محاسبه می شود:
RL1 = 650.548 – 0.2 × (650.548 – 1090) =
738.4384 توسو تصمیم گیرنده اعلام شده است :059 = 2RL

جدول 1. زم ن پ دازش ک i و م شین j
pij 1 2 3
1 30 80 20
2 10 20 40
3 50 40 12
4 20 60 25
5 40 20 34
6 70 30 18
7 10 50 16
8 10 120 21
9 50 110 30
10 80 30 40

جدول 2. مق د بهینة توابع هد ح صل از حل تک هدفة مسئله
حل بهینه برای مدب تک هدفه Z1 Z2
حل بهینه برای 1z 582 3138
حل بهینه برای 2z 1050 166
مقدار ایده آب= yIK 581.9 165.9
جدول 3. مق د ب دا وزنظ و ت بع اهدا به دس آمده از مدل چبیش
1 *2 3 *4 *5 6
λ1 0.90 0.40 0.85 0.19 0.92 0.28
λ2 0.10 0.60 0.15 0.81 0.08 0.72
Z1 653.092 882.387 702.591 1090.000 650.548 949.560
Z2 806.631 366.225 849.817 785.000 955.355 308.879

جدول 4. م جح ت ن جواب ه وش RLTP
تکرار RL1 RL2 Z1 Z2 U(z)
1 +∞ +∞ 650.548 955.355 802.951
2 738.4384 950* 648.000 926.050 787.025
* با نظر تصمیم گیرنده در نظر گرفته شده است.
جدول 5. نتیجة ح صل از وش محدود اپسیلون
روش Z1 Z2 U(z)
ε-constraint 209.050 194.343 201.6965

جدول 6. نت ج حل مدل ب وش RLTP و محدود اپسیلون
روش Z1 Z2 U(z)
RLTP 648.000 926.050 787.025
ε-constraint 646.000 950.000 798
جدول 7. نت ج حل مدل به وسیلة دو وش RLTP و محدود اپسیلون ب استف ده از ب دا ه ت کیب وزنظ متف وت
وزن ها U(z) RLTP ε-constraint Min U(z)
0.1 0.9 898.245 919.6 898.245
0.35 0.65 828.7325 843.6 828.7325
0.45 0.55 800.9275 813.2 800.9275
0.5 0.5 787.025 798 787.025
0.55 0.45 773.1225 782.8 773.1225
0.65 0.35 745.3175 752.4 745.3175
0.9 0.1 675.805 676.4 675.805

پم از دو بار تکرار، رضایت تصمیم گیرنده با جـوابارائه شده در تکرار دوم فراهم می شود. جـدوب 4 جـواب مرجح روش RLTP در دو تکرار انجـام شـده وRL هـای درنظرگرفته شده را نشان می دهد.
وش محدود اپسیلون
برای حل مسسله با استفاده از این روش، تابع هـدا اوببرای بهینه سازی انتخاب شد. تابع هدا دوم، بر اسـاسآنچه در پی می آید، به محدودیت تبدیل می شود و حـدبالایی آن )2ε( برابر 059=2RL قرار داده می شود:
950 = 2f2(x) ≤ ε2 ε2 = RLجدوب 5 نتیجة حاصل از حل مدب را با اسـتفاده ازروش محدودیت اپسیلون نشان می دهد.
تحلیل حس سی
برای مقایسة کیفیت جواب های نهایی به دسـت آمـده بـاروش RLTP و محدودیت اپسـیلون یـک تـابع جمعـی(U(z با وزن هـای 5/0 و 5/0 بـه کـار مـی رود. نتـایج درجدوب 6 می آید. بر اساس جـدوب 6، جـواب حاصـل ازروش RLTP مقدار تابع تجمعی کمتـری دارد و جـواب ی با کیفیت بیشتر نسـبت بـه روش محـدودیت اپسـیلونارائه می دهد. برای نتیجـه گیـری کلـی دربـارة کیفیـتج واب ارائ هش ده ب ا ای ن دو روش ،ج دوب 7 کیفی ت ج واب ه ا را ب ه وس یلة هف ت ترکی ب وزن ی مختل ف به کاررفته در تابع جمعی نشان مـی دهـد. بـق نتـایجدرا شده در جدوب 7، RLTP بهتـر از روش محـدودیتاپس یلون در مس سلة زم ان بن دی ای ن پ ژوهش عم ل می کند.
نتیجه ای
در ای ن پ ژوهش، م دب دوهدف ة جدی د ب رای مس سلة زمــان بنــدی کارهــا در سیســتم جریــان کارگــاهی جای گشتی با فرض وجـود عملیـات نـت پیشـگیرانه درحالت بدون ایست ارائه شد .عملیات نـت دارای پنجـرة زمانی است؛ وری که فاصلة بین دو عمل نـت متـوالینباید از یک مقدار مشخص بیشتر باشد .در این پژوهش سعی شد به مدب سازی ریاضی مسـ سله پرداختـه شـود.
اس تفاده از ای ن م دب ب رای ح ل مس ائل کوو ک وزمان بندی کارها در یـک خـو تولیـد کووـک مناسـباست .نتـایج حاصـل از حـل مـدب بـه وسـیلة دو روش RLTP و محدودیت اپسیلون و مقایسة انجام شـده روی کیفیت جواب ها برتری روش RLTP را نشان می دهد.
برای گسترش این تحقیق می توان عدم دسترسی را با عدم قطعیـت فـرض کـرد و از روش هـایی کـه عـدمقطیعت را در نظر می گیرنـد اسـتفاده کـرد؛ روش هـاییهمچون فازی، احتمالی، یا استوار48.
نشریهم اجع
Pinedo, M. (2008). Scheduling: Theory, Algorithms, and Systems. 3rd. Ed. Springer, New York.
Ma, Y., Chu, C., and Zuo, C. (2010). “A survey of scheduling with deterministic machine availability constraints.” Computers & Industrial Engineering, Vol 58, No. 2, 199–211.
Lee, C.- Y. (1997). “Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint.” Operations Research Letters, Vol. 20, No. 3, 129–139.
Allaoui, H., Artiba, A., Elmaghrabyb, S. E., and Rianea, F. (2006). “Scheduling of a two-machine flowshop with availability constraints on the first machine.” International Journal of Production Economics, Vol. 99, No. (1–2), 16–27.
Breit, J. (2004). “An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint.” Information Processing Letters, Vol. 90, No. 6, 273–278.
Ng, C. T. and Kovalyov, M. Y. (2004). “An FPTAS for scheduling a two-machine flowshop with one unavailability interval.” Naval Research Logistics (NRL), Vol. 51, No. 3, 307–315.
Wang, X. and Edwin Cheng, T. C. (2007). “Heuristics for two-machine flowshop scheduling with setup times and an availability constraint.” Computers & Operations Research, Vol. 34, No. 1, 152–162.
Lee, C.- Y. (1999). “Two-machine flowshop scheduling with availability constraints.” European Journal of Operational Research, Vol. 114, No. 2, 420–429.
Cheng, T. C. E. and Liu, Z. (2003). “Approximability of two-machine no-wait flowshop scheduling with availability constraints.” Operations Research Letters, Vol. 31, No. 4, 319–322.
Allaoui, H. and Artiba, A. (2014). “Hybrid Flow Shop Scheduling with Availability Constraints.” International Series in Operations Research & Management Science, Vol. 200, 277–299.
Espinouse, M. L., Formanowicz, P., and Penz, B. (1999). “Minimizing the makespan in the two-machine no-wait flow-shop with limited machine availability.” Computers & Industrial Engineering, Vol. 37, No. (1–2), 497–500.
Espinouse, M. L., Formanowicz, P., and Penz, B. (2001). “Complexity Results and Approximation Algorithms for the Two Machine No-Wait Flow-Shop with Limited Machine Availability.” The Journal of the Operational Research Society, Vol. 52, No. 1, 116–121.
Wang, G. and Cheng, T. C. E. (2001). “Heuristics for two-machine no-wait flowshop scheduling with an availability constraint.” Information Processing Letters, Vol. 80, No. 6, 305–309.
Kubzin, M. A. and Strusevich, V. A. (2004). “Two-machine flow shop no-wait scheduling with a nonavailability interval.” Naval Research Logistics (NRL), Vol. 51, No. 4, 613–.136
Aggoune, R. (2004). “Minimizing the makespan for the flow shop scheduling problem with availability constraints.” European Journal of Operational Research, Vol. 153, No. 3, 534–.345
Aggoune, R. and Portmann, M. -C. (2006). “Flow shop scheduling problem with limited machine availability: A heuristic approach.” International Journal of Production Economics, Vol. 99, No. (1–)2, 4–.51
Minella, G., Ruiz, R., and Ciavotta, M. (2008). “A review and evaluation of multiobjective algorithms for the flowshop scheduling problem.” INFORMS Journal on Computing, Vol. 20, No. 3, 451–.174
Mokhtaria, H., Nakhai Kamal Abadia, I., and Cheraghalikhanib, A. (2011). “A multi-objective flow shop scheduling with resource-dependent processing times: trade-off between makespan and cost of resources.” International Journal of Production Research, Vol. 49, No. 19, 5851–.5785
Frosolinia, M., Bragliaa, M., and Zammoria, F. A. (2011). “A modified harmony search algorithm for the multi-objective flowshop scheduling problem with due dates.” International Journal of Production Research, Vol. 49, No. 20, 5957–.5895
Khalili, M. and Tavakkoli-Moghaddam, R. (2012). “A multi-objective electromagnetism algorithm for a bi-objective flowshop scheduling problem.” Journal of Manufacturing Systems, Vol. 31, No. 2, 232–239.
Reeves, G. R. and MacLeod, K. R. (1999). “Some experiments in Tchebycheff-based approaches for interactive multiple objective decision making.” Computers and Operations Research, Vol. 26, No. 13, 1311–1321.
Steuer, R. E. (1986). Multiple criteria optimization: theory, computation, and application. Wiley, New York.
Haimes, Y. Y., Wismer, D. A., and Lasdon, D. S. (1971). “On bicriterion formulation of the integrated systems identification and system optimization.” IEEE Transactions on Systems, Man and Cybernetics, Vol. SMC-1, No. 3, 296–97. واژه ه انگلیسظ به ت تیب استف ده د متن
Single Machine
Flow Shop
Job Shop
Open Shop
Release Date
Setup Time 7- Preemption
Precedence
Availability
Failure
Preventive Maintenance
Hole
Scenario
Reusable (r)
Non-reusable (nr)
Semi Reusable 17- Makespan (Cmax)
Maximum Lateness (Lmax)
Total Completion Time
Total Weighted Completion Time
Total Tardiness
Total Weighted Tardiness
Total Earliness and Tardiness
Johnson’s Rule
Non-deterministic Polynomial-time Hard
Dynamic Programming
Heuristic
Johnson Algorithm
Worst Case Ratio Error
Gilmor & Gamry Algorithm
Polynomial Time Approximation Solution
Time Window
Meta-heuristic
نشریه
Genetic Algorithm
Tabu Search
Geometric Method
Harmony Search
Electromagnetic Algorithm
Pareto Front
Interactive Method
Reservation Level Tchebycheff Procedure
Non-dominated Solution
ε-constraint
Reservation Level
Iteration
Maximally Dispersed Solutions
General Algebraic Modeling System
Robust



قیمت: تومان


دیدگاهتان را بنویسید