Algorithms of minimizing the total tardiness on a single machine based on determination of shortest hamiltonian path in the graph and the dominance rules
The paper proposes a method, algorithms and its implementations using dominance rules for minimizing the total tardiness on a single machine based on shortest Hamiltonian path in a arbitrary graph that improve the efficiency and not reduce the execution time. Metrics for evaluating the effectiveness of the dominance rules are proposed. The experimental results of algorithms are developed that justify the effectiveness of the proposed modifications by getting local optimal solutions during procedure.