Bottleneck Just-in-Time Sequencing for Mixed-Model Production Systems
Files
Date
2008
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Department of Mathematics
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.
Description
Keywords
Bottleneck, Time Sequence