An algorithm for insertion of idle time in the single-machine scheduling problem with convex cost functions

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| < H/z.