A New Algorithm for a Special Structure of the Single Machine Tardiness Problem

The single machine total tardiness problem has been studied extensively by researchers over the last fifty years. A recent exhaustive review of the single machine tardiness problem concluded that the structure of the one machine tardiness problem enables the development of problem-specific heuristic algorithms. Our study explores an important structure of this problem (a congested or a tight schedule) and proposes a heuristic algorithm to tackle it. In addition, we explore some fundamental conditions for optimality and prove that our proposed rule satisfies these conditions. We also provide insights as to why this structure cannot satisfy one specific fundamental condition