Job shop scheduling with modified due dates

This paper introduces a new dispatching rule to job shop scheduling, extending earlier results to a multi-machine environment. This new rule, which uses modified due dates is compared to other popular dispatching methods over a range of due date tightness at two utilization levels. The results for mean tardiness indicate that the modified operation due date (¸<OD) rule compares very favorably with other prominent dispatching methods. The modified due date is a job’s original due date or the operation’s original due date or the operation’s early finish time, whichever is larger. A comparison of the job-based version with the operation-based version indicated that the operation-based version tended to be more effective at meeting due dates. The main performance measure was mean job tardiness, although the proportion of tardy jobs was also reported, and the two measures together imply the conditional mean tardiness. The MOD rule was compared to several well-known tardiness-orientated priority rules, such as minimum slack-per-operation (S/OPN), smallest critical ratio (SCR), and CONVERT. The MOD rule appeared to be more robust than the other rules to changes in the tardiness than the other rules, except under conditions where due dates were quite loose. In this situation, very little tardiness occurs for any of the rules. The MOD rule appeared to be more robust than the the other rules to changes in the tightness of due dates, and similar results occurred at both high and low utilizations.