کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
474159 | 698846 | 2008 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Lagrangian bounds for just-in-time job-shop scheduling
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Lagrangian bounds for just-in-time job-shop scheduling Lagrangian bounds for just-in-time job-shop scheduling](/preview/png/474159.png)
چکیده انگلیسی
We study the job-shop scheduling problem with earliness and tardiness penalties. We describe two Lagrangian relaxations of the problem. The first one is based on the relaxation of precedence constraints while the second one is based on the relaxation of machine constraints. We introduce dedicated algorithms to solve the corresponding dual problems. The second one is solved by a simple dynamic programming algorithm while the first one requires the resolution of an NP-hard problem by branch and bound. In both cases, the relaxations allow us to derive lower bounds as well as heuristic solutions. We finally introduce a simple local search algorithm to improve the best solution found. Computational results are reported.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 35, Issue 3, March 2008, Pages 906–915
Journal: Computers & Operations Research - Volume 35, Issue 3, March 2008, Pages 906–915
نویسندگان
Philippe Baptiste, Marta Flamini, Francis Sourd,