An expediting heuristic for the shortest processing time dispatching rule

Abstract

Recent research on the scheduling of job shops has demonstrated the need for dispatching rules that are effective over a wide range of due-date tightness. In this paper a new dispatching rule is presented and compared with other prominent dispatching rules. The new rule employs shortest-processing-time (SPT) scheduling in a controlled manner: using due-date information to expedite jobs that are late or behind schedule, and employing a heuristic to control the scheduling of jobs with long processing times. Based on a simulation analysis, the rule is shown to perform nearly as well as the SPT rule with respect to mean job flowtime, and without the undesirable SPT side-effect of large conditional mean tardiness. The rule is also shown to be robust to changes in due-date tightness. In comparison with other well-known dispatching rules, its performance is generally superior with respect to mean flowtime, mean tardiness and conditional mean tardiness, with only the COVERT rule performing nearly as well. Unlike the COVERT rule, which requires the estimation of a job's remaining shop queue time, the proposed rule requires no estimation of global shop characteristics.