Abstract: A flexible dynamic Job shop scheduling problem with jobs releasing and delivering both in batches, which arises from the context of auto-parts production systems, is addressed. In the problem, jobs are released to workshop successively in batches over time; a batch should be delivered as a whole when all the jobs in it are finished. In the shop, there are several types of machines, each of which consists of some identical machines. Total tardiness of all batches under consideration and the proportion of tardy batches are taken as two performance measures. For the problem being strongly NP-hard, a scheduling experiment is conducted by discrete event dynamic system simulation. In the modeling of discrete event system, setting methods of the release times and the due dates of job batches are proposed. A total of fifteen dispatching rules, including six new proposed dispatching rules and nine dispatching rules selected from literature, are put into the scheduling experiment. Performance evaluations are conducted by one-way analysis of variance and post-hoc comparisons with the experiment results. The evaluations indicate that a new proposed dispatching rule, equivalent modified earliest due date for batch(EMDD.b), has the overwhelming superiority to the other rules under consideration, and the five other new proposed rules also perform well with respect to the one or two performance measures.

Key words: Job shop, dynamic scheduling, flexible scheduling, dispatching rule, discrete event system simulation