بخشی از مقاله
1 مقدمه1
امروزه با توجه به رقابتی شدن شرایط بازارها، سازمانها برای حفظ و بقا باید به دنبال افزایش کارایی و بهینهسازی عملیات تولیدی خود باشند. به همین دلیل باید عوامل متفاوتی را در راستای بهینهسازی برنامه زمانبندی خود و برای پاسخگویی بهنگام به تقاضاهای مشتریان مد نظر قرار دهند. این شرایط شرکتها را به حرکت از فرآیندهای برنامهریزی مجزا به سمت برنامهریزی یکپارچه ترغیب
.1 نویسنده مسئول.
تلفن: 0351-8122405، پست الکترونیکی: Mfakhrzad@yazd.ac.ir
میکند. با استفاده از سیستمهای برنامهریزی یکپارچه، آنها میتوانند نسبت به تغییرات به سرعت پاسخ دهند و محصولاتی با کیفیت بالاتر و هزینههای تولید کمتر ارائه کنند .[1-3] با شکلگیری مفهوم یکپارچهسازی، سیستمهای ساخت یکپارچه شکل گرفتند تا به شرکتها در داشتن سطح خدمتدهی عالی برای غلبه بر رقبا در بازار پرتلاطم امروزی کمک کنند. برنامهریزی و زمانبندی پیشرفته 2(APS) شامل یک سری از تکنیکهای زمانبندی در حالت ظرفیت محدود ( از سطح کارگاه تا سطوح بالای سیستمهای یکپارچه ساخت) و یک گام تکاملی جدید در راستای یکپارچهسازی
2 . Advanced Planning and Scheduling (APS)
برنامهریزی و زمانبندی پیشرفته با در نظر گرفتن اثر یادگیری در سیستمهای ساخت کارگاهی انعطافپذیر 14
مدلهای برنامهریزی است APS .[4] بیشتر در سازمانهایی قابل بهکارگیری است که یک یا چند مورد از حالات زیر اتفاق بیفتد: (1) تولید برای سفارش انجام شود نه برای انبارش، (2) محصولات نیازمند تعداد زیادی قطعه یا عملیات باشند، (3) تولید با محدودیت سرمایه و منابع مواجه باشد، (4) محصولات برای استفاده از منابع با هم در رقابت باشند (محیط چند محصولی)، (5) شرایط ناپایدار باشد به گونهای که امکان زمانبندی منابع وجود نداشته باشد و (6) استفاده از یک رویکرد تولید انعطافپذیر اجتناب ناپذیر باشد. تا کنون در تمامی مقالات مربوط به حیطه APS و تولید کارگاهی یک فرض رایج این بوده که زمان پردازش کارها ثابت و مستقل از توالی است. در حالی که در بسیاری از موارد عملی با تکرار کارهای مشابه (و یا متفاوت)، توانایی و مهارت اپراتور افزایش و در نتیجه آن، زمان پردازش کارها کاهش مییابد. این امر باعث بهبود مستمر عملکرد تسهیلات تولیدی مخصوصاً نیروی انسانی میشود و در ادبیات موضوع با نام اثر یادگیری شناخته میشود. بنابراین در این مقاله، برای اولین بار یک مدل برنامهریزی و زمانبندی پیشرفته به گونهای توسعه داده شده است که بتواند مفهوم اثر یادگیری را لحاظ کند. این
مدل نه تنها برای اعمال اثر یادگیری در مدلهای زمانبندی کارگاهی انعطافپذیر، بلکه برای مدلهای موازی و خطوط مونتاژ که در آنها زمان پردازش عملیات (بنا به هر دلیلی) تغییر میکند نیز قابل استفاده است. با توجه به پیچیدگی محاسباتی بالای مسأله، برای حل مدل پیشنهادی نیز یک الگوریتم ژنتیک چند مرحلهای پیشنهاد شده است.
در ادامه مقاله، در بخش دوم به مروری اجمالی بر ادبیات APS و اثر یادگیری پرداخته شده است. سپس در بخش سوم یک مدل ریاضی کاربردی برای مسأله APS با در نظر گرفتن اثر یادگیری ارائه و برای حل آن در بخش چهارم یک الگوریتم ژنتیک چند مرحلهای توسعه داده شده است. بخش پنجم به نتایج محاسباتی اختصاص یافته و در نهایت در بخش ششم نتیجهگیری و پیشنهاد کار آیندگان آورده شده است.
-2 ادبیات موضوع
به طور کلی میتوان پژوهشها در حیطه مسائل APS را به دو دسته کلی کیفی و کمی تقسیمبندی کرد. در پژوهشهای کیفی از دید مدیریتی به جنبههای تحلیلی، انتقادی و توصیفی پرداخته شده است که از موضوع این مقاله خارج است. علاقهمندان به مقالات کیفی میتوانند به عنوان نمونه به مراجع 5]،[6 مراجعه کنند. در پژوهشهای کمی،معمولاً ابتکار در ارایه مدلهای ریاضی و یا بهبود روشهای حل موجود بوده است. در حیطه پژوهشهای کمی، مسائل زمانبندی در حالت برونسپاری نظر محققان زیادی را به خود جلب کرده است. اینگونه مسائل معمولاً هنگامی کاربرد دارد که تولیدکننده بخواهد سفارشها را دقیقاً در یک موعد مقرر تحویل
دهد. لی و همکاران [7] مدلی جامع برای مسأله APS در حالت مجاز بودن برونسپاری پیشنهاد دادند و برای اولین بار مفهوم تنوع مسیرهای پردازش را در مدلهای APS لحاظ کردند. آنها برای حل مدل پیشنهادی یک روش ابتکاری کارا بر مبنای الگوریتم ژنتیک ارائه کردند. چن و جی [8] یک مدل MIP کارا با محدودیتهای ظرفیت، ترتیب عملیات، زمان انجام سفارش و موعدهای تحویل برای یکپارچهسازی مسأله برنامهریزی تولید و زمانبندی عملیات در یک محیط چند محصولی ارائه کردند. تابع هدف آنها، کمینهسازی هزینه بر مبنای دو معیار زمان بیکاری سیستم و هزینههای زودکرد-دیرکرد سفارشها بود. یکی از نکات مهم در مقالاتی که از الگوریتم ژنتیک استفاده کردهاند نحوه مناسب رمزگذاری و رمزگشایی جوابهاست. یانگ و تانگ [9] یک الگوریتم ژنتیک تطبیقی1 برای حل مسأله APS در حالت چند هدفه ارائه و برای نشان دادن کارایی و سرعت الگوریتم پیشنهادی خود از مثالهای عددی موجود در مقاله ژانگ و گن [10] استفاده کردند.
به طور معمول، ماشینها توانایی تولید چند نوع قطعه را دارند اما این نکته در مدلسازی مسائل APS لحاظ نشده است. به همین دلیل، ارسلان اورنک و همکاران [11] مدل چن و جی [8] را با استفاده از مفهوم گراف انفصالی2 توسعه دادند و برای قطعات قابلیت پردازش روی ماشینهای متفاوت در نظر گرفتند. از جمله معایب عمده این پژوهش این است که هیچ گونه روش حل و یا مثال عددی برای درک بهتر مدلسازی ارائه نشده است. چن و همکاران [12] یک مطالعه موردی برای مسأله APS در کارخانجات ساخت وسائل روشنایی در چین با استفاده از مدل چن و جی [8] انجام و برای حل آن یک روش هوشمند ابتکاری بر مبنای مفهوم الگوریتم ژنتیک و کلیدهای تصادفی3 ارائه دادند. در تمامی مقالات موجود در ادبیات موضوع، فرض شده که زمان پردازش کارها ثابت و مستقل از توالی بوده و با گذشت زمان تغییر نمیکند. در حالی که در چند سال اخیر مطالعات پژوهشگران در مورد پدیده هایی مانند اثر یادگیری، اثر خستگی و زمانهای پردازش متغیر و قابل کنترل، صحت این فرض را مورد تردید قرار داده است. به همین دلیل در این مقاله، مدل موجود در [ 11] به گونهای توسعه داده شده است که بتوان فرض متغیر بودن زمانهای پردازش (به عنوان مثال اثر یادگیری) را در مدلسازی لحاظ و آن را به شرایط دنیای واقعی محیطهای تولیدی نزدیکتر کرد. در قسمت بعدی تاریخچه مختصری از مبحث اثر یادگیری بیان شده است تا لزوم اعمال این اثر در مدلهای زمانبندی مشخص شود.
1. Adaptive Genetic Algorithm 2. Disjunctive graph 3. Random keys
51 نشریه پژوهشهای مهندسی صنایع در سیستمهای تولید / سال اول / شماره اول / بهار و تابستان 1392
-1-2 اثر یادگیری و تاریخچه آن
یک فرض رایج در مسائل زمانبندی کلاسیک این است که زمان تولید یک محصول (پردازش کار) ثابت و مستقل از جایگاهش در توالی تولید است. برای مثال، بیکر فرض میکند زمانهای پردازش ثابت، مشخص و مستقل از توالی کارهاست .[13] از آن جا که مسائل کلاسیک زمانبندی برای محیطهای چندماشینه محدود و ناکارا هستند، با تکامل اینگونه مسائل از اوائل دهه 1990 مدلهای نوینی در مسائل زمانبندی به وجود آمد؛ از جمله مسأله زمان بندی با زمانهای پردازش قابل کنترل، زمانبندی کارها با زمانهای پردازش وابسته به زمان و زمانبندی کارها روی ماشینهای چندمنظوره .[14] بسیاری از محققین با بررسی برنامه زمانبندی تجربی و تئوری به این نتیجه رسیدهاند که زمانهای پردازش کارها تراکمپذیرند .[15] یکی از رویکردها برای کاهش زمان پردازش کارها و در نظر گرفتن تراکمپذیری، استفاده از مبحث یادگیری است .[16] در بیشتر مواقع با تکرار یک کار، توانایی و مهارت کارگر افزایش و زمان پردازش کارها کاهش مییابد. این امر باعث بهبود مستمر عملکرد تسهیلات تولیدی (مخصوصاً نیروی انسانی) میشود و در ادبیات
موضوع با نام اثر یادگیری شناخته میشود.
رایت [17] اولین کسی بود که به تحقیق در مورد مفهوم اثر یادگیری در چارچوب یک کار علمی پرداخت. او با استفاده از آزمایش ها علمی در صنایع هواپیمایی، فرضیه مشهور %80 را مطرح کرد که »با دو برابر شدن خروجی تولید، زمان پردازش هر واحد %20 کاهش مییابد.« با توجه به محسوس بودن نقش نیروی انسانی در محیطهای زمان بندی، تعداد عملیاتی که در آن احتمال وقوع یادگیری وجود داشته باشد زیاد است؛ بنابراین در نظر گرفتن یادگیری در محیطهای زمانبندی معقول به نظر میرسد. اولین بار بیسکاپ [18] مفهوم اثر یادگیری را در مسایل زمانبندی بکار برد. این مفهوم پس از آن مورد توجه بسیاری از پژوهشگران قرار گرفت و امروزه پژوهشهای متعددی در این زمینه به چاپ رسیده است. برای اعمال اثر یادگیری در مدلهای زمانبندی دو رویکرد عمده و متفاوت وجود دارد که هر یک اعتبار خاص خود را دارند.
-1رویکرد موقعیتگرا1 که در آن، یادگیری تحت تأثیر تعداد کارهایی است که تاکنون پردازش شدهاند.معمولاً این رویکرد در مواردی استفاده میشود که پردازش واقعی کارها عمدتاً ماشینمحور بوده و با مداخله کمتر انسان انجام میشود.
-2رویکرد مجموع زمان پردازش2 که در آن، یادگیری تحت تأثیر مجموع زمان کارهایی است که تاکنون پردازش شدهاند. به عنوان مثالهای عملی از این رویکرد میتوان فرآیندهایی را نام برد که انجام آنها بسیار پیچیده و خطا ساز است. توصیه پژوهشگران بر آن است
1. Position-Based Learning 2. The Sum of Processing Time
که اگر تراکنشهای انسانی اثر قابل ملاحظهای در طی پردازش کارها داشته باشد، بهتر است که اثر یادگیری به صورت وابسته به زمان در نظر گرفته شود .[19]
در طی چند سال اخیر، اثر یادگیری به دلیل اهمیت آن در مباحث نوین مدیریتی، صنایع و بخشهای تجاری، توجه خاصی را در مسائل زمانبندی به خود جلب کرده است [20] که رشد نمایی حجم مقالات ارایهشده در این حیطه گواه این ادعاست.
دژونگ با استفاده از نتایج مطالعات زمانسنجی، یک مدل یادگیری جدید و کاربردی برای تقریب میزان کاهش زمان پردازش کارها در تکرارهای آتی ارایه داد (رابطه (( 1) که در مراجع به این فرمول اشاره مستقیم شده است 14]،.[15
(1) p j ,r p j ( M (1 M )r ) j 1, r n ×
که در آن، p j زمان پردازش نرمال کار، 0 شاخص یادگیری،
M فاکتور تراکمناپذیری8 و r موقعیت (جایگاه) کنونی کار (قطعه) در
برنامه زمانبندی است. دژونگ برای کارهای اپراتور-محور
0.25 M و برای کارهای ماشین-محور M 0.5 را پیشنهاد
کرد. اوکولوفسکی و گاویجنویچ [14] بر مبنای رابطه 1) )، مدلی برای زمانبندی ماشینهای موازی با هدف کمینهسازی دامنه عملیات ارائه و ادعا کردند که اولین کسانی هستند که مدل دژونگ را به عنوان اثر یادگیری در حیطه مسائل زمانبندی وارد کرده اند. هرچند که به نظر میرسد قبل از آنها، بهلولی و ذگردی [15] این رابطه را در نظر گرفته بودند. در ادامه به برخی از مهمترین و جدیدترین پژوهشها در زمینه اثر یادگیری اشاره میشود:
جی وانگ و جیان وانگ [21] هر دو رویکرد یادگیری موقعیتگرا و مجموع زمان پردازش را در نظر گرفته و یک مدل یادگیری ترکیبی ارایه کردند. ژانگ و همکاران [22] بر مدلهای مجموع لگاریتمی زمانهای پردازش و پردازش موقعیتگرا تمرکز و رابطهای برای مجموع لگاریتم زمانهای پردازش ارائه کردند. امینی و همکاران [ 23] یک مدل ریاضی برای مسأله ماشین های موازی یکسان در حالت وجود اثر یادگیری در زمانهای آماده سازی و اثر خستگی در تخلیه ارائه و جوابهای مدل قطعی خود را با روشهای ابتکاری مقایسه کردند. همتا و همکاران [24] یک مدل بهینهسازی چند هدفه را برای مدل بالانس خط مونتاژ در حالت نامشخص بودن زمان پردازش کارها ارائه و با ترکیب دو تکنیک موزون و ماکسیمین، یک روش حل برای مدل خود ارائه کردند. در ادامه همین پژوهش، همتا و همکاران [25] برای حل مسأله در ابعاد بزرگ، یک الگوریتم بهینهسازی انبوه ذرات با جستجوی متغیر همسایگی پیشنهاد دادند. بهنامیان و فاطمی قمی [26] مسأله فلوشاپ ترکیبی چند هدفه را در حالت زمان پردازش وابسته به زمان مورد بررسی قرار دادند و یک روش نمایش جواب و الگوریتم فراابتکاری استوار جدید پیشنهاد دادند.
Min Z C max ×
1, 2,...,b
1, 2,..., n
برنامهریزی و زمانبندی پیشرفته با در نظر گرفتن اثر یادگیری در سیستمهای ساخت کارگاهی انعطافپذیر 16
-3 ارایه مدل ریاضی و بررسی پیچیدگی آن
معمولاً مدلهای موجود در ادبیات موضوع برنامهریزی و زمان بندی پیشرفته یکسان و یا دارای مفهوم مشابهی هستند. با این حال مقاله اورنک و همکاران [11]، یکی از جدیدترین و کاملترین مدلهای ارایهشده در حیطه APS است که قابلیت مدلسازی محیطهای کارگاهی انعطافپذیر را داراست. اما یکی از معایب این پژوهش آن است که زمانهای پردازش کارها ثابت و مستقل از توالی فرض شده است. به همین دلیل این مدل به گونه ای توسعه داده شده است که با حذف فرض ثابت بودن زمان پردازش کارها، بتوان اثر یادگیری را در مدلهای APS لحاظ کرد. قابل ذکر است که با توجه به پیش نیازهای استفاده از مدلهای یادگیری، در این پژوهش بخش قابل توجهی از ساختار مدلسازی و نحوه تعریف متغیرهای تصمیم نسبت به مقاله مبنا تغییر کرده است.
یک محیط تولیدی چند محصولی را در نظر بگیرید که با استفاده از یک سری ماشین آلات اقدام به تولید سفارشهای مشتریان میکند. هر محصول ساختار درختی داشته و از یک سری قطعه و زیر مونتاژ تشکیل شده و برای تولید هر قطعه، ماشینهای متناوبی در اختیار است. ماشینها میتوانند در زمانی غیر از صفر نیز در دسترس باشند اما همه سفارشها در زمان صفر در دسترس هستند. هدف مدل، ارایه یک برنامه زمانبندی برای تولید قطعات تمامی سفارشهاست به گونهای که دامنه عملیات کمینه شود. در این برنامه زمان بندی دقیقاً مشخص میشود که کدام قطعه از کدام محصول، باید چه موقع و توسط چه ماشینی تولید شود. در اینجا به توضیح
ساختار مدل پرداخته میشود:
اندیسها و مجموعهها:
: j , i اندیس محصولات (سفارشهای مشتری) i , j
:n تعداد کل محصولات مورد برنامهریزی (کل سفارشات مشتریان) : A Pi مجموعه قطعات متفاوت مورد نیاز برای تولید محصول i : N A Pi تعداد قطعات متفاوت مورد نیاز برای تولید محصول i : b کل قطعات مورد نیاز برای برآورده کردن سفارشهای تمامی
مشتریان که از رابطه (2) بدست میآید.
(2) n
N (A ( Pi )) × b
: q , p اندیس قطعات p ,q 1, 2, ..., b 1 i
: N ip تعداد قطعه مورد نیاز p برای تولید یک واحد محصول i
: l , k اندیس ماشینآلات 1, 2,..., m k , l
: m تعداد کل ماشینها
: r اندیس موقعیت (جایگاه) انجام کار که حداکثر برابر با کل
قطعاتی است که باید تولید شوند یعنی r
پارامترها:
: wh ساعات کار روزانه
: pi قطعه نهایی محصول i یعنی بالاترین قطعه در درخت محصول :Qi تعداد سفارش محصول i
: t ipk مدت زمان نرمال تولید قطعه p از سفارش محصول i روی ماشین k در حالت نرمال (بدون در نظر گرفتن موقعیت انجام کار) : M ipk عامل تراکمناپذیری: (درصدی از زمان پردازش قطعه p از سفارش i روی ماشین k که بدون دخالت انسان انجام میشود.)
