Track: Operations Management

Abstract

The one machine weighted tardiness problem has been studied extensively by researchers over the last few decades. It is a problem that is simple to state, but not easy to solve. It is a problem of sequencing a set of independent jobs on a single machine with the objective of minimizing total weighted tardiness. In view of its NP-hard nature, a decomposition-based heuristic is proposed and computationally compared with some well-known heuristics available in literature. The proposed heuristic consists of two phases. In the first phase, certain dominance conditions for a selective forward neighborhood swap are developed and applied. The second phase consists of a local improvement procedure using a single pass insertion technique to further improve the schedule. The simplicity of the algorithm enables manual solutions to small problems. Several problem-sets with different schedules and three measures of performance are used in this comparison. Initial results are promising and indicate that the proposed heuristic is the best for all measures of performance.

Keywords: Single machine scheduling, tardiness, dominance conditions, empirical results