کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4959540 | 1445954 | 2017 | 27 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Anchored reactive and proactive solutions to the CPM-scheduling problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Anchored reactive and proactive solutions to the CPM-scheduling problem Anchored reactive and proactive solutions to the CPM-scheduling problem](/preview/png/4959540.png)
چکیده انگلیسی
In a combinatorial optimization problem under uncertainty, it is never the case that the real instance is exactly the baseline instance that has been solved earlier. The anchorage level is the number of individual decisions with the same value in the solutions of the baseline and the real instances. We consider the case of CPM-scheduling with simple precedence constraints when the job durations of the real instance may be different than those of the baseline instance. We show that, given a solution of the baseline instance, computing a reactive solution of the real instance with a maximum anchorage level is a polynomial problem. This maximum level is called the anchorage strength of the baseline solution with respect to the real instance. We also prove that this latter problem becomes NP-hard when the real schedule must satisfy time windows constraints. We finally consider the problem of finding a proactive solution of the baseline instance whose guaranteed anchorage strength is maximum with respect to a subset of real instances. When each real duration belongs to a known uncertainty interval, we show that such a proactive solution (possibly with a deadline constraint) can be polynomially computed.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 261, Issue 1, 16 August 2017, Pages 67-74
Journal: European Journal of Operational Research - Volume 261, Issue 1, 16 August 2017, Pages 67-74
نویسندگان
Pascale Bendotti, Philippe Chrétienne, Pierre Fouilhoux, Alain Quilliot,