Heuristics for minimizing mean tardiness form parallel machines

The concept of parallel operations has been widely used in manufacturing and data processing. However, not many efficient methods have been proposed to reduce job tardiness. This article proposes an efficient heuristic to minimize the mean tardiness of a set of tasks with known processing times and due dates for single and m parallel machines. For the single-machine case, the proposed heuristic is compared with the well-known Wilkerson and Irwin algorithm; for the m parallel machine case, it is compared with an extension of the Wilkerson-Irwin algorithm. We also introduce a simple dispatching rule, and it is compared with some existing dispatching rules. The comprehensive simulation results show that the proposed heuristic performs better than the Wilkerson-Irwin algorithm at a significantly reduced computational time.