تحقیق بررسی مدلسازی و حل مسئله زمانبندی جریان های کارگاهی با زمان های تنظیم وابسته به توالی

توضیحات

تحقیق بررسی مدلسازی و حل مسئله زمانبندی جریان های کارگاهی با زمان های تنظیم وابسته به توالیسلولهاي توليدي1 معمولا شامل يك گروه از ماشين آلات كه به توليد محدوده مشخصي از خانواده ها2 تخصيص داده شده اند مي باشد. يك خانواده يك مجموعه اقلام3 است كه نيازمندي مشتركي به لحاظ ابزار و توالي هاي عملياتي دارند. در اين محيط، توليد سلولي نيازمند سه فعاليت برنامه ريزي، قبل از توليد واقعي است. نخست گروهبندي ماشين آلات در سلولهاي توليدي مختلف (فرم دهي سلولها4). دوم، اقلام باید به ماشين آلات مشخص در سلولهاي توليدي، تخصيص داده شوند (بار دادن به ماشين آلات5). سوم، اقلام باید در هر سلول توليدي زمانبندي شوند [5 و 6]. اغلب چنين مسائل زمانبندي شامل سلولهاي توليدي چندتايي و احتمالا پيچيده است. بنابراين تلاشهايی در جهت توسعه مفهوم زمانبندي جهت يك سلول توليدي در يك زمان صورت گرفته است. اين بخش از تحقیق به مسئله زمانبندي چند سفارش1 دريافتي از چند مشتري در فضای جریان کارگاهی جایگشتی2 با فرض آنكه فعاليتهاي مرتبط با فرم دهي و بار دادن انجام گرفته، مي پردازد. هر سفارش مي تواند به عنوان يك خانواده و هر كار به عنوان يك قلم در نظر گرفته شود. البته يك تفاوت عمده وجود دارد و آن اين است كه همه سفارشات به ابزار و توالي هاي عملياتي يكساني نياز دارند. در فرم دهي و باردادن سلولهاي توليدي، اقلام خانواده بر اساس توالي هاي عملياتي به سلولها تخصيص مي يابد. بنابراين جريان مواد و زمانبندي، حتي چنانچه اقلام توليدي نيازمند ابزار متفاوتي جهت تنظيمات باشند، ساده مي شود. در اين فرآيند ممكن است هر خانواده نيازمند ماشين آلات مشابهي باشد و مسلما اقلام با ترتيب مشخصي بر روي ماشين آلات پردازش مي شوند. اين سلولهاي توليدي سلول توليدي جریان کارگاهی خالص نام دارند و مشخص كننده جریان کارگاهی معمول مي باشند. اين شرايط در زمان وجود چندين خانواده با نيازمندي هاي متفاوت صادق نخواهد بود [5]. معمولا يك هزينه تنظيم عمده جهت تغيير پردازش از كارها در يك سفارش به سفارش ديگر نياز است. یکی از شناخته شده ترین مسائل زمانبندی مسئله زمانبندی جریان کارگاهی است. این مسئله برای بیش از پنجاه سال در میان محققین جایگاه ویژه ای را برای خود باز کرده است. در این مسئله m مرحله بصورت سری وجود دارد که در هر مرحله یک ماشین یا بیشتر وجود دارد. n کار باید بر روی m ماشین پردازش شوند. هر کار بر روی هر ماشین، یک زمان پردازش مثبت دارد. در جریان کارگاهی، همه کارها با یک ترتیب بر روی ماشین آلات پردازش می شوند. زمان پردازش هر کار در هر مرحله می تواند متفاوت باشد. در این شرایط برای هرماشین n! توالی از کارها وجود خواهد داشت و در کل برای مسئله (n!)m توالی ممکن خواهیم داشت. یک ساده سازی در این ارتباط، حفظ ترتیب پردازش کارها از ماشین 1 تا ماشین m است. این بدان معنی است که کارها با یک ترتیب بر روی همه ماشین آلات پردازش شوند. چنین مسئله ای تحت عنوان مسئله جریان کارگاهی جایگشتی شناخته می شود. در این حالت به اندازه n! توالی برای کارها وجود خواهد داشت که با این شرایط مسئله تحت عنوان مسئله کاملا سخت شناخته می شود [5]. از جمله صنایعی که مسائل زمانبندی جریان کارگاهی جایگشتی بصورت کاملا برجسته و حیاتی مطرح می باشد، صنعت نساجی، کابل و رنگ است. در این تحقیق سعی بر آن بوده است تا با ایده گرفتن از چنین صنایعی در دنیای واقعی، تعریف متفاوتی از مسئله زمانبندی بر اساس ماهیت این صنایع در شرایط واقعی ارائه گردد. در حقیقت در اين تحقيق ما يك سلول توليدي تكي كه شامل تعدادي ماشين آلات (مراحل) و تعدادي سفارش كه بايد بر روي ماشين آلات پردازش شوند را در نظر مي گيريم. هر سفارش یک مشتری مشخص دارد و شامل تعداد مشخصي از كارهاي مشابه است. كارهاي هر سفارش بايد از طريق سلولهای توليد، مرحله به مرحله پردازش شوند و زماني كه اولين كار يك سفارش شروع به پردازش شد، كارهاي متعلق به سفارشات ديگر تا زمان پردازش آخرين كار سفارش مربوطه نمي توانند پردازش شوند. در حقیقت انقطاع سفارش در هنگام پردازش مجاز نبوده ولی چنین کاری در هنگام ارسال سفارش امکان پذیر است. بدیهی است عدم امکان انقطاع سفارش در هنگام پردازش به دلیل هزینه های تنظیم بالا، در این گروه از صنایع و به خصوص در صنعت نساجی می باشد. كارهاي متعلق به يك سفارش دقيقا شبيه به يكديگر هستند و بنابراين زمان يا هزينه تنظيمي ميان دو كار از يك سفارش وجود ندارد. هر سفارش با توجه به مشتری مربوطه، زمان تحویل و هزینه تاخیر مشخص دارد و هزینه های تاخیر به ازای هر واحد از سفارش که با تاخیر ارسال می گردد و هر واحد زمانی تاخیر محاسبه می شود. به همین منظور و به جهت کاهش هزینه های تاخیر، انقطاع سفارش در هنگام ارسال برای مشتری امکان پذیر خواهد بود چراکه هر واحد از یک سفارش با تاخیر که زودتر به دست مشتری برسد هزینه تاخیر کمتری خواهد داشت. هزينه و زمان تنظيم اولين كار از هر سفارش به زمانبندي قبلي بستگي دارد. اين شرايط منطبق با بسياري از مسائل دنياي واقعي است. براي مثال در صنعت نساجی و به خصوص در فرآيند رنگرزي و ريسندگي (همه انواع الياف مانند اكريليك، پلي استر و A-10) تعدادي سفارش وجود دارد كه تفاوت ميان آنها رنگ آنهاست. هر سفارش اندازه مشخصي دارد و زمان و هزينه تنظيم كاملا وابسته به توالي است (فرآيند تميزكاري و انجام برخي تنظيمات براي رنگ جديد بسته به رنگ قبلي است). از سوی دیگر برخي توالي ها در تولید هزينه زيادي را تحمیل می کنند و ممكن است غير منطقي باشند. به عنوان مثال در صنعت ریسندگی، توليد الياف با رنگ كاملا روشن (سفيد، كرم روشن) بعد از الياف با رنگ كاملا تيره (سياه، سورمه اي و زرشكي) هزينه تنظيم بسيار بالايي دارد (بيش از دو روز فرآيند تميز كاري و حداقل به ازاي هر ماشين يك و يا دو سبد ضايعات). عدم امكان پذيري اين توالي ها بسته به حد بالاي هزينه توليد است. مسلما با توجه به قيمت فروش، هر سفارش يك حد بالا جهت هزينه هاي توليد دارد كه توليد با بيشتر از آن هزينه، غير منطقي است. شرايط مشابهي نيز در صنعت كابل در شرایطی كه رشته سيم هاي رنگي توليد مي شوند وجود دارد. می توان مثالهاي متعددي به خصوص در صنايع شيميايي و صنايع نساجي پيدا نمود كه اين شرايط صادق باشد. جداي از وابستگي ميان توالي ها، اين عدم امكان پذيري برخي از توالي ها (بر اساس حد بالاي هزينه توليد) در ادبيات موضوع كاملا ناديده گرفته شده است. همچنين ما به دنبال يك تابع هدف واقعي براي مسئله هستيم. با يك مرور سريع در ارتباط با ادبيات موضوع ما با بسياري از معيارها در ارتباط با تابع هدف مواجه مي شويم. ولي در فرآيند زمانبندي، تابع هدف بايد شامل بر همه هزينه هاي سيستم كه وابسته به تصميمات زمانبندي هستند باشد [2]. در مسائل زمانبندی دنياي واقعي، در نظرگيري اجزاء هزينه و معيارهاي گوناگون تصميم اهميت زيادي دارد و صرفا لحاظ نمودن یک معیار عمده (همانند زمان ختم کل که در بسیاری از تحقیقات پیشین به چشم می خورد) سئوال برانگيز است. در اين تحقيق فرض بر وجود استراتژي توليد جهت سفارش1 است. در این استراتژی، تولید بر اساس سفارشات رسیده انجام می شود و برخلاف استراتژی تولید جهت انبار2 که ابتدا تولید انجام شده و سپس کالا در انبار به منظور یافتن مشتری مناسب نگهداری می شود، کالایی بدون وجود سفارش از طرف مشتری تولید نخواهد شد. انبوهی از سفارشات در پریود نخست دریافت می شوند که تعدادي از آنها بر اساس توان توليد قبول و بقيه رد مي شوند. این فرضیات نیز بر اساس شرایط دنیای واقعی جهت صنایع ذکر شده در نظر گرفته شده اند. منابع تولید باید به گونه اي زمانبندي شوند تا تمامي هزينه هاي ملموس چون هزينه ديركرد، هزينه تنظيم و هزينه نگهداري که از جمله حیاتی ترین معیارها در مباحث زمانبندی و برنامه ریزی تولید در بسیاری از صنایع است، حداقل شود. در چنين شرايطي قائدتا يك مدل زمانبندي چند معياره نياز است. همانگونه که از توضیحات بر می آید در تحقیق حاضر، کارها در مسائل جریان کارگاهی معمول با سفارشات جایگزین شده اند. زمانبندی تعدادی از سفارشات که هر سفارش حاوی تعداد مشخصی از کارهای مشابه و یک مشتری مشخص با زمان تحویل قطعی و همچنین هزینه تاخیر مشخص است، محور اصلی تحقیق است. در مسئله مورد بررسی هزینه های نگهداری و تاخیر اهمیت فراوان دارد. در این گونه مسائل، تصمیمات زمانبندی دو سطح دارد. در سطح بالاتر زمانبندی سفارشات قرار دارد به نحوی که کدام سفارش و به چه نحوی و با چه ترتیبی باید پردازش شود. سطح بعدی زمانبندی کارهای داخل هر سفارش است به این ترتیب که کارها با چه ترتیبی و به چه شکلی باید پردازش شوند. در اینجا صرفا سطح نخست بررسی می شود و ترتیب پردازش کارهای داخل هر سفارش، موضوع این تحقیق نیست. در مسئله مورد بررسی، زمان و هزینه های تنظیم مهم و وابسته به توالی می باشند. کارهای داخل هر سفارش کاملا مشابه فرض می شوند و زمان و هزینه تنظیم میان دو کار از یک سفارش نادیده گرفته می شود. همچنین فرض می شود برخی از توالی ها میان سفارشات ناممکن باشد. همانگونه که در ادامه تحقیق تحلیل خواهد شد اضافه نمودن چنین فرضی، یافتن یک جواب اولیه برای مسئله مورد بررسی بر اساس روشهای ابتکاری موجود را بسیار دشوار می سازد. يك زمان تحويل مشخص و هزينه تاخير معين براي هر سفارش (بر اساس نظر مشتري آن) فرض مي شود. هدف حداقل نمودن هزينه هاي تنظيم، تاخير و نگهداري می باشد. همانگونه که در ادامه بررسی خواهد شد با توجه به خصوصیات مسئله مورد بررسی روشهاي ابتكاري موجود در حل مسئله چندان كارا نمي باشند بنابراين در این تحقیق يك روش ابتکاری جهت یافتن جواب اولیه و همچنین یک روش ابتکاری جهت بهبود جواب اولیه بر اساس روش شبیه سازی تبریدی1 به منظور حل مسئله زمانبندي ارائه خواهد شد. در مجموع، عدم توجه به گروه عظیمی از مسائل زمانبندی در دنیای واقعی در ادبیات موضوع، انگیزه اصلی طرح مسئله حاضر می باشد که با توجه به کاربردی بودن آن می تواند به عنوان یک ضرورت در تحقیق مطرح باشد. مسلما چنین توجهی به مسائل زمانبندی در صنایع با توجه به فرضیات واقعی آن می تواند فاصله عمیقی که بعضا میان مسائل دنیای واقعی و مباحث علمی وجود دارد را کاهش داده و سرفصل جدیدی را جهت این دسته از مسائل بگشاید. همانگونه که در ادامه بصورت برجسته تر مطرح می گردد، عمده تولیدات علمی در زمینه مسائل زمانبندی در سابقه موضوع بر اساس شرایط بسیار محدود از دنیای واقعی بوده و انگیزه اصلی در پرداختن به آنها عمدتا شکست روشهای ابتکاری با توسعه بیشتر آنها می باشد. مسلما درنظرگیری شرایط دنیای واقعی موجب پیچیده تر شدن مسئله خواهد شد که در این حیطه استفاده از روشهای فراابتکاری موثر راهگشا خواهد بود. متدولوژی کلی تحقیق منطبق بر گام های ذیل می باشد: 1) تشریح شرایط زمانبندی در صنایعی چون نساجی، کابل و رنگ 2) مدلسازی مسئله با توجه به فرضیات واقعی 3) حل مسئله با بکارگیری یک روش ابتکاری شامل بر: 3-1) ساخت جواب اولیه با کمک گرفتن از دانش تئوری گراف 3-2) بهبود جواب اولیه با استفاده از روش ترکیبی شبیه سازی تبریدی 4) مقایسه روش ارائه شده با یک روش مناسب در ادبیات موضوع 5) حذف برخی فرضیات مسئله جهت نزدیک شدن به مسائل معروف زمانبندی که در مرور ادبیات بصورت گسترده به آن پرداخته شده است. 6) توسعه روشهای ترکیبی مختلف بر اساس الگوریتم ژنتیک، بهینه سازی جامعه مورچگان و الکترومغناطیس به منظور شکست بهترین روشهای فراابتکاری موجود در ادبیات موضوع فرمت فایل : Word ( قابل ویرایش ) تعداد صفحات : 91