A vector space model for variance reduction in single machine scheduling

Abstract

Reducing the variance of part completion times about promised due dates is an important element of Just-In-Time production because it reduces the work-in-process inventory and tardiness simultaneously. Scheduling models and algorithms are developed to minimize the Mean Squared Deviation (MSD) of completion times about due dates on a single machine. A generic model is developed in real vector space for understanding the structural relationship between the optimal schedule and the location of the due dates. Geometric insights gained from this vector space model are used to relate the shortest and longest processing time sequences to the level of difficulty of the MSD optimization problem. The vector space model is used to develop dominance conditions for a branch and bound algorithm and to analytically synthesize parameters for a continuous variable feedback control algorithm for distributed scheduling. The control algorithm lends itself to massively parallel / distributed computation and is found to produce near optimal solutions efficiently, which makes it more scalable and practical compared to the branch and bound algorithm. Computational experiments with both approaches are presented.