Optimal level schedules for mixed-model, Just-in-Time assembly systems

Abstract

<p>The usage problem which occurs in the scheduling of mixed-model assembly processes operating under Just-In-Time (JIT) methods is examined. A minimax objective function, which has not been considered previously for use with mixed-model JIT systems, is introduced to control these processes. A general integer programming model of the problem is developed with the goal being to determine optimal sequencing methods for various formulations of this model. It is shown that the single-level, unweighted version of the model can be solved to optimum using an algorithm which is polynomial in the total product demand. A graph theoretic representation of the problem permits the calculation of bounds on the objective value. Of particular significance is the upper bound which demonstrates that a feasible sequence always exists for each copy of every product in which the actual level of production never deviates from the ideal level by more than 1 unit. Symmetries within the problem are shown to exist which substantially reduce the computational effort. Extensions to weighted single-level problems are made. A dynamic programming (DP) algorithm is presented for optimizing the multi-level problem formulations. The time and space requirements of this DP are demonstrated. Tests of the DP's performance capabilities, characteristics and limitations are performed. As the growth of the DP's state space could severely restrict the problem size if all of the states are generated, a necessary screening method, employing simple heuristics, is used. The results of the testing indicate that the size of the problems which can be optimized is constrained by the solution time. Conversely, the size of the problems that could be optimized never became constrained by the storage requirements since the simple heuristics acted as highly efficient screening mechanisms. The experimentation also uncovered certain inherent solution characteristics.</p>