کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6894419 | 1445922 | 2018 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Algorithms for the unrelated parallel machine scheduling problem with a resource constraint
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Algorithms for the unrelated parallel machine scheduling problem with a resource constraint Algorithms for the unrelated parallel machine scheduling problem with a resource constraint](/preview/png/6894419.png)
چکیده انگلیسی
We consider the unrelated parallel machine scheduling problem with a renewable resource constraint (UPMR). For the two-machine variant of the problem, we propose a very efficient mixed-integer linear programming (MILP) model. For more than two machines, we propose a two-stage heuristic, which first uses a MILP model to calculate a lower bound and assign jobs to machines, and then uses a constraint programming (CP) model to schedule jobs on machines. If the solution of the two-stage heuristic is not proven optimal, the problem is solved using a CP model for the complete UPMR, with a hot start provided by the two-stage heuristic. New large benchmark problem instances with up to 1000 jobs are generated. Extensive computational experiments are carried out on these, as well as on smaller instances from the literature. Our algorithms obtain excellent solutions for much larger problem instances than previously proposed methods. For the UPMR with two machines, our MILP model solves all test instances to optimality in very modest computation times, greatly outperforming previously proposed methods. For the variant with more than two machines, our overall algorithm, which combines the two-stage heuristic with a full CP model, finds for the smaller instances from the literature better than or the same solutions as all previously proposed methods in considerably less computation time. Difficult types of problem instances are also identified for future research.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 271, Issue 3, 16 December 2018, Pages 839-848
Journal: European Journal of Operational Research - Volume 271, Issue 3, 16 December 2018, Pages 839-848
نویسندگان
Krzysztof Fleszar, Khalil S. Hindi,