Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
476468 | Computers & Operations Research | 2005 | 12 Pages |
Abstract
This paper addresses the problem of optimally inserting idle time into a single-machine schedule when the sequence is fixed and the cost of each job is a convex function of its completion time. We propose a pseudo-polynomial time algorithm to find a solution within some tolerance of optimality in the solution space, i.e., each completion time will belong to a small time interval z within which the optimal solution lies. Letting H be the planning horizon and |J| the number of jobs, the proposed algorithm is superior to the current best algorithm in terms of time-complexity when |J|
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Emerson C. Colin, Roberto C. Quinino,