Bottleneck Just-in-Time Sequencing for Mixed-Model Production Systems

Abstract

Due to today’s competitive automotive industrial challenges of providing a variety of products at a very low cost by smoothing productions on a flexible transfer line, one of the most important and fertile research topic in industrial mathematics is to penalize jobs both for being early and for being tardy. A problem is to determine a production sequence for producing different types of products on the line. Just-in-Time (JIT) mixedmodel production system is used to address this problem, which involves producing only the right products of different models of a common base product in evenly balanced sequences in the exact quantities, at the right times, at the right place. Sequencing JIT production system can be formulated as a challenging nonlinear integer programming problem. The goal of such system is to balance the rate of production of products. Minimization of the variation in demand rates for outputs of supplying processes is the output rate variation problem (ORVP) and minimization of the variation in the rate at which different products are produced on the line is the product rate variation problem (PRVP). The problem for minimizing of deviations between actual and desired production for PRVP can be solved efficiently in pseudo-polynomial time complexity. However, the ORVPs for two or more levels are strongly NP-hard. Heuristic algorithms and dynamic programming to solve such NP-hard problems are summarized. But ORVPs with pegging assumption are solvable by reducing them to the corresponding weighted PRVPs. The cyclic sequences are optimal for both sum and max deviation PRVPs. For the bottleneck PRVP, a binary search technique is used to test the existence of a perfect matching and thereby to get optimal sequence. A feasible sequence always exists such that, at all times, the deviation of actual production from the desired level of production for every product is never more than one unit for the max-absolute and maxsquared PRVPs. An elegant algebraic concept of balanced words is used to deal the bottleneck PRVP. The max-absolute PRVP is shown to be Co-NP with leaving its general complexity open. In this thesis, we study several interesting algebraic structures, properties, existence of cyclic solutions and two applications of bottleneck PRVP. An optimal sequence for an instance of max-absolute PRVP is obtained. With considering two min-sum and maxabsolute objectives, a bicriterion objective for balancing the sequence is analyzed. A comparative study of different objectives is also summarized. Moreover, several directions for further research are also explored including some emerged conjectures.