Single machine scheduling to minimize weighted earliness subject to no tardy jobs (Q1105480)

At first, the authors study the weighted earliness problem with the added constraint that no machine idle time is allowed. The problem is shown to be equivalent to a scheduling problem where the objective is to minimize the weighted completion time subject to no tardy jobs and the authors use the known results in order to solve their problem. A heuristic algorithm is provided and several cases of the weighted earliness problem with the added constraint that can be solved optimally by using this heuristic algorithm are identified. For the weighted earliness problem without the added constraint a heuristic algorithm is proposed and cases of the problem are identified for which this heuristic is optimal. Moreover a dynamic programming algorithm is given. Computational results for several control parameters to illustrate the proposed algorithms are also presented.