مقاله زمانبندی گروهی ماشینهای موازی یکسان با زمانهای آمادهسازی وابسته به توالی

بخشی از مقاله

چکیده

در پژوهش حاضر به بررسی زمانبندی گروهی ماشینهای موازی یکسان میپردازیم. مساله زمانبندی گروهی یکی از شاخههای مسائل زمانبندی و توالی عملیات است. در این حوزه از مسائل، کارها یا همان قطعات تولیدی براساس مشابهتهایشان به چندین گروه یا خانواده تقسیمبندی میشوند. با توجه به مفهوم تولید بهنگام، هدف مورد مطالعه کمینه سازی مجموع وزنی زودکرد و دیرکرد است. بخاطر اهمیتی که زمانهای آمادهسازی در مسائل برنامهریزی تولید دارند، زمانهای آمادهسازی را وابسته به توالی درنظرگرفتیم و یک مدل ریاضی خطی عدد صحیح مختلط - MIP - را برای این مساله توسعه دادیم. با کدنویسی این مدل در نرم افزار GAMS جواب بهینه برای مسائل با اندازه کوچک به دست آمد. با توجه به NP-hard بودن مساله تعدادی الگوریتم ابتکاری برای حل آن در زمان کوتاه پیشنهاد میشود.

-1 مقدمه

مسایل زمانبندی ماشینهای موازی در میان مهمترین مسایل در ادبیات مربوط به زمانبندی قرار میگیرند. از دید تئوری، تعمیمی از مدل تک ماشین و حالت خاصی از مدل ماشینهای سری انعطاف پذیر است. مسائل ماشینهای موازی میتوانند به سه صورت یکسان، یکنواخت و نامرتبط در نظرگرفته شوند. در ماشینهای یکسان، مدت زمان پردازش کارها مستقل از ماشین است، در حالی که در دو حالت دیگر زمان پردازش کارها روی ماشینها بر اساس نوع ماشین تغییر میکند .[1]

مسائل زمانبندی را میتوان از دو دیدگاه مدیریت و مشتری مورد بررسی قرارداد. از دید مدیریت، کمینهسازی معیارهایی مانند بیشینه زمان تکمیل و بارگذاری ماشین، مورد توجه است؛ در حالی که از دیدگاه مشتری تحویل به موقع در موعد تحویل در اولویت قرار دارد که در سیستم تولید بهنگام - JIT - کاربرد زیادی دارد .[1] در ادبیات موضوع به طور کلی دو هدف کمینهسازی مجموع زودکردها و کمینه-سازی مجموع دیرکردها به عنوان یک هدف واحد به نام زودکرد/ دیرکرد - ET - در نظر گرفته میشود که در واقع نشان دهنده مفهوم تولید بهنگام در محیط تولیدی است.

تولید بهنگام نوعی فلسفه تولیدی است که با یک هدف بسیار ساده یعنی، اقلام مورد نیاز را با کیفیت مورد نیاز، به مقدار مورد نیاز و دقیقا در زمان مورد نیاز تولید کنید، ایجاد شده است. در واقع تولید بهنگام به دنبال آن است تا تنها اقلام مورد نیاز را در زمان مناسب و به مقدار مورد نیاز تولید کند. این سادهترین تعریف از رویکرد تولید بهنگام است. اجرای سیاست فوق منجر به انباشت حداقل محصول نهایی در انبار شده و از هزینههای نگهداری موجودی و سایر هزینههای مرتبط به میزان قابل توجهی خواهد کاست. با استناد به فلسفه تولید بهنگام، شرکتها سعی در انجام کارها در زمانی نزدیک به موعد تحویلشان دارند. عدم تحقق این هدف منجر به تحمیل هزینههای متععدی به شرکت میگردد.

در حالیکه سیاست تولید بهنگام به برنامهریزی تولید بر اساس موعدهای تحویل هر سفارش تمایل دارد، تولید گروهی به ملاحظات آمادهسازی سفارشات متعلق به خانوادههای یکسان توجه دارد که به آن زمانبندی گروهی میگوییم . توسعه و به کارگیری تکنولوژی گروهی 2 - GT - در زمانبندی گروهی و تولید سلولی - CM - تاثیر زیادی بر روی اجرای سیستمهای تولید دستهای کارآمد دارد .[2] در مسائل زمانبندی گروهی کارها یا همان قطعات تولیدی براساس مشابهتهایشان به چندین گروه یا خانواده تقسیمبندی میشوند.

هر گروه شامل مجموعهای از قطعات است که شرایط یکسانی از لحاظ ابزارآلات مورد نیاز جهت پردازش، آمادهسازیهای مورد نیاز روی ماشینها و مسیر پردازش دارند. نتیجه این امر مساله زمانبندی گروه-های کاری خواهد بود و هدف از آن تعیین توالی قطعات هر گروه و همچنین تعیین توالی خود گروههاست به نحوی که یک شاخص اندازه-گیری بهینه شود. علاوه بر این، اجرای زمانبندی گروهی و سیستمهای تولید سلولی میتوانند منجر به زمانهای عملیاتی کوتاهتر، موجودی-های - سرمایههای - کمتر، کاهش انتقال و بررسی مواد و هزینههای تولید شوند .[2]

زمانبندی گروهی معمولا در دو سطح داخلی و خارجی انجام می-شود. سطح خارجی توالی مطلوبی از بخشی از خانوادهها یعنی گروهها را پیدا میکند و سطح داخلی توالی مطلوب کارها در هر گروه را پیدا میکند . مسایل زمانبندی گروهی با و یا بدون فرضیات تکنولوژی گروهی بررسی میشود. تکنولوژی گروهی به طور متوالی همه کارهای یک گروه را وادار به پردازش میکند . اما زمانبندی بدون تکنولوژی گروهی اجازه میدهد تا گروه ها به زیر گروه ها تقسیم شوند.

زمانبندی بدون تکنولوژی گروهی از زمان آمادهسازی دستهای استفاده میکند در حالیکه در زمانبندی با تکنولوژی گروهی از زمان آمادهسازی گروهی استفاده میشود. زمانهای آمادهسازی بین گروهها یا دستهها میتوانند وابسته به توالی یا مستقل از آن باشند. زمان آمادهسازی مستقل از توالی هنگامی است که زمانهای آمادهسازی مورد نیاز برای تغییر از یک گروه به گروه دیگر به ترتیب آنها بستگی ندارد؛ در غیر اینصورت مساله یک مساله وابسته به توالی است .[3]

قابل ذکر است همانطور که کارهای متعلق به یک گروه یکسان مشابه هستند، زمان آمادهسازی مورد نیاز برای تغییر از یک کار به کار دیگر در مقایسه با زمان اجرا ناچیز فرض میشود. با این حال، زمان آمادهسازی قابل ملاحظه ای برای تغییر از یک گروه به گروه دیگر مورد نیاز خواهد بود چرا که کارهای متعلق به گروهها متفاوت هستند. مساله تحقیقاتی موجود در این مقاله را با توجه به نمادگذاری مرسوم میتوان به صورت | , ℎ  | ∑ -  ʹ + " - طبقه بندی کرد. عبارت بیانگر محیط ماشینهای موازی یکسان است،

بیانگر مساله زمانبندی گروهی است و ℎ   وابسته بودن زمانهای آمادهسازی به توالی را بیان میکند و ∑ -  ʹ + " - تابع هدف مساله را نشان میدهد. بلکریشنان و همکاران [4]، یک مدل برنامهریزی عدد صحیح مختلط برای حل مساله ماشینهای موازی یکنواخت توسعه دادهاند. به دلیل اختلافهای موجود بین ماشینها، زمان مورد نیاز برای پردازش کار از ماشینی به ماشین دیگر تفاوت میکند. همچنین آنها فرض کردهاند که هر کار زمانهای تحویل، زمانهای آزادسازی، جریمههای زودکرد و دیرکرد مجزایی دارد. هدف حداقل کردن کل دیرکرد و زودکرد وزنی است. آنها برای مسائل با اندازه بزرگ نیز روشی براساس روش تجزیه بندر ارائه کردهاند.

آلوارز والدس و همکاران [5]، مساله زمانبندی مجموعه ای از کارها روی مجموعهای از ماشینهای موازی یکسان را مورد بررسی قرار داده-اند که هدف به حداقل رساندن مجموع وزنی جریمههای زودکرد و دیرکرد با توجه به موعد تحویل مشترک است. آنها دو روش فراابتکاری پیوند مجدد مسیر و جستجوی پراکنده را پیشنهاد کردند نتایج محاسباتی نشان میدهد که الگوریتمها راه حلهای خوبی در زمان محاسبات متوسط بدست میآورند.

الخمیس و همکاران [6]، یک مساله زمانبندی ماشین موازی با موعدهای تحویل مجزا در مورد زمان بیکاری مجاز ماشین را بررسی کردند. آنها یک الگوریتم ژنتیک و بازپخت شبیهسازی شده برای به حداقل رساندن مجموع وزنی زودکرد / دیرکرد پیشنهاد دادند. مصلحی و مهنام [1]، مساله کمینه سازی مجموع بیشینه زودکرد و دیرکرد بر ماشینهای موازی یکسان را مورد بررسی قرار دادند. آنها با استفاده از حدود بالا و پایین و اصول غلبه مناسبی که برای مساله توسعه داده شده است، یک رویه شاخه و کران برای دستیابی به زمانبندیهای بهینه ارائه کردند. همچنین برای حل مساله از دو روش فراابتکاری شامل الگوریتم ژنتیک و بهینه سازی گروه ذرات به منظور یافتن توالی مناسب در زمان کوتاه استفاده کردند.

زمانبندی گروهی نیز در طیف وسیعی از مسائل زمانبندی کاربرد دارد. لی و همکاران [7]، به حداقل رساندن یک تابع هدف که شامل زودکرد، دیرکرد، تخصیص موعد تحویل و هزینههای جریان برای یک مساله زمانبندی گروهی مستقل از توالی بر روی تک ماشین است را مورد بررسی قرار دادند. لگندران و همکاران [8]، سه الگوریتم جستجوی ممنوع به منظور به حداقل رساندن کل زمان تکمیل برای یک مساله زمانبندی گروهی وابسته به توالی دو ماشینه را توسعه دادند.

در این تحقیق آمادهسازی وابسته به توالی است. پس از آن سلماسی، لگندران و اسکندری [3]، کار خود را برای به حداقل رساندن دامنه عملیات مساله زمانبندی گروهی ماشینهای سری وابسته به توالی گسترش دادند، آنها یک الگوریتم بهینه سازی کلونی مورچگان ترکیبی را برای حل این مساله ایجاد کردند. وانگ و لیو [9]، یک مساله زمانبندی گروهی با دو معیار که به ترتیب هم زمانهای آمادهسازی و هم زمانهای پردازش کار توابعی افزایشی از زمان آغاز آن هستند را مورد مطالعه قرار دادند.

آنها دو هدف که در آن معیار اصلی مجموع وزنی زمان تکمیل و معیار ثانویه حداکثر قیمت است را بررسی کردند. یک الگوریتم زمان چند جملهای برای حل این مساله زمانبندی گروهی دو معیاره با زمانهای آماده-سازی رو به زوال و زمانهای پردازش کار ارائه شده است. بزرگیراد و لگندران [3]، یک مساله زمانبندی گروهی با فرض تکنولوژی گروهی در محیط ماشینهای موازی نامرتبط را بررسی کردهاند. آنها یک تابع هدف دو معیاره برای بهینهسازی مجموع وزنی از کل زمان تکمیل و کل دیرکرد را در نظر گرفتهاند، که به ترتیب به نفع تولیدکننده و مشتریان است.

زمانهای آمادهسازی بین گروهها وابسته به توالی هستند. برای شباهت بهتر با موقعیتهای دنیای واقعی، زمانهای دسترسی کار و زمانهای دردسترس بودن ماشین به صورت پویا در نظرگرفته شده است. برای پیدا کردن راه حل بهینه/ نزدیک به بهینه مساله، الگوریتمهای فراابتکاری مبتنی بر جستجوی ممنوع ایجاد شده است. نتایج بدست آمده نشان میدهد این الگوریتم از درجه بالایی از بهره وری و اثر بخشی برخوردار است.

اسچالر [10]، چند روش برای زمانبندی ماشینهای موازی یکسان با آمادهسازی خانوادگی هنگامی که هدف به حداقل رساندن مجموع دیرکردهاست را مورد بررسی قرار داد. این روشها روی چندین مجموعه مساله با تعداد خانوادههای مختلف کارها و ماشینها، توزیع-های زمان آمادهسازی مختلف و سطوح مختلف از موعد تحویل متراکم و  تغییر پذیر آزمایش شده است. نتایج نشان میدهد که الگوریتمهای ژنتیک موثرترین الگوریتمها برای مساله هستند. با توجه به آنچه گفته شد تا به امروز تحقیقات زیادی در مورد زمانبندی گروهی انجام نشده است.

بنابراین با در نظر گرفتن زمانبندی گروهی در محیط ماشینهای موازی که از اهمیت زیادی در کارخانجات و سایر محیطهای تولیدی برخوردارند میتوان مقدار تولید و موجودی را بهبود بخشید و هزینههای ناشی از اضافهکاریها را کم کرد که در نتیجه باعث صرفهجویی در زمان میشود. در نظر گرفتن کمینهسازی مجموع وزنی زودکرد و دیرکرد به عنوان تابع هدف که هم به سود تولید کننده و هم به سود مشتری است نیز تاکنون در مسائل مربوط به زمانبندی گروهی ماشینهای موازی بررسی نشده است. سایر قسمتهای مقاله به شرح زیر سازماندهی شده است. بخش2، فرمولبندی و مدل ریاضی مساله است. در بخش3 به توصیف الگوریتمهای ابتکاری پیشنهادی برای حل مساله مورد نظر میپردازیم. در بخش4، به تجزیه و تحلیل نتایج خواهیم پرداخت و در نهایت بخش 5، نتیجه گیری این تحقیق را در بر میگیرد.

-2 مدل ریاضی مساله

برای مساله مورد بررسی در این پژوهش، یک مدل برنامهریزی خطی عدد صحیح مختلط - MIP - پیشنهاد می شود. در این مساله کار مختلف وجود دارد که روی ماشین موازی یکسان پردازش می-شوند. همه کارها در گروه مختلف قرار میگیرند که هر گروه شامل کار میباشد.