Sequencing mixed model assembly lines for a Just-In-Time production system

This study is concerned with the mixed model assembly line sequencing problem for just-in-time production systems. Such a problem finds applications in flexible production lines where a uniform demand exists for N different item types and this demand needs to be satisfied in batches at a constant rate over a given planning horizon. Optimality properties are provided and used to develop a 0-1 integer linear programming formulation with three sets of constraints that considers varying batch processing times for different types of items. The first two sets of constraints are equivalent to the supply and demand constraints of an asymmetric assignment problem. The third set, which represents the process time non-overlap constraints, is relaxed to form a Lagrangian dual problem. The Lagrangian dual is then solved using a subgradient optimization technique. Some optimality conditions for the mixed model assembly line sequencing problem are provided. Efficient heuristics have been developed to yield an initial primal feasible solution and to convert a primal infeasible solution to a feasible solution. Computational results show that the average relative deviation from optimality for small size problems (up to 20 jobs) is 1.89%, for medium size problems (31-40 jobs) is 1.09%, and for large size problems (41-140 jobs) is 3.15%.