کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141453 | 1489504 | 2013 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A polynomial time algorithm for makespan minimization on one machine with forbidden start and completion times
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider the problem of scheduling independent jobs on a single resource under a special unavailability constraint: a set of forbidden instants is given, where no job is allowed to start or complete. We show that a schedule without idle time always exists if the number of forbidden instants is less than the number of distinct processing times appearing in the instance. We derive quite a fast algorithm to find such a schedule, based on an hybridization between a list algorithm and local exchange. As a corollary minimizing the makespan for a fixed number of forbidden instants is polynomial.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 10, Issue 4, November 2013, Pages 241–250
Journal: Discrete Optimization - Volume 10, Issue 4, November 2013, Pages 241–250
نویسندگان
Christophe Rapine, Nadia Brauner,