بخشی از مقاله
چکیده:
در این تحقیق، مسئله زمانبندي در محیط جریان کارگاهی انعطافپذیر با در نظر گرفتن ماشینهاي موازي غیر مشابه بررسی میشود بهگونهاي که در هر حداقل یک مرحله دو یا چند ماشین موازي غیرمشابه میباشد. تابع هدف در نظر گرفته شده در این تحقیق کمینهسازي بیشینه زمان تکمیل کارها میباشد. با توجه به NP-hard بودن مسأله، از روش تجریه بندرز براي حل این مسأله استفاده شده است. براي ارزیابی کارایی روش پیشنهادي، 17 مسأله آزمایشی در ابعاد گوناگون تولید شده است. نتایج نشان میدهد که الگوریتم تجزیه بندرز در ابعاد کوچک سبب بهبود زمان حل نمیشود ولی با افزایش ابعاد مسأله، این روش مسائل را در مدت زمان کمتري نسبت به مدل ریاضی حل میکند.
کلمات کلیدي: محیط جریان کارگاهی انعطافپذیر؛ ماشین موازي غیرمشابه؛ الگوریتم تجزیه بندرز، حداکثر زمان تکمیل کارها.
.1 مقدمه
در دنیاي صنعتی امروز با توجه به کاهش منابع تولیدي از جمله ماشینها و تجهیزات تولیدي، انرژيهاي مورد نیاز تولید، افزایش هزینههاي بهکارگیري و راهاندازي تجهیزات و بیکاري ماشین آلات، ارزش بهینهسازي و میزان بهرهبرداري از منابع و زمان در سیستمهاي تولیدي روزبهروز بیشتر میشود. یکی از مطرحترین موضوعات در بهینهسازي استفاده از منابع که توجه محققان و پژوهشگران زیادي را به جلب است، مقوله زمانبندي میباشد. ایجاد یک برنامهریزي اثربخش و کارآمد جهت تعیین توالی تولید، ارتباط اساسی با افزایش راندمان سیستمهاي تولیدي دارد. همچنین در زمینه تحقیق در عملیات، زمانبندي به عنوان یک زمینه فعال تحقیق در نظر گرفته شده است، بهگونهاي که توالی عملیات و زمانبندي در واقع نوعی فرایند تصمیمگیري است که داراي نقشی اساسی در ارتقاي بهره وري درصنایع تولیدي و خدماتی است. زمانبندي در واقع به معناي تعیین زمان آغاز و پایان عملیات به روي منابع است و هدف عمده آن ایجاد تعادل میان اهداف مغایر، به کارگیري مؤثر کارگران، تجهیزات، و تسهیلات، همزمان با کاهش زمان انتظار مشتریان، موجوديها و زمان فرآیندهاست.
یکی از محیطهاي کاري بسیار پرکاربرد در دنیاي واقی محیط جریان کارگاهی انعطافپذیر 1 - FFS - میباشد. در مسائل با محیط کاري جریان کارگاهی انعطافپذیر فرض میشود c مرحله به صورت سري وجود دارد و در هر مرحله - حداقل یک مرحله - ، حداقل دو ماشین به صورت موازي وجود دارد که هر یک از کارها باید به ترتیب در هر مرحله توسط یکی از ماشینها پردازش شود و به مرحله بعدي انتقال یابد. در مسئله جریان کارگاهی انعطافپذیر با ماشینهاي غیرمشابه، مدت زمان فرآیند کارها در یک مرحله با یکدیگر متفاوت است زیرا ماشینهاي موجود در هر مرحله با یکدیگر تفاوت دارند. مهمترین علت این تفاوت ناشی از این واقعیت است که بعضی از ماشینها فقط مناسب گروه خاصی از کارها میباشند و یا بعضی از کارها بهخاطر شرایط خاصی که دارند فقط میتوانند به بعضی از ماشینهاي خاص تخصیص یابند .[1]
چینگ جانگ لیائو و همکاران [2] یک مسئله زمانبندي در محیط جریان کارگاهی انعطافپذیر را با هدف کمینهسازي زمان تکمیل در نظر گرفتند. همچنین یک روش جدید را با ترکیب الگوریتم بهینه سازي ازدحام ذرات و الگوریتم ابتکاري گلوگاه پی شنهاد کردند. نادري و همکاران[3] چهار مدل ریا ضی را براي یک م سئله زمانبندي در محیط جریان کارگاهی انعطافپذیر تو سعه دادند. آنها آزمای شاتی را براي مقای سه عملکرد مدلها بر ا ساس اندازه و پیچیدگی محا سباتی انجام دادند و علاوه بر ان یک الگوریتم بهینه سازي ازدحام ذرات نیز پیشنهاد کردند.
ا سدي گنگرج [4] یک روش ابتکاري مبتنی بر گلوگاهها براي حل م سأله زمانبندي در محیط جریان کارگاهی انعطافپذیر تو سعه دادد. او براي ارزیابی کیفیت روش، کران پایین ارائه شده توسط کورز و آسکین [5] را براي مسأله FFS با ماشینهاي موازي غیرمشابه توسعه داد.
فتاحی [6] و همکاران یک مسئله زمانبندي در محیط جریان کارگاهی انعطافپذیر با عملیات مونتاژ را با هدف کمینهکردن بیشینه زمان تکمیل در نظر گرفتند و از یک الگوریتم ابتکاري شاخه و کران براي تولید جواب استفاده کردند و براي افزایش کارایی الگوریتم تعدادي حد بالا و پایین گسترش داده شد. جولایی [7] و همکاران یک مسئله زمانبندي جریان کارگاهی انعطافپذیر را با تابع هدف کمینهکردن بیشینه زمان تکمیل و حداکثر دیرکرد در نظر گرفتند و سه رویکرد فراابتکاري بر اساس الگوریتم شبیهسازي تبرید در نظر گرفته شد. مورسلی و پوچت [8]، یک الگوریتم شاخه و کران را براي مسئله زمانبندي جریان کارگاهی ترکیبی با تابع هدف کمینهکردن بیشینه زمان تکمیل کارها ارائه دادند و چندین استراتژي جهت محدود سازي حدود بالا و پایین در نظر گرفته شد. ازمایشات عددي نشان داد که زمان اجرا در مسائل با اندازه متوسط و حتی بالا نیز کم است و همچنین الگوریتم شکاف بین حدود بالا و پایین را تا %50 کاهش داده است. تاسوشی نیشی [9]
و همکاران یک روش ازاد سازي لاگرانژ براي حل م سئله زمانبندي جریان کارگاهی براي کمینه سازي مجموع وزنی دیرکرد در نظر گرفتند. در این تحقیق یک ازادسازي لاگرانژ با تولید برش پیشنهاد شد و نتایج نشان داد که عملکرد روش پیشنهادي با استفاده از روش معمول لاگرانژ بدون افزایش زمان کل محاسبات بهتر عمل میکند. لیو و چانگ [10] ، یک رویکرد مبتنی بر ازادسازي لاگرانژ را براي مسئله زمانبندي جریان کارگاهی ترکیبی با زمان اماده سازي وابسته به توالی و هزینه و کمینه سازي زودکرد و دیرکرد را نظر گرفتند. م سئله زمانبندي دو مرحلهاي جریان کارگاهی انعطافپذیر با تابع هدف کمینهکردن بی شینه زمان تکمیل کارها توسط داریا ترخو و همکاران [11]، مورد بررسی قرار گرفت. آنها یک الگوریتم بندرز جهت حل ارائه کردند که در مسئله اصلی توالی کارها در مرحله اول و تخصیص کارها به ماشینها در مرحله دوم در زیر مسئله انجام شده است. اسدي گنگرج [12] از روش آزادسازي لاگرانژین براي حل مسأله زمانبندي در محیط جریان کارگاهی انعطافپذیر با ماشینهاي موازي غیرمشابه استفاده کردند. تابع هدف در نظر گرفته شده کمینهسازي بیشینه زمان تکمیل کارها میباشد.
با توجه به پیچیدگی بالاي م سأله زمانبندي در محیط جریان کارگاهی انعطافپذیر، حل م سائل در ابعاد متو سط و بزرگ با ا ستفاده از مدلهاي ریا ضی تو سعه یافته در مدت زمان معقول امکانپذیر نمیباشد. از این رو محققان زیادي روشهاي ابتکاري و فراابتکاري متنوعی را براي حل این مسأله توسعه دادهاند، اما این روشهاي تضمینی براي ارائه جوابهاي بهینه و حتی نزدیک به بهینه ارائه نمیکنند. از اینرو توسعه روشهاي دقیق نظیر تجزیه بندرز میتواند راهگشا باشد. در این تحقیق، براي ارائه روش تجزیه بندرز از مدل ریاضی ارائه شده توسط اسدي گنگرج [12] استفاده شده است. ادامه تحقیق بهصورت زیر سازماندهی است. در بخش دوم مدل ریاضی توسعه یافته توسط اسدي گنگرج [12] معرفی میشود و در بخش سوم، الگوریتم تجزیه بندرز توسعه یافته ارائه میشود. در بخش چهارم تحقیق، ازمایشات عددي براي نشان دادن کارایی الگوریتم بیان میشود و در نهایت در بخش پنجم نتیجهگیري این تحقیق و زمینههاي تحقیقات آتی بیان خواهد شد.
.2 مدل ریاضی
در این بخش به معرفی مدل ریاضی براي مسئله زمانبندي در محیط سري انعطاف پذیر با ماشینهاي موازي غیرمشابه پرداخته میشود. تابع هدف در نظر گرفته شده براي مسئله، کمینهسازي بیشینه زمان تکمیل کارها یا Cmax میباشد. نشانههایی که براي نمایش این مدل ریاضی استفاده شده است به شرح زیر میباشد:
: j ,l اندیس کارها : i اندیس مراحل
: k اندیس ماشینهاي هر مرحله : n تعداد کارها
: m تعداد مراحل
: si تعداد ماشینهاي در مرحله i
: Pijk مدت زمان فرآیند کار j در مرحله i بر روي ماشین k
: M عدد بسیار بزرگ
:Cij زمان تکمیل کار j در مرحله i
: X ijk اگر کار j به ماشین k در مرحله i تخصیص یابد برابر با 1 در غیر اینصورت .0 :Y ilj اگر کار l قبل از کار j در مرحله i فرآیند شود برابر با 1 در غیر اینصورت .0
:W ijl اگر کارهاي l و j در مرحله i بر روي یک ماشین فرآیند شوند برابر با 1 در غیر اینصورت .0
بنابراین با توجه به مطالب ارائه شده مدل ریاضی عدد صحیح مختلط به صورت زیر خواهد بود:
تابع هدف - 1 - به دنبال کمینه نمودن Cmax است و محدودیت - 2 - بر این نکته تأکید دارد که هر کار میتواند فقط بر روي یک ماشین در هر مرحله فرآیند شود. محدودیت - 3 - نشان میدهد که زمان تکمیل کار j در مرحله اول بزرگتر یا مساوي مدت زمان فرآیند آن در مرحله اول میباشد. رابطه میان زمان تکمیل کار j در دو مرحله متوالی در محدودیت - 4 - بیان شده است. مجموعه محدودیتهاي - 5 - و - 6 - نشان دهنده رابطه میان دو کار متوالی که بر روي یک ماشین میباشد. محدودیت - 7 - ن شان میدهد که اگر دو کار l و j به یک ما شین در مرحله i تخ صیص یابند مقدار متغیر برابر با 1 خواهد شد. سرانجام محدودیت - 8 -
بیان میدارد که متغیرهاي تصمیم صفر یا یک میباشند.
.3الگوریتم تجزیه بندرز
بسیاري از مسایلی که از نظر عملی از اهمیت برخوردارند را میتوان بهصورت ترکیبی از چند مسئله کوچک در نظر گرفت؛ در واقع بسیاري از سیستمهاي دنیاي واقعی داراي ساختارهایی غیر متمرکز هستند. الگوریتم تجزیه بندرز اولین بار توسط جی اف بندرز در سال 1692 ابداع شد. این روش اغلب براي حل مسائلی به کار میرود که شامل متغیرهاي پیوسته و گسسته هستند. ایده کلی الگوریتم بنابر تقسیم مسئله به دو قسمت است: یک زیر مسئله خطی که تنها شامل متغیرهاي پیوسته است و یک مسئله اصلی که شامل متغیرهاي گسسته پیچیده و محدودیتهاي مربوط به آنها است. زیر مسئله خطی حاصل به راحتی توسط روش برنامهریزي خطی قابل حل است. در واقع استراتژي الگوریتم بندرز بنابر ثابت کردن متغیرهاي گسسته و حل دوگان زیر مسئله خطی حاصل است. سپس الگوریتم با استفاده از جواب حاصل از دوگان زیر مسئله خطی، تعدادي برش - محدودیت - براي افزودن به مسئله اصلی تولید میکند. این روند تا جایی ادامه مییابد که مسئله اصلی داراي تعداد کافی برش براي رسیدن به جواب بهینه باشد.
.3,1 زیر مسئله2
زیر مسئله خطی تنها شامل متغیرهاي پیوسته است و متغیرهاي باینري موجود در مسئله اصلی در واقع در این قسمت مقادیر و ثابتی خواهند بود. زیر مسئله خطی حاصل به راحتی قابل حل است. در واقع استراتژي الگوریتم بندرز بنابر ثابت کردن متغیرهاي گسسته و حل دوگان زیر مسئله خطی حاصل است. در نتیجه مدل ریاضی زیرمسأله مسأله اصلی به صورت زیر خواهد بود:
