Single machine scheduling to minimize total tardiness: New heuristics and empirical comparisons to existing heuristics

The single machine total tardiness problem is shown to be NP-hard. That is, large problems cannot be readily solved to optimality due to the exponential growth in computation time and core storage requirements. Therefore, considerable research has been devoted to the development of heuristic procedures.;Another purpose of this research is to discuss certain special properties for a neighborhood job swap in the case of the proposed heuristics. Also, certain dominance conditions for any two groups of tardy jobs are developed and proved for a special case.;Contributions and results. New heuristics are developed in the case of 1//TT and 1//TWT problems. These heuristics are hybrid in nature and use both decomposition rules and local search techniques such as selective neighborhood swap and insertion procedures. In the case of the 1|sij |Sigmati. and 1|sij|Sigmawit i problems, an AU-COVERT class of heuristics have been proposed and compared with two existing rules in current literature. And in the case of minimizing total tardiness of families of jobs, a new GEDD rule to minimize total tardiness and total weighted tardiness has been proposed.;The proposed heuristics are experimentally compared with some leading rules in current literature. A total of 1000 wide ranging problem sets (with different due dates and tardiness factors leading to tight, loose, and medium schedules) involving 100 jobs in each case were empirically tested on all the heuristics. The proposed heuristics have performed considerably well and found to be superior to the existing rules in most cases.;The purpose of this research is to propose new decomposition based heuristics and to experimentally compare them with the existing rules in the following areas: (1) Single machine total tardiness (1//TT) and total weighted tardiness problems (1//TWT). (2) Single machine total tardiness problem with sequence dependent setups (1|sij|Sigmati) and the total weighted tardiness problem with sequence dependent setups (1|s ij|Sigmawiti). (3) Single machine total tardiness and total weighted tardiness problems with families of jobs.;Computational work is coded in Fortran77 and run on a Cray J916 SuperComputer. Finally, the Kruskal-Wallis non-parametric test is used to statistically conclude if any significant differences exist amongst these heuristics.