بخشی از مقاله
چکیده
مساله مورد بررسی در این پژوهش زمانبندی گروهی ماشینهای موازی غیر وابسته است. زمانبندی گروهی یکی از شاخههای مسائل زمانبندی و توالی عملیات است. در این حوزه از مسائل، کارها یا همان قطعات تولیدی براساس مشابهتهایشان به چندین گروه یا خانواده تقسیمبندی میشوند. با توجه به مفهوم تولید بهنگام، هدف مورد مطالعه کمینهسازی مجموع وزنی زودکرد و دیرکرد است. بخاطر اهمیتی که زمانهای آمادهسازی در مسائل برنامهریزی تولید دارند، زمانهای آمادهسازی را وابسته به توالی در نظرگرفتیم و یک مدل ریاضی خطی عدد صحیح مختلط - MIP - را برای این مساله توسعه دادیم. با کدنویسی این مدل در نرم افزار GAMS جواب بهینه برای مسائل با اندازه کوچک به دست آمد. با توجه به NP-hard بودن مساله تعدادی الگوریتم ابتکاری برای حل آن در زمان کوتاه پیشنهاد میشود.
کلمات کلیدی: زمانبندی گروهی، ماشینهای موازی غیر وابسته، الگوریتم ابتکاری، تولید بهنگام.
-1 مقدمه
زمانبندی یکی از مهمترین عناصر یک سیستم تولیدی است که در آن چگونگی تخصیص و توالی کارها - محصولات - به ماشینها، با توجه به معیارها و محدودیتهای سیستم، در افق برنامهریزی مشخص میگردد. مسایل زمانبندی ماشینهای موازی در میان مهمترین مسایل در ادبیات مربوط به زمانبندی قرار میگیرند. از دید تئوری، تعمیمی از مدل تک ماشین و حالت خاصی از مدل ماشینهای سری انعطاف پذیر است. مسائل ماشینهای موازی میتوانند به سه صورت یکسان، یکنواخت و غیر وابسته در نظرگرفته شوند .[1] در ماشین آلات یکسان، زمان پردازش در میان تمام ماشین آلات یکسان است. در ماشینهای یکنواخت، ماشین دارای سرعتهای مختلف است اما هر ماشین در یک نرخ ثابت کار میکند. ماشینهای غیر وابسته، برای زمانی است که ماشین میتواند در نرخهای متفاوتی کار کند و نیز هنگامی که یک ماشین معین بتواند کارهای مختلفی را در نرخهای مختلف پردازش کند تعریف میشود .[2] با توجه به اینکه ماشینهای موازی در این تحقیق غیر وابسته هستند لذا به دلیل اختلافهای موجود بین ماشینها، زمان مورد نیاز برای پردازش یک کار از ماشینی به ماشین دیگر تفاوت میکند.
مسائل زمانبندی را میتوان از دو دیدگاه مدیریت و مشتری مورد بررسی قرارداد. از دید مدیریت، کمینهسازی معیارهایی مانند بیشینه زمان تکمیل و بارگذاری ماشین، مورد توجه است؛ در حالی که از دیدگاه مشتری تحویل به موقع در موعد تحویل در اولویت قرار دارد که در سیستم تولید بهنگام - JIT - کاربرد زیادی دارد .[1] در ادبیات موضوع به طور کلی دو هدف کمینهسازی مجموع زودکردها و کمینهسازی مجموع دیرکردها به عنوان یک هدف واحد به نام زودکرد/ دیرکرد - ET - در نظر گرفته میشود که در واقع نشان دهنده مفهوم تولید بهنگام در محیط تولیدی است. تولید بهنگام نوعی فلسفه تولیدی است که با یک هدف بسیار ساده یعنی، اقلام مورد نیاز را با کیفیت مورد نیاز، به مقدار مورد نیاز و دقیقا در زمان مورد نیاز تولید کنید، ایجاد شده است. اجرای سیاست فوق منجر به انباشت حداقل محصول نهایی در انبار شده و از هزینههای نگهداری موجودی و سایر هزینههای مرتبط به میزان قابل توجهی خواهد کاست.
در حالیکه سیاست تولید بهنگام به برنامهریزی تولید بر اساس موعدهای تحویل هر سفارش تمایل دارد، تولید گروهی به ملاحظات آماده-سازی سفارشات متعلق به خانوادههای یکسان توجه دارد که به آن زمانبندی گروهی میگوییم. توسعه و به کارگیری تکنولوژی گروهی - GT - در زمانبندی گروهی و تولید سلولی - CM - تاثیر زیادی بر روی اجرای سیستمهای تولید دستهای کارآمد دارد .[3] در مسائل زمانبندی گروهی کارها یا همان قطعات تولیدی براساس مشابهتهایشان به چندین گروه یا خانواده تقسیمبندی میشوند. هر گروه شامل مجموعهای از قطعات است که شرایط یکسانی از لحاظ ابزارآلات مورد نیاز جهت پردازش، آمادهسازیهای مورد نیاز روی ماشینها و مسیر پردازش دارند. نتیجه این امر مساله زمانبندی گروههای کاری خواهد بود و هدف از آن تعیین توالی قطعات هر گروه و همچنین تعیین توالی خود گروههاست به نحوی که یک شاخص اندازهگیری بهینه شود. علاوه بر این، اجرای زمانبندی گروهی و سیستمهای تولید سلولی می-توانند منجر به زمانهای عملیاتی کوتاهتر، موجودیهای - سرمایههای - کمتر، کاهش انتقال و بررسی مواد و هزینههای تولید شوند .[3]
زمانبندی گروهی معمولا در دو سطح داخلی و خارجی انجام میشود. سطح خارجی توالی مطلوبی از بخشی از خانوادهها یعنی گروهها را پیدا میکند و سطح داخلی توالی مطلوب کارها در هر گروه را پیدا میکند. مسایل زمانبندی گروهی با و یا بدون فرضیات تکنولوژی گروهی بررسی میشود. تکنولوژی گروهی به طور متوالی همه کارهای یک گروه را وادار به پردازش میکند. اما زمانبندی بدون تکنولوژی گروهی اجازه میدهد تا گروه ها به زیر گروه ها تقسیم شوند. زمانبندی بدون تکنولوژی گروهی از زمان آمادهسازی دستهای استفاده میکند در حالیکه در زمانبندی با تکنولوژی گروهی از زمان آمادهسازی گروهی استفاده میشود. زمانهای آمادهسازی بین گروهها یا دستهها میتوانند وابسته به توالی یا مستقل از آن باشند. زمان آمادهسازی مستقل از توالی هنگامی است که زمانهای آمادهسازی مورد نیاز برای تغییر از یک گروه به گروه دیگر به ترتیب آنها بستگی ندارد؛ در غیر اینصورت مساله یک مساله وابسته به توالی است .[4]
قابل ذکر است همانطور که کارهای متعلق به یک گروه یکسان مشابه هستند، زمان آمادهسازی مورد نیاز برای تغییر از یک کار به کار دیگر در مقایسه با زمان اجرا ناچیز فرض میشود. با این حال، زمان آمادهسازی قابل ملاحظه ای برای تغییر از یک گروه به گروه دیگر مورد نیاز خواهد بود چرا که کارهای متعلق به گروهها متفاوت هستند. مساله تحقیقاتی موجود در این مقاله را با توجه به نمادگذاری مرسوم میتوان به صورت طبقه بندی کرد. عبارت بیانگر محیط ماشینهای موازی غیر وابسته است، بیانگر مساله زمانبندی گروهی است و وابسته بودن زمانهای آمادهسازی به توالی روی هر ماشین را بیان میکند و تابع هدف مساله را نشان میدهد.
افضلی راد و رضاییان[2]، لین و همکاران 5[] و ولّدا و همکاران [6] مساله زمانبندی ماشینهای موازی غیر وابسته را در نظر گرفتند. در مساله افضلی راد و رضاییان زمان آمادهسازی وابسته به توالی است اما در دو مساله دیگر زمان آمادهسازی وابسته به توالی و ماشین است. در این مسائل هدف کمینهسازی دامنه عملیات است. افضلی راد و رضاییان الگوریتمهای فرا ابتکاری مبتنی بر الگوریتم ژنتیک و سیستم ایمنی مصنوعی، لین و همکاران الگوریتم ترکیبی کلونی زنبور مصنوعی ولّدا و همکاران الگوریتم ژنتیک شامل جستجوی محلی سریع و جستجوی محلی افزایش یافته عملگر متقاطع را برای این مسائل ارائه کردند.
بلکریشنان و همکاران [7]، یک مدل برنامهریزی عدد صحیح مختلط برای حل مساله ماشینهای موازی یکنواخت توسعه دادهاند. به دلیل اختلافهای موجود بین ماشینها، زمان مورد نیاز برای پردازش کار از ماشینی به ماشین دیگر تفاوت میکند. آنها همچنین فرض کردهاند که هر کار زمانهای تحویل، زمانهای آزادسازی، جریمههای زودکرد و دیرکرد مجزایی دارد. هدف حداقل کردن کل دیرکرد و زودکرد وزنی است. آنها برای مسائل با اندازه بزرگ نیز روشی براساس روش تجزیه بندر ارائه کردهاند. الخمیس و همکاران [8]، یک مساله زمانبندی ماشین موازی با موعدهای تحویل مجزا در مورد زمان بیکاری مجاز ماشین را بررسی کردند. آنها یک الگوریتم ژنتیک و بازپخت شبیهسازی شده برای به حداقل رساندن مجموع وزنی زودکرد/دیرکرد پیشنهاد دادند.
نوگویرا و همکاران [9]، یک مساله زمانبندی ماشینهای موازی غیر وابسته با هدف کمینهسازی مجموع جریمههای زودکرد و دیرکرد را مورد بررسی قرار دادند. در این تحقیق زمانهای آمادهسازی وابسته به توالی کار و ماشین و همچنین زمانهای بیکاری در نظرگرفته شده است. برای این مساله سه الگوریتم ابتکاری پیشنهاد شده است. اولی یک الگوریتم ابتکاری روش جستجوی تطبیقی تصادفی حریص - - GRASP ساده است، الگوریتم ابتکاری دوم شامل یک روش تشدید مبتنی بر شیوه پیوند مجدد مسیر است و سومی یک روش ابتکاری جستجوی محلی تکراری است که در فاز جستجوی محلی از الگوریتم GRASP استفاده میکند. نتایج نشان میدهد که الگوریتم GRASP بطور قابل توجهی با استفاده از الگوریتمهای ابتکاری دوم و سوم بهبود یافته است.
زمانبندی گروهی نیز در طیف وسیعی از مسائل زمانبندی کاربرد دارد. لی و همکاران [10] ، به حداقل رساندن یک تابع هدف که شامل زودکرد، دیرکرد، تخصیص موعد تحویل و هزینههای جریان برای یک مساله زمانبندی گروهی مستقل از توالی بر روی تک ماشین است را مورد بررسی قرار دادند. لگندران و همکاران [11]، سه الگوریتم جستجوی ممنوع به منظور به حداقل رساندن کل زمان تکمیل برای یک مساله زمانبندی گروهی وابسته به توالی دو ماشینه را توسعه دادند. در این تحقیق آمادهسازی وابسته به توالی است. پس از آن سلماسی، لگندران و اسکندری [4]، کار خود را برای به حداقل رساندن دامنه عملیات مساله زمانبندی گروهی ماشینهای سری وابسته به توالی گسترش دادند، آنها یک الگوریتم بهینه سازی کلونی مورچگان ترکیبی را برای حل این مساله ایجاد کردند.
بزرگیراد و لگندران [4]، یک مساله زمانبندی گروهی با فرض تکنولوژی گروهی در محیط ماشینهای موازی نامرتبط را بررسی کردهاند.
آنها یک تابع هدف دو معیاره برای بهینهسازی مجموع وزنی از کل زمان تکمیل و کل دیرکرد را در نظر گرفتهاند، که به ترتیب به نفع تولیدکننده و مشتریان است. زمانهای آمادهسازی بین گروهها وابسته به توالی هستند. برای شباهت بهتر با موقعیتهای دنیای واقعی، زمان-های دسترسی کار و زمانهای دردسترس بودن ماشین به صورت پویا در نظرگرفته شده است. برای پیدا کردن راه حل بهینه/ نزدیک به بهینه مساله، الگوریتمهای فراابتکاری مبتنی بر جستجوی ممنوع ایجاد شده است. نتایج بدست آمده نشان میدهد این الگوریتم از درجه بالایی از بهره وری و اثر بخشی برخوردار است.
با توجه به آنچه گفته شد تا به امروز تحقیقات زیادی در مورد زمانبندی گروهی انجام نشده است. بنابراین با در نظر گرفتن زمانبندی گروهی در محیط ماشینهای موازی که از اهمیت زیادی در کارخانجات و سایر محیطهای تولیدی برخوردارند میتوان مقدار تولید، موجودی و اضافه کاریها را بهبود بخشید. در نظر گرفتن کمینهسازی مجموع وزنی زودکرد و دیرکرد به عنوان تابع هدف که هم به سود تولید کننده و هم به سود مشتری است نیز تاکنون در مسائل مربوط به زمانبندی گروهی ماشینهای موازی بررسی نشده است. سایر قسمتهای مقاله به شرح زیر سازماندهی شده است. بخش2، فرمولبندی و مدل ریاضی مساله است. در بخش3 به توصیف الگوریتمهای ابتکاری پیشنهادی برای حل مساله مورد نظر میپردازیم. در بخش4، به تجزیه و تحلیل نتایج خواهیم پرداخت و در نهایت بخش 5، نتیجه گیری این تحقیق را شامل میشود.
-2 مدل ریاضی مساله
برای مساله مورد بررسی در این پژوهش، یک مدل برنامهریزی خطی عدد صحیح مختلط - MIP - پیشنهاد میشود. در این مساله کار مختلف وجود دارد که روی ماشین موازی غیر وابسته پردازش میشوند. همه کارها در گروه مختلف قرار میگیرند که هر گروه شامل کار میباشد. هر کار مجاز است تنها روی یک ماشین پردازش شود، و همهی کارهای یک گروه نیز باید روی همان ماشین پردازش شوند. از طرفی، یک گروه نمیتواند روی یک ماشین پردازش شود اگر حداقل یک کار در این گروه وجود داشته باشد که نتواند روی آن ماشین پردازش شود. پارامترها و متغیرهای تصمیم و همچنین مدل ریاضی مساله به شرح زیر است:
-1-2 اندیس های مساله
