The job shop tardiness problem: A decomposition approach

An important criterion for evaluating the effectiveness of many manufacturing firms is their ability to meet due dates. In low to medium volume discrete manufacturing, typified by traditional job shops and more recently by flexible manufacturing systems, this criterion is usually operationalized on the shop floor through the use of prioritizing dispatching rules. The widespread use of dispatching rules had led to a number of investigations where the due date performance of various rules is compared. In contrast to previous research on dispatching rules, this paper proposes a new approach that decomposes the dynamic problem into a series of static problems. These static problems are solved in their entirely, and then implemented dynamically on a rolling basis. To illustrate this approach, a specific heuristic is developed that constructs the schedule for the entire system by focusing on the bottleneck machine. Computational results indicate that significant due date performance improvement over traditional dispatching rules can be obtained by using this new approach.