Abstract
We explore a set of diverse tardiness related problems for single machine preemptive scheduling in their most general forms, and for each one of these problems we compare the performance of different solution approaches. We start by comparing the performance of two proposed heuristics versus the conventional modeling approach for the solution of the Total Weighted Tardiness problem with and without overtime capacity allocation. We continue the discussion focusing only on exact methods, and we do this by comparing the performance between the conventional model and an advanced model that borrows from the aggregate planning paradigm. We conclude our discussion by comparing the conventional and advanced modeling approaches under a set of diverse tardiness related problems including: Total Weighed Tardiness, Total Weighted Completion, Total Weighted Earliness and Tardiness and Total Weighted Number of Tardy Jobs. Via numerical experimentation and analytical methods we show that the the proposed heuristics as well as the advanced modeling approaches are more efficient at obtaining good quality solutions than their corresponding conventional models. For larger size problems, the advanced modeling approach and the heuristics represent more efficient tools for generating optimal or near-optimal schedules to a variety of tardiness related problems.