کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
475413 699303 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Mixed Integer Programming models for job shop scheduling: A computational analysis
ترجمه فارسی عنوان
مدل های برنامه نویسی عدد صحیح مختلط برای زمانبندی فروشگاه کار: یک تجزیه و تحلیل محاسباتی
کلمات کلیدی
فهرست مطالب مقاله
چکیده 
لغات کلیدی
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)، که یک روش متداول دیگر برای زمانبندی بوده و معروف ترین الگوریتم کامل برای ارائه ی یک نگرش وسیع میان رویکردهای مختلف می باشد، مقایسه می شوند.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی
In both industry and the research literature, Mixed Integer Programming (MIP) is often the default approach for solving scheduling problems. In this paper we present and evaluate four MIP formulations for the classical job shop scheduling problem (JSP). While MIP formulations for the JSP have existed since the 1960s, it appears that comprehensive computational studies have not been performed since then. Due to substantial improvements in MIP technology in recent years, it is of interest to compare the standard JSP models using modern optimization software. We perform a fully crossed empirical study of four MIP models using CPLEX, GUROBI and SCIP, focusing on both the number of instances that can be proved optimal and the solution quality over time. Our results demonstrate that modern MIP solvers are able to prove optimality for moderate-sized problems very quickly. Comparing the four MIP models, the disjunctive formulation proposed by Manne performs best on both performance measures. We also investigate the performance of MIP with multi-threading and parameter tuning using CPLEX. Noticeable performance gain is observed when compared to the results using only single thread and default parameter settings. Our results serve as a snapshot of the performance of modern MIP solvers for an important, well-studied scheduling problem. Finally, the results of MIP is compared to constraint programming (CP), another common approach for scheduling, and the best known complete algorithm to provide a broad view among different approaches.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 73, September 2016, Pages 165–173
نویسندگان
, ,