بخشی از مقاله
چکیده
این مقاله به بررسی مساله زمانبندي در محیط جریان کاري منعطف1 با محدودیت انجام همزمان چند کار روي یک ماشین میپردازد. در ادبیات موضوع تاکنون به این مساله پرداخته نشده است. این مساله در مواردي که با ایستگاههایی چون کوره اعم از کوره هاي پخت و عملیات حرارتی، سندبلاست2، شات بلاست3 و ... که در آنها چند کار بطور همزمان میتوانند روي یک ماشین مورد پردازش قرار بگیرند، کاربرد دارد. ابتدا نشان میدهیم مساله از نوع NP-Hard است و سپس سه الگوریتم ابتکاري بمنظور حل مساله و یک کران پایین بمنظور مقایسه الگوریتمها توسعه داده میشود.
الگوریتمهاي ابتکاري ارائه شده بر پایه الگوریتمهاي مربوط به مساله ماشینهاي موازي4 ، تئوري محدودیتها5 و قاعده جانسون6 استوار هستند. در انتها نیز به مقایسه الگوریتمهاي ارائه شده با یکدیگر پرداخته ایم. تعداد زیادي از مسائل که بصورت تصادفی ایجاد شده اند، توسط این سه الگوریتم حل شده و نتایج آنها با کران پایین توسعه داده شده مقایسه گردیده است. نتایج نشاندهنده برتري نسبی الگوریتم مبتنی بر مساله ماشینهاي موازي است.
-1 مقدمه
این مقاله به بررسی زمانبندي چند کار روي چند ماشین در محیط جریان کاري منعطف با محدودیت انجام همزمان چند کار روي یک ماشین میپردازد. امروزه در اکثر محیطهاي تولیدي با ایستگاههایی مواجه میشویم که در آنها چند کار بطور همزمان میتوانند روي یک ماشین مورد پردازش قرار بگیرند. ایستگاههایی مثل کوره اعم از کوره هاي پخت و عملیات حرارتی، سند بلاست، شات بلاست ، ریخته گري - قالبهاي خوشهاي - و ... از جمله ایستگاههایی هستند که در آنها چند کار بطور همزمان میتوانند روي یک ماشین مورد پردازش قرار بگیرند. همچنین در مواردي که نمیتوان از زمان حمل و نقل بین ایستگاهها صرفنظر کرد و این حمل و نقل بصورت دستهاي صورت میپذیرد، میتوان حمل و نقل را بصورت ایستگاهی در نظر گرفت که در آن چند کار بطور همزمان میتوانند روي یک ماشین مورد پردازش قرار بگیرند.
Linn & Zhang [1] طی مقالهاي کارهایی که تا سال 1999 روي این مساله انجام شده بود را طبقه بندي کردند. اغلب این تحقیقات در زمینه مساله جریان کاري منعطف، بدون در نظر گرفتن هر گونه محدودیتی بود. بعد از این سال تحقیقات کمی روي مساله جریان کاري منعطف خالص صورت پذیرفت [2,3,4,5] و در اکثر تحقیقات، مساله مذکور با در نظر گرفتن محدودیتهایی مورد بررسی قرار میگرفت. Botta[6] به بررسی مساله جریان کاري منعطف، با در نظر گرفتن محدودیتهاي تقدمی7 و شکاف زمانی8 بین فعالیتها و تابع هدف کمینه کردن حداکثر تاخیرها9 پرداخت. Sawik[7] یک روش حل دقیق براي مساله جریان کاري منعطف، با در نظر گرفتن بافرهاي10 میانی محدود در بین مراحل ارائه داد.
Sawik[8] مجددا یک روش دقیق براي حل مساله جریان کاري منعطف، با در نظر گرفتن بافرهاي میانی محدود ارائه داد که علاوه بر محدودیتهاي مساله قبل فرض زمانبندي گروهی11 را نیز همراه خود داشت. Gupta et al[9] به بررسی مساله جریان کاري منعطف با محدودیت قابل کنترل بودن زمانهاي فعالیت و موعدهاي تحویل قابل تعیین پرداختند. آنها فرض کردند که توالی کارها در تمام مراحل یکسان است. تابع هدف مساله آنها کمینه کردن جمع وزنی زمانهاي تکمیل ، تاریخهاي تحویل12، زمانهاي زودکرد 13و زمانهاي دیر کرد 14کارها بود. Kurz & Askin[10] به بررسی مساله جریان کاري منعطف، با در نظر گرفتن زمانهاي آماده سازي15 وابسته به توالی16 و مجاز بودن پرش کارها از برخی مراحل پرداختند.
Kurz & Askin[11] مجددا به بررسی همین مساله پرداختند و پس از مدلسازي عدد صحیح مختلط 17مساله مذکور و ارائه یک کران پایین، یک الگوریتم ژنتیک18، بنام RKGA، براي آن ارائه نمودند. Bertel & Billaut [12] به بررسی مساله جریان کاري منعطف، با تابع هدف کمینه کردن جمع وزنی تعداد کارهاي دیرکرددار19 پرداختند. آنها فرض کردند که محدودیت متفاوت بودن سرعت ماشینها و مجاز بودن برگشت مجدد کارها 20به مراحل قبلی نیز وجود دارد.
Logendran & Carson [13] به بررسی مساله جریان کاري منعطف، با در نظر گرفتن زمانبندي گروهی و تابع هدف کمینه کردن حداکثر زمانهاي تکمیل پرداختند. Oguz et al [14] به بررسی مساله جریان کاري منعطف با تابع هدف کمینه کردن حداکثر زمانهاي تکمیل و این محدودیت که براي هر عملیات در هر مرحله چند ماشین مورد نیاز است، پرداختند. kyparisis & koulamas[15] به بررسی مساله جریان کاري منعطف، با تابع هدف کمینه کردن حداکثر زمان تکمیل کارها و با در نظر گرفتن محدودیت متفاوت بودن سرعت ماشینها پرداختند. Low[16] به حل مساله جریان کاري منعطف، با تابع هدف کمینه کردن جمع زمان جریان21 کارها توسط الگوریتم شبیه سازي بازپخت22 پرداخت.
وي فرض کرده بود که زمانهاي آماده سازي مستقل از توالی بوده ولی زمانهاي تخلیه23 وابسته به توالی هستند. مساله مورد بررسی در این مقاله تاکنون در ادبیات موضوع مورد بررسی قرار نگرفته است. در ادامه این مقاله، در بخش دو به تعریف مساله میپردازیم. در بخش سوم به ارائه روشهاي مختلف براي حل مساله مورد نظر پرداخته میشود. در بخش چهارم یک کران پایین براي مساله توسعه داده میشود. بخش پنجم به بیان نتایج محاسباتی بدست آمده از مقایسه و بررسی روشهاي مختلف حل مساله اختصاص یافته است و در بخش پایانی نتیجه گیري و زمینه هاي مختلف براي کارهاي آتی ارائه میگردد.
-2 تعریف مساله ش
مساله مورد نظر با زمانبندي در محیط جریان کاري منعطف سر و کار دارد. در این محیط فرض میشود که تعداد n کار وجود دارند که باید در m مرحله روي آنها پردازش انجام پذیرد. در هر مرحله مانند مرحله j تعداد l j ماشین وجود دارد. مسیر انجام پردازش براي تمام کارها یکسان می- باشد و هر کار باید از تمام مراحل بگذرد و در هر مرحله تنها باید روي یکی از ماشینها پردازش شود. همچنین زمان آماده بودن24 ، براي تمام کارها برابر صفر فرض میشود.
