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

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

Keywords:

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