زمانبندی کارها در محیط کارگاه گردش کاری با معیار حداقل سازی مجموع دیرکرد و زودکرد کارها

در این مقاله مسئلهٔ زمانبندی nكارمستقل بر روی m ماشین در محیط كارگاه گردش كاری جایگشتی۱ با زمانهای پردازش و موعد تحویل دلخواه بررسی و یك مدل با هدف كمینه كردن مجموع دیركردها و زودكردها ( ) با استفاده از تكنیك الگوریتمهای ژنتیك ارائه میشود. این مسئله از نوع مسایل ایستاست و بجز محدودیت ماشین آلات (به عنوان منابع) محدودیت دیگری برآن حاكم نیست. همچنین مسئلهٔ موردنظر از لحاظ اطلاعات در دسترس معین است. مدل ارائه شده به لحاظ بهینگی جواب نهایی و زمان حل مسئلهٔ ارزیابی و جوابهای آن با یكی از مدلهای موجود مقایسه میشود.
● مقدمه :
از زمان چاپ اولین مقالهٔ جانسون دربارهٔ مسئلهٔ توالی عـملیات كـارگاه گـردش كاری درسال ۱۹۵۴، این مسئله مورد توجه بسیاری از پژوهشگران قرار گرفت. در مسئلهٔ كارگاه گردش كاری ، m ماشین و n كار وجـود دارد. هـركار نیازمند m عملیات است و برای هر عـملیات یك ماشین متفاوت لازم است.n كار با توالی یكسان روی m ماشین انجام میشوند. زمان فرآیند كارi روی ماشین j به صورت tij.,…,m) ۲,۱j= و ,...,n۲,۱i=) بیان میشود.
هدف یافتن بهترین ترتیب انجام و تكمیل كارهاست. بهینگی توالی عملیات با در نظر گرفتن یك معیار كارایی مثلاً زمان تكمیل كل كارها، مـجموع دیـركـردها یـا مــجموع دیـركــردها و زودكردها مشخص میشود. تنها تفاوت كارگاه گردش كاری ترتیبی با كارگاه گردش كاری در حالت عمومی این است كه در حالت اول كارها در مراحل مختلف فرآیند (ماشینها)از یكدیگر سبقت نمیگـیرند. بـه عـبارت دیـگر تـرتیب كـارها روی ماشین اول ، تعیین كنندهٔ ترتیب كارها روی تمام ماشینهاست. در حالت عمومی ، كارها ممكن است در مراحل مختلف فرآیند از یكدیگر سبقت بگیرند. در عمل ، اكثر مسائل كارگاه گردش كاری از نوع ترتیبی است و سبقت كارها از یكدیگر به ندرت اتفاق میافتد.
▪ فرضهای اصلی مسئله عبارت اند از
۱) هـركار بـاید به ترتیب به وسیلهٔ تمام ماشینها پردازش شود.
۲) در هر زمان هر ماشین تنها یك كار را پردازش میكند.
۳) در یك زمان هر كار تنها به وسیلهٔ یك ماشین پردازش میشود.
۴) كارها به طور پیوسته انجام میشوند و بریدگی مجاز نیست.
۵) زمانهای آماده سازی كارها مستقل از توالی آنهاست و به عنوان بخشی از زمان پردازش در نظر گرفته میشود
۶) توالی عملیات كارها روی تمام ماشینها یكسان است و باید توالی عمومی تعیین شود. در اكثر صنایع تولیدی بزرگ، مانند خودروـ سازی و صنایع مونتاژ ، عملیات پردازش قطعات و تكمیل كارها به صورت خطی و مرحلهای صورت مـیگیرد. از ایـن رو مـسایل زمـانبندی كـارگاه گردشكاری، طیف گستردهای از مدلهای تولیدی و مونتاژ را در برمیگیرد. از طرف دیگر این مسئله بـا مـعیار حـداقل كـردن مـجموع دیــركردها و زودكـردها ( ) یـك مـعیار تـولیدكننده ـ مشتری پسند و در جهت اهداف سیستمهای تولید درست به موقع است و كمتر مورد توجه محققان بوده است. اغلب مسایل توالی عملیات NP-Hard هستند.
از اینرو، الگوریتمهای جستجوی دقیق وبهینهیاب برای حل اینگونه مسایل مستلزم زمان محاسباتی زیادی است. بویژه این زمان با بزرگ شدن ابعاد مسئله به صورت نمایی افزایش مییابد و در برخی موارد نیز یافتن جواب بهینه عملاٌ امكانپذیر نیست. به همین خاطر الگوریتم‌های ابتكاری كه در پی به دست آوردن جواب خوب در زمان كوتاه هستند، در حل این مسائل كاربرد بسیاری پیدا كرده اند. در این مقاله یك الگوریتم ژنتیك برای مسئلهٔ موردنظر ارایه شده است. در ادامه مروری بر پیشینهٔ موضوع صورت گرفته و بعد ازآن به تشریح الگوریتم‌های ژنتیك پرداخته است. سپس به تعیین پارامترهای الگوریتم ژنتیك برای مسئلهٔ موردبحث و تشریح مدل پرداخته و مدل ارائه شده ارزیابی میشود. در پایان بحث و نتیجه گیری آمده است.
● مروری بر پیشینهٔ‌ موضوع
جانسون مسئلهٔ n قطعه و دو ماشین سری را با فرضیات مدل پایه موردبررسی قرارداد و جواب بهینهٔ مسئله یعنی كمینه كردن دامنهٔعملیات (Cmax) را ارائه كرد. وی همچنین نشان داد كه در جواب بهینه ترتیب عملیات دو ماشین یكسان است. بسیاری از محققان ، كار جانسون را برای تعمیم به ماشینهای بیشتر و پیداكردن الگوریتم‌های بهینه ادامه دادند ولی جز در حالات خاص‌موفقیت چندانی برای حل مسئله در حالت كلی به دست نیاوردند. دودك و همكاران نشان دادند كه مسئله با تابع هدف كمینه كردن Cmax از مسائل Np-Hard است . از این رو، روشهای ابتكاری سریعاٌ رشد یافتند.
این مسئله به صورت n/m/p/ Cmax نمایش داده میشود. دودك و تیوتون ، ایگنال و شارج ، اسمیت ودودك ، آشور به ارایهٔ روش حل BB و قواعد حذف میپردازند. در این مقالات جواب بهینه برای مسائل با اندازههای كوچك به دست آمده است و عملاٌ برای مسائل بزرگ كارایی ندارند. پالمر ،كمبل و همكاران ، داننبرینگ ، و كینگ و اسپچیس به روشهای ابتكاری پرداخته‌اند. داننبرینگ و همچنین ذگردی و همكاران روشهای ابتكاری را به دو دستهٔ روشهای ساختنی و روشهای بهبود دادنی تقسیم كردهاند. روشهای ابتكاری جالبی توسط ناواز و همكاران برای حل مسئلهٔ n/m/p/ Cmax ارایه شده است.
مبنای این روش بر اساس داشتن اولویت بالاتر برای قطعه با كل زمان پردازش بیشتر است. این روش به روش NEH مشهور است. ناواز و همكاران نشان دادهاند كه الگوریتم NEH در اكثر موارد كارایی بهتری نسبت به الگوریتم CDS دارد. عثمان و پاتس و ریوز معتقدند كه كارایی روش NEH در بین سایر روشهای سنتی از همه بیشتر است. اشكال اساسی تمام روشهای بهبوددهنده با هر نوع تابع هدف، توقف در نقاط كمینهٔ محلی است. برای رفع این مشكل ، روشهای جدیدی از جمله بازپخت شبیه سازی شده۱ (SA)، الگوریتم ژنتیكی (GA) و پژوهش تابو۲ (TS) مطرح شدهاند. در مقالهٔ س كروس و همكاران گفته میشود كه GA یك تكنیك بهینه سازی برای توابع تعریف شده روی دامنهٔ محدود است. كلیهٔ روشهای TSوGA, SA پارامتری هستند و باید برای هر مسئله مشخص شوند. بزرگترین اشكال این روشها، طولانی بودن زمان حل مسائل نسبت به روشهای ابتكاری سنتی است.
روش GA توسط ریورز برای حل مسائلn/m/p/ Cmax به كار برده شده است. در GA ی ارائه شده یكی از اعضای جمعیت اولیه، جواب الگوریتمNEH است. این روش با SA ی مربوط به اگبو و اسمیت مقایسه و برتری آن نشان داده شده است.كمینه كردن مجموع وزنی انحراف از موعد تحویل با وزن‌های مشابه برای زودكرد و دیركرد، یك تابع غیرمنظم است و توسط دی و همكاران حالتی با موعد تحویل قطعات یكسان مورد بررسی قرار گرفته و جواب بهینه همراه با مشخص كردن موعد تحویل با استفاده ازروشDP ارائه شده است. تابع هدف فوق با وزن‌های متفاوت زودكرد و دیركرد و محاسبهٔ‌موعد تحویل یـكسان بـرای تـمام قطعات، توسط دیلیپان مورد توجه قرار گرفته و ضمن اثبات قضایایی از روش شاخه و كران برای پیدا كردن جواب بهینه و ارائهٔ روشی ابتكاری استفاده شده است. این روش توانایی حل مسئلههای با حداكثر ۱۵ قطعه را دارد.در بررسیهای انجام شده برای حالت كلی مسئلهٔ كارگاه گردش كاری۱ با معیار مجموع زودكرد و دیركردها (مسئلهٔ ) مقاله ای یافت نشد.

نویسنده:
سید محمدحسن حسینی، فریبرز جولای

منبع : فصلنامه مدیرساز