A comparison of dispatching rules for job shops with multiple identical jobs and alternative routeings

SUMMARY

In general job shop scheduling, n jobs have to be scheduled on m machines. We consider the job shop scheduling problems in which there are orders with sizes greater than one (therefore there are multiple identical jobs), and in which each operation can be processed on several machines (therefore there are alternative routeings for the operations). These characteristics of the problems impose special precedence relationships among operations. We compare various dispatching rules for list scheduling algorithms and test several methods for defining successors of an operation using the precedence relationships. Mean tardiness, mean flow time, and number of tardy jobs are used as performance measures in the comparison.