۲-۴-۲-۲- موعد تحویل نامعلوم
پانوالکر و همکاران[۵۳]مساله کلاسیک زمانبندی تک ماشینه و تخصیص موعد تحویل)این مساله بصورت خلاصه مساله[۲۷]pss گفته می شود که خلاصه ای از اسامی پایه گذاران آن می باشد(را بصورت زیر تعریف می کنند:
“n کار موجود یک موعد تحویل یکسان دارند که بایستی تعیین گردد.کارها قبل یا بعد از تعیین یک موعد تحویل روی یک ماشین تکمیل می گردند.این موعد تحویل جزئی از تابع هزینه میﺑاشد.مقدار جریمه مربوط به موعد تحویل خطی بوده و مستقل از کارها میﺑاشد. هدف, یافتن مقدار بهینه موعد تحویل و توالی بهینه کارها روی ماشین به گونه ای است که مجموع دیرکرد و زودکرد و هزینه مربوط به موعد تحویل حداقل گردد.”
آداموپولوس و پاپیس[۵۴]مساله زمانبندیn کار مستقل را روی m پردازنده موازی غیریکسان تحت یک موعد تحویل یکسان و نامعلوم برای کارها بررسی کردهﺍند.موعد تحویل یک متغیر تصمیممیﺑاشد.هدف, تخصیص کارها به ماشینﻫا و تعیین موعد تحویل به گونهﺍی است که کل هزینه حداقل شود.این هزینه ترکیبی از موعد تحویل نامعلوم و کل دیرکرد و زودکرد میﺑاشد.از آنجا که مساله NP-hard میﺑاشد, یک روش ابتکاری چندجمله ای بر حسب زمان برای حل آن توسعه داده شده است.این روش راه حلﻫای موثری برای مساله میﻳابد.این روش, روی یک مساله نمونه تولید شده بصورت تصادفی تست گردیده و کارایی آن نشان داده شده است.
بیسکپ و چنگ[۵۵]مساله زمانبندیn کار مستقل را رویm ماشین موازی بررسی کردهﺍند.آنها فرض کردهﺍند که شرکتﻫا دو هدف را در نظر دارند.یکی رسیدن به انحراف کم از موعد تحویل یکسان برای همه کارها و دیگری حداقل کردن زمان تکمیل کل کار.بنابراین هدف یافتن زمانبندی بهینه کارها روی ماشینﻫا و موعد تحویل یکسان بهینه برای تمامی کارها به گونهﺍی است که ترکیبی از کل دیرکرد و زودکرد وزنی و زمان اتمام حداقل شود.آنها نشان دادهﺍند که مساله NP-hardبوده و سپس یک نمونه قابل حل چند جملهﺍی بر حسب زمان برای آن ارائه دادهﺍند.سپس یک روش ابتکاری به منظور یافتن جوابهای نزدیک به بهینه برای این مساله توسعه داده شده و کارایی آن با بهره گرفتن از نتایج محاسباتی بدست آمده از چند مساله نمونه اثبات گردیده است.
موشیو[۵۶]مساله زمانبندی کارها و تخصیص موعد تحویل را برای ماشینﻫای موازی یکسان حل کرده است.مساله بصورت زیر می باشد.
“Nکار قرار است رویMماشین موازی یکسان انجام شوند.همه کارها در زمان صفر در دسترس بوده و همگی دارای موعد تحویل dمیﺑاشند که بایستی مقدار بهینه آن تعیین گردد.زمان بیکاری برای ماشینﻫا مجاز بوده ولی انقطاع کارها مجاز نمیﺑاشد.هدف یافتن زمانبندی و موعد تحویل به گونه ای است که مقدار Z(q,d)=min{WEmaxEj,WTmaxTj,Wdd} بهینه گردد.
تابع هدف از نوع minmaxمیﺑاشد. آنها روی معرفی یک الگوریتم ابتکاری برای حل این مساله NP-hard متمرکز شده اند.این الگوریتم ابتکاری شامل دو مرحله می باشد.در مرحله اول, یک زمانبندی بر اساس قاعده [۲۸] LPTبرای کارها ارائه گردیده و در مرحله دوم, مساله تخصیص موعد تحویل برای زمانبندی ایجاد شده در مرحله اول بررسی میﮔردد. سپس آنها یک حد پایین برای تابع هزینه یافتهﺍند. سپس نشان دادهﺍند که این روش ابتکاری(حد پایین) تحت چندین فرض عمومی مجانبا بهینه میﺑاشد. سپس آنها با بهره گرفتن از یکسری مطالعه عددی وسیع نشان دادهﺍند که الگوریتم ابتکاری و حد پایین ایجاد شده توسط آنها نتایج اجرایی بسیار خوبی را نشان میﺩهند.
موشیو و یاول[۵۷]مساله ای از توالی یک مجموعه کارهای مستقل روی یک مجموعه از ماشینﻫای موازی یکسان و تخصیص موعد تحویل به کارها را با هدف حداقل کردن مجموع دیرکرد وزنی و زودکرد وزنی و هزینه موعد تحویل در نظر میﮔیرند.آنها مساله[۲۹]GPSS(UJ) را در نظر میﮔیرند.این مساله برای حالت تک ماشینه میﺗواند بصورت زیر بیان شود:
“nکار مستقلJبایستی روی یک ماشین پردازش گردند.کارها در زمان صفر در دسترس هستند.موعد تحویل همه کارها که یک متغیر تصمیم میﺑاشد یکسان بوده و باdنمایش داده میﺷود.زمان عملیات کارj با pj نشان داده می شود. فرض میﮔردد که این مقدار برای همه کارها برابر با واحد باشد.سه جزء هزینه در نظر گرفته میﺷود.یکی برای زودکرد،یکی برای دیرکرد و دیگری برای موعد تحویل.هزینه هر واحد زودکرد کارj و هزینه هر واحد دیرکرد آن به ترتیب با Bj ,ajنشان داده میﺷود.جریمه هر واحد تعویق موعد تحویل با نشان داده میﺷود.تابع هدفی که بایستی حداقل گردد،بصورت رابطه ۲-۱۴می باشد.با بهره گرفتن از روش استاندارد سه پارامتری مساله بصورتمعادله۲-۱۵بیان می گردد
“
(۲-۱۴)
(۲-۱۵)
آنها نشان دادهﺍند که کل زمان مورد نیاز برای حل مساله GPSS(UJ) برای تک ماشین O(n2) میﺑاشد.این مقدار برایm ماشین موازی یکسان نیز صدق میﮐند.آنها همچنین مساله[۳۰]TWET(UJ) را در نظر میﮔیرند.این مساله مشابه مساله GPSS(UJ) میﺑاشد با این تفاوت که در آن مقدار برابر با صفر در نظر گرفته میﺷود.با بهره گرفتن از روش استاندارد سه پارامتری مساله بصورترابطه ۲-۱۶بیان میﮔردد.آنها یک الگوریتم( O(n3برای حالت تک ماشینه و یک الگوریتمO(n3) برای حالت mماشین موازی یکسان ارائه کردهﺍند.
(۲-۱۶)
آنها یک الگوریتم O(n4(n*logn)) برای حالت تک ماشینه برای حل مسالهGMWAL(UJ) [۳۱] ارائه کرده اند.این مساله مشابه مسالهGPSS(UJ) می باشد با این تفاوت که در آن تابع هدف بصورتminmax در نظر گرفته میﺷود.با بهره گرفتن از روش استاندارد سه پارامتری مساله برای حالت تک ماشین بصورت معادله ۲-۱۷بیان میﮔردد:
(۲-۱۷)
مین و چنگ [۵۸] از یک الگوریتم ژنتیک مختلط به منظور بدست آوردن جوابﻫای نزدیک به بهینه برای مساله تعیین موعد تحویل بهینه و زمانبندی کارها روی ماشینﻫای موازی یکسان استفاده کردهﺍند.هدف, حداقل کردن هزینه دیرکرد وزنی و زودکرد وزنی و هزینه تعویق موعد تحویل میﺑاشد. هر کار جریمه دیرکرد و زودکرد مجزایی دارد.
۲-۵- دسترسی محدود به ماشینها:
در این مسائل به هر یک از کارها یک زیر مجموعه از مجموعه ماسینها با عنوان مجموعه پردازشی نسبت داده می شود به طوریکه هر کار تنها بر روی ماشینهای موجود در مجموعه پردازشی خود می تواند پردازش شود.در یک نگرش کلی به محدودیت دسترسی محدود به ماشینها هر کدام از مجموعه های پردازشی مربوط به وضعیتی می باشد که در آن کار ها داری ویژگی هایی هستند که تنها بخشی از ماشینها قادر به پردازش آنها می باشند
مسائل ماشینهای موازی با محدودیت مجموعه های پردازشی در کلاس مسائل NP-HARD قرار دارند]۶۲[به همین خاطر محققان الگوریتم ابتکاری و فراابتکاری را برای بهینه سازی این نوع مسائل به کار گرفتند.لیونگ و لی ]۶۳[زمانبندی ماشینهای موازی نامرتبط را با محدویت دسترسی به ماشینها با تمرکز بر روی تابع هدف زمان پایان کار بیشینه بررسی نمودند.
۲-۵- جمع بندی :
با توجه به اهمیت معیار دیر کرد در سیستم های مختلف بخصوص JIT و نیاز به حفظ اعتماد مشتری بررسی ماشین های موازی با در نظر گرفتن معیار دیر کرد بسیار کاربردی و سودمند می باشد.از طرف دیگر اتمام کارها زودتر از موعد تحویل می تواند هزینه هایی مانند هزینه نگهداری برای شرکت ایجاد کند؛ بدین جهت معیار زود کرد نیز جهت تضمین میزان بهره وری بسیار سودمند بوده و در سیستم های تولیدی مورد توجه قرار می گیرد. در این فصل مطالعاتی از افراد مختلف در ارتباط با معیارهای مذکور آورده شده است و شرح مختصری از از هر مسأله آورده شده است. در فصل بعد مدل ریاضی مسأله مورد نظر ارائه گردیده و فرضیات مربوط به آن بیان می شود.
فصل سوم
مدل ریاضی پیشنهادی
۳-۱- مقدمه:
زمانبندی به طور وسیعی در محیط های صنعتی و تجاری که کارها باید در آن محیط ها با منابع محدود انجام شوند، مورد بررسی می باشد. درجه ارضاء اهداف مورد نظر در یک محیط صنعتی یا تجاری به طور زیادی تحت تأثیر مدل زمانبندی کارها در آن محیط می باشد. بنابراین روش مورد استفاده برای تعیین توالی کارها بسیار مهم است.
در بسیاری از موقعیت ها روش های ریاضی می توانند ابزار لازم الاجرا برای تعیین توالی تهیه کنند. فرموله کردن مسأله زمانبندی با روش های ریاضی جهت کنترل و بهینه کردن کارایی مسائل دنیای واقعی، درک موقعیت مسأله و مشخص کردن پیچیدگی مسأله مورد نظر، همواره مورد توجه محققان این علم بوده است.اگر چه رویکرد برنامه ریزی عدد صحیح به عنوان یک روش دقیق ظرفیت عملکرد محدودی در بهینه سازی مسائل زمانبندی در زمان محاسباتی معقول دارد.از سوی دیگر،بیشتر مسائل موجود در محیطهای صنعتی اندازه بزرگتری نسبت به ظرفیت محاسباتی مدل برنامه ریزی عدد صحیح دارند.با این وجود این مدلها جواب بهینه لازم برای توسعه و اعتبار سنجی عملکرد رویکردهای ابتکاری و فراابتکاری گوناگون را فراهم می نمایند.
برای نوشتن مدل ریاضی یک مسأله زمانبندی، ابتدا باید مشخصات مسأله از جمله : مشخصات کارها و پارامترهای مربوط به آنها، مدل ماشین ها و منابع، اهداف مورد نظر مسأله، فرضیات مسأله و محدودیت های تعریف شده در مدل را به طور واضح تشریح کرد.
۳-۲-تعریف مسئله:
مسئله زمانبندی ماشینهای موازی نامرتبط با محدودیت زمان نصب وابسته به توالی کارها ودسترسی محدود به ماشینها و محدوئیت زمان دسترسی به کارها به منظور کمینه سازی زودکرد و دیرکرد وزنی کارها به شرح زیر ارائه می گردد:
یک مجموعه از کار متمایز بر روی مجموعای از ماشین که به صورت موازی کنار هم قرار گرفتند پردازش می شود به طوریکه هر کار تنها بر روی یک ماشین پردازش می شود و هر ماشین در هر لحظه قادر به پردازش تنها یک کار می باشد.هر یک از کارها بر روی زیرمجموعه ای از مجموعه ماشینها به صورت ، می تواند پردازش شود.این زیر مجموعه اصطلاحا مجموعه های پردازشی نامیده میشود و تعداد مجموعه پردازشی در مسئله وجود دارد.بر روی هر کار در طول یک دوره زمانی معین یک بار پردازش صورت می پذیرد و به این دوره زمانی زمان پردازش اطلاق می شود.زمان پردازش کارها بر روی ماشینها نه تنها به نوع کار بلکه به نوع ماشین هم بستگی دارد و بین زمان های پردازش کارها بر وری ماشینهای مختلف رابطه مشخصی وجود ندارد.قبل از آغاز پردازش یک کار بر روی یک ماشین به منظور آماده سازی آن ماشین برای پردازش آن کار عملیاتی انجام می شود که از آن با عنوان عملیات نصب ماشین یاد می شود و به دوره زمانی که در آن عملیات نصب ماشین انجام میشود زمان نصب ماشین اطلاق میشود.این زمان به نوع کاری که بر روی ماشین پردازش می شود و به نوع کار قبلی پردازش شده و همچنین به نوع ماشین بستگی دارد و اصطلاحا به آن زمان نصب وابسته به توالی کارها اطلاق میشود. زمان دسترسی به کارها زمانی است که یک کار وارد کارگاه شده و آماده دریافت سرویس های لازم از ماشین های تولیدی است. این زمان، زودترین زمانی است که می توان عملیات پردازش را به روی یک کار آغاز نمود هر کار با در نظر گرفتن موقعیت آن در توالی پردازش کارها بر روی ماشین مربوطه پس از سپری شدن زمان نصب و زمان پردازش تکمیل می شود.هر کدام از کارها دارای موعد تحویل متمایز می باشند و میزان انحراف زمان تکمیل کارها از موعد تحویل به صورت زود کرد و دیر کرد زمانی محاسبه می شود.به زمان های زود کرد و دیر کرد هر کدام از کارها وزن هایی به صورت ضرایب متمایز نسبت داده می شود که بیانگر هزینه زمان های زود کرد و دیر کرد می باشند.مجموع این زمان های به عنوان معیار بهینه سازی مسئله محسوب شده و در نتیجه تابع هدف مسئله کمینه سازی هزینه های زود کرد و دیر کر کارها می باشد.
۳-۳- فرضیات مسئله:
فرضهای در نظر گرفته شده در این مسئله به صورت زیر است:
۱-زمان نصب وابسته به توالی هنگام تعویض کارها بر روی ماشینها وجود دارد
۲-هر کدام از کارها تنها بر روی زیر مجموعه ای از مجموعه ماشینها می تواند پردازش شوند
۳-تمامی کارها در ابتدای افق زمانبندی در دسترس نمی باشد به عبارتی پردازش کار نمی تواند قبل از زمان دسترسی آغاز شود
۴-تمامی ماشینها به طور مستمر دسترس هستند و امکان خرابی ماشینها وجود ندارد
۵-هر ماشین در هر لحظه قادر به پردازش تنها یک کار می باشد
۶-هر کار در طول زمان پردازش خود تنها بر روی یک ماشین پردازش می شود
۷-زمان های پردازش،نصب،موعد تحویل و ضرایب هزینه زود کرد و دیر کرد زمانی و زمان دسترسی به کارهامعین می باشد
۸-بیکاری ماشینها مجاز است
۹-کار مجازی نوع صفر مفروض است.این کار همواره در اولین موقعیت بر روی تمامی ماشینها پردازش می شود.زمان پردازش این کار صفر منظور می شود و شروع پردازش آن نیازی به انجام عملیات نصب ماشین ندارد
۳-۴- مدل ریاضی پیشنهادی:
در این بخش مدل ریاضی خطی پیشنهادی با رویکرد برنامه ریزی عدد صحیح برای مسئله مورد بررسی ارائه می گردد.پیش از ارائه مدل،به شرح پارامترهای ورودی ، متغیرهای تصمیم گیری،محدودیتها و تابع هدف آن پرداخته می شود:
۳-۴-۱- پارامترهای ورودی (ورودی مدل) :
مقادیر ورودی که باید در ابتدای حل مدل ریاضی مشخص شوند عبارتند از :
:تعداد کارها
: تعداد ماشینها
:زمان پردازش کار نوع j بر وری ماشین i
فرم در حال بارگذاری ...
