کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10348149 | 699386 | 2012 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An exact approach for scheduling jobs with regular step cost functions on a single machine
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An exact approach for scheduling jobs with regular step cost functions on a single machine An exact approach for scheduling jobs with regular step cost functions on a single machine](/preview/png/10348149.png)
چکیده انگلیسی
This paper studies a single-machine scheduling problem whose objective is to minimize a regular step total cost function. Lower and upper bounds, obtained from linear and Lagrangian relaxations of different Integer Linear Programming formulations, are compared. A dedicated exact approach is presented, based on a Lagrangian relaxation. It consists of finding a Constrained Shortest Path in a specific graph designed to embed a dominance property. Filtering rules are developed for this approach in order to reduce the size of the graph, and the problem is solved by successively removing infeasible paths from the graph. Numerical experiments are conducted to evaluate the lower and upper bounds. Moreover, the exact approach is compared with a standard solver and a naive branch-and-bound algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 39, Issue 5, May 2012, Pages 1033-1043
Journal: Computers & Operations Research - Volume 39, Issue 5, May 2012, Pages 1033-1043
نویسندگان
Boris Detienne, Stéphane Dauzère-Pérès, Claude Yugma,