On the flexibility of a decision theory-based heuristic for single machine scheduling

For sequencing a set of jobs on a single machine, DTS estimates the total effect of selecting the next job in the sequence. To this, the completion times for all jobs resulting from this decision need to be estimated. We provide an estimator for job completion times and prove it to be the expected completion time. We also prove that DTS using this estimator provides optimum solutions for a number of single machine scheduling problems. Finally, we provide an extensive computational study comparing DTS to 38 competing PD approaches for a large variety of objectives (31). The results indicate DTS to be a flexible and viable alternative to PD approaches almost independent of specific objectives and problem instance characteristics.