| Abstract: | We study the level scheduling problem in a Just-in-Time system, determining the assembly sequence of products in a mixed model assembly line. The objective of the level scheduling problem is to minimize the deviation of the quantities of each component part withdrawn from predetermined target levels. In addition, side constraints guarantee that a product of one selected type cannot immediately follow a product of another selected type in the assembly sequence. The objective function incorporates absolute value operators to define the deviation of part usage from the target level. We show how this nonlinear objective function can be transformed so that the model takes the form of a 0/1 mixed integer linear program and describe formulation refinements and a pre-processing procedure which facilitate solution. The constraint set for the semi-assignment problem with side constraints is included as an embedded substructure of the level scheduling model, a 0/1 mixed integer linear program. First, we study the polyhedral structure of the semi-assignment problem with side constraints and identify a family of facets and valid inequalities. We prove that the facets identified for the problem are also facet-defining for the level scheduling problem. Then, we investigate the polyhedral structure of the level scheduling problem, presenting additional valid inequalities and facets. In addition, polynomial separation algorithms associated with the valid inequalities are presented. Computational results are also included. |
|---|