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

This report extends prior research on the “decision theory” approach for scheduling/sequencing (DTS). Compared to other construction heuristics like priority dispatching (PD) approaches, DTS has the advantage that it is flexible regarding a diverse range of regular and non-regular objectives. Furthermore, multiple decision criteria linearly combined within a single objective function can be addressed. 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.