Programming algorithm for individual machines with distinct penalties for earliness and tardiness

In this work we consider the one machine problem, with distinct due-dates and penalties for earliness and tardiness. For a previously defined sequence, we utilize the sum of weighted lateness (earliness or tardiness) as objective function. This work is presented as a generalization of the Garey et al. scheduling algorithm. Using a computational structure called heap, this algorithm allows a schedule construction in O(nlogn) time while the best found in literature runs in O(n²).