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

چکیده 

لغات کلیدی

1. مقدمه 

2. سابقه 

2.1. تعریف مسئله 

شکل 1. مسئله ی زمانبندی فروشگاه کار. سه کار J1، J2، J3 در سه ماشین M1، M2 و M3 زمانبندی شده اند

2.2. مرور نوشته ها

3. مدل های MIP

3.1. مدل گسسته 

شکل 2. مدل گسسته

3.2. مدل گسسته ی لیائو

3.3. مدل شاخص زمانی 

شکل 3. مدل شاخص زمانی.

3.4. مدل مبتنی بر ترتیب بندی 

4. آزمایش ها و مباحث 

شکل 4. مدل مبتنی بر رتبه

جدول 1. مقایسه ی مدل های MIP برای JSP .  و  به ترتیب نشان دهنده ی تعداد ماشین ها، تعداد کار ها و تعداد کل نقطه های زمانی می باشند. 

4.1. نمونه های مسئله 

4.2. مقایسه ی مدل های MIP 

جدول 2. مقایسه ی مدل های MIP برای سه حل کننده ی مورد استفاده. اعداد برجسته بهترین

شکل 5. عملکرد MRE با گذشت زمان برای مدل های گسسته ی MIP با استفاده از CPLEX. 

(a) مسائل 15 x 15، (b) ta01 – ta10

 شکل 6. عملکرد MRE با گذشت زمان برای مدل های گسسته ی MIP با استفاده از SCIP

(a) مسائل 15 x 15، (b) ta01 – ta10

4.3. مقایسه ی نرم افزارهای مختلف بهینه سازی MIP 

4.4. مقایسه ی محدودیت های گسسته 

4.5. چند ریسگی و تنظیم پارامتر 

جدول 3. مقایسه ی فرمول های گسسته با استفاده از محدودیت های شاخص (با استفاده از CPLEX). اعداد برجسته بهترین فرمول را برای هر حل کننده ی مربوط به اندازه ی مسئله ی داده شده نشان می دهند. علامت – بدین معنی است که هیچ یک از 10 نمونه مسئله در کمتر از 3600 s به بهینگی حل نشدند. 

 جدول 4. مقایسه ی بهترین مدل MIP با چندریسگی و تنظیم پارامتر (با استفاده از CPLEX) و مدل CP. اعداد برجسته بهترین فرمول را برای هر حل کننده ی مربوط به اندازه ی مسئله ی داده شده نشان می دهند. علامت – بدین معنی است که هیچ یک از 10 نمونه مسئله در کمتر از 3600 s به بهینگی حل نشدند. 

4.6. مقایسه ی MIP و CP

4.7. مقایسه با آخرین تکنولوژی ها 

شکل 7. عملکرد MRE مدل های MIP، CP و iSTS-SGS با گذشت زمان. توجه داشته باشید که برای مسائل ta11-ta20، ابزار تنظیم تنظیمات پارامتری متفاوت تر از پیش فرض پیدا نکرده است. در نتیجه ما منحنی را برای تنظیم چندگانه طرح ریزی نکرده ایم، (a) مسائل 20 x 20، (b) ta11-ta20. 

5. نتیجه گیری 

ضمیمه ی A. مدل CP

در نوشته های صنعتی و هم در نوشته های تحقیقاتی، برنامه نویسی عدد صحیح مختلف (MIP) اغلب رویکرد پیش فرض برای حل مسائل زمانبندی می باشد. در این مقاله چهار فرمول MIP را برای مسئله ی سنتی زمانبندی فروشگاه کار (JSP) ارائه داده و ارزیابی می کنیم. در حالی که فرمول های MIP برای JSP از دهه ی 1960 پدید آمده اند، به نظر می رسد که مطالعات محاسباتی جامع از آن زمان اجرا نشده اند. به خاطر بهبود های چشمگیر در تکنولوژی MIP در سال های اخیر، مقایسه ی مدل های استاندارد JSP با استفاده از نرم افزار بهینه سازی مدرن مطلوب می باشد. ما با استفاده از CPLEX، GUROBI و SCIP یک مطالعه ی کاملا تجربی روی چهار مدل MIP انجام داده و بر روی تعداد نمونه هایی که می توانند ثابت شوند که بهینه هستند و کیفیت راه حل با گذشت زمان، تمرکز می کنیم. نتایج ما حاکی از این می باشند که حل کننده های مدرن MIP می توانند بهینگی را به سرعت برای مسائل اندازه-متوسط اثبات کنند. در مقایسه ی چهار مدل MIP، فرمول گسسته ی مطرح شده توسط مانه بهترین عملکرد را در هر دو مقیاس عملکردی ارائه می دهد. ما همچنین عملکرد MIP با تنظیم پارامتر و چند ریسگی با استفاده از CPLEX بررسی می کنیم. هنگام مقایسه ی نتایج با استفاده از تنها یک دنباله و مقداردهی های پیش فرض پارامتری، گین عملکردی چشمگیری مشاهده می شود. نتایج ما بعنوان تصویر لحظه ای عملکرد حل کننده های مدرن MIP برای مسئله ی زمانبندی مهم و به خوبی مطالعه شده، عمل می کنند. در نهایت نتایج MIP با برنامه نویسی محدود (CP)، که یک روش متداول دیگر برای زمانبندی بوده و معروف ترین الگوریتم کامل برای ارائه ی یک نگرش وسیع میان رویکردهای مختلف می باشد، مقایسه می شوند.

برنامه نویسی عدد صحیح مختلط (MIP) بطور گسترده ای به مسائل زمانبندی اعمال شده و این اغلب رویکرد اولیه برای حمله به مسئله ی جدید زمانبندی می باشد. برای مثال، از بین 40 تحقیق منتشر شده در مجله ی زمانبندی سال 2014، 14 مورد از MIP استفاده کرده اند، که بیش از هر تکنولوژی دیگری می باشد. با توجه به این محبوبیت، همراه با بهبودهای انجام پذیرفته در تکنولوژی MIP تجاری، درک اینکه مدل های مختلف MIP برای زمانبندی در بافت حل کننده های مدرن چگونه با همدیگر مقایسه می شوند، ارزشمند می باشد. سه فرمول پرکاربرد MIP برای مسائل زمانبندی عبارتند از: فرمول شاخص زمانی، فرمول مبتنی بر رتبه بندی، و فرمول گسسته. یک مقایسه ی نظری میان این فرمول ها حاکی از این است که فرمول گسسته بعنوان بهترین فرمول بوده و فرمول شاخص زمانی بدترین آن ها می باشد. با این حال، برخلاف تاریخچه ی طولانی این فرمول ها، به نظر تابه حال یک مطالعه ی کامل محاسباتی برای مقایسه ی عملکرد فرمول های مختلف با استفاده از حل کننده های MIP انجام نپذیرفته است. در جدیدترین مطالعه ما پی بردیم که اپل گیت و همکارانش یک الگوریتم شاخه و مرز براساس فرمول گسسته ارائه دادند و به این نتیجه رسیدند که JSP حتی برای مسائل دارای اندازه متوسط نیز از لحاظ محاسباتی چالش برانگیز می باشد. در این مقاله، ما عملکرد چهار مدل MIP خود را برای JSP سنتی مقایسه می کنیم. علاوه بر سه فرمول JSP استاندارد، ما یک فرمول گسسته ی دیگر ارائه می دهیم که لیائو ادعا کرده است بر فرمول اصلی برتری دارد. ما آزمایش های مربوط به سه حل کننده ی مختلف را انجام می دهیم: ، و . CPLEX و GUROBI هر دو بعنوان حل کننده های جدید تجاری MIP در نظر گرفته می شوند، در حالی که SCIP سریعترین حل کننده ی غیرتجاری می باشد. هدف ما ارائه ی مقایسه ی کامل تجربی مدل های MIP برای JSP با استفاده از حل کننده های مختلف MIP و شناسایی موثرترین مدل می باشد. نتایج تجربی ما با استفاده از CPLEX و GUROBI برخلاف Pan نشان می دهند که مدل شاخص زمانی می تواند بهتر از مدل مبتنی بر رتبه بندی برای مسائل کوچک عمل کند، اما در مقیاس بندی مسائل بزرگتر به خاطر اندازه مدل ناکام می ماند. بعلاوه، برخلاف یافته ی لیائو، نتایج ما نشان مید هند که مدل گسسته ی اصلی نسبت به مدل گسسته ی لیائو برای CPLEX و GUROBI موثرتر می باشد. با این حال، آزمایش های انجام پذیرفته با استفاده از SCIP، نتایج متفاوتی ارائه داده اند: اولا، مدل مبتنی بر رتبه بندی برای مسائل کوچک بر مدل شاخص زمانی برتری دارد، دوما، با این که در نگاه اول فرمول گسسته ی لیائو به نظر نسبت به فرمول گسسته ی اصلی موثرتر می باشد، اما بررسی دقیق مشخص می کند که این تفاوت ها به خاطر تکنیک های مختلف پیش پردازش به کار رفته توسط SCIP و پدیده ی گسستگی در فرآیند جستجوی حل کننده های MIP می باشند. برخلاف این تفاوت ها، در بین تمامی حل کننده های تست شده، مدل گسسته بر مدل های شاخص زمانی و مبتنی بر رتبه بندی برتری دارد. ما سپس دو جنبه ی حیاتی مدل های شاخص زمانی را بررسی می کنیم: چند ریسگی و تنظیم پارامتر. چندریسگی اجازه می دهد جستجو بصورت موازی انجام پذیرد و در نتیجه می تواند بطور چشمگیری عملکرد را بهبود بخشد. هدف تنظیم پارامتر یافتن بهترین مجموعه ی پارامترها برای دسته ی خاصی از مسائل می باشد. ما آزمایش ها را با بهترین مدل MIP یعنی مدل گسسته با استفاده از CPLEX انجام می دهیم. نتایج نشان می دهند که اجرای هشت دنباله بصورت موازی باعث بهبود 1.5 برابری عملکرد برای مسائلی که می توانند بهینه باشند می شود، که 4.5 برابر سریع تر از جستجوی پیش فرض تک دنباله ای می باشد. برای مسائلی قبلی که برای آن ها راه حل بهینه پیدا نشد و در عرض یک ساعت اثبات شد، کیفیت راه حل با گذشت زمان 30 درصد بهبود یافت. ما همچنین یک مقایسه از بهترین نتایج MIP با دو رویکرد کامل ارائه می دهیم: برنامه نویسی گسسته (CP) و iSTS-SGS، که دومی الگوریتم دقیق نوین می باشد. انگیزه های ما از مقایسه ی CP و MIP دوگانه می باشند. اولا، از آنجایی که MIP و CP بطور گسترده ای توسط متخصصین بعنوان تکنولوژی خارج از محدوده برای زمانبندی استفاده شده اند، درک تفاوت های بین عملکردهای آن ها ارزشمند می باشد. ثانیا، به خاطر بهبودهای چشمگیر حل کننده های MIP و CP در یک دهه ی گذشته، بررCPLEXشرفت های MIP و CP مطلوب می باشد. ما یک مطالعه ی تجربی با استفاده از CPLEX برای مدل گسسته ی MIP با تنظیم پارامتر و چند ریسگی و بهینه ساز برای مدل CP انجام داده ایم. نتایج تجربی ما نشان می دهند که MIP برای مسائل دارای اندازه ی متوسط و دارای هدف اثبات بهینگی، همانند CP عمل می کند. با این حال برای نمونه های بزرگتر JSP نسبت MIP برتری داشته و با iTST-SGS قابل مقایسه می باشد. بطور خلاصه نوآوری این مقاله در تجزیه و تحلیل تجربی مدل های MIP برای مسئله ی زمانبندی فروشگاه کار می باشد.