THE LINE SEGMENTATION PROBLEM

This paper describes a line segmentation problem in a multistage, multimachine production system. The production facility can concurrently produce several types of circuit boards because each production stage consists of multiple machines. The items produced are categorized into families, and items belonging to the same family share the common major setup, while switching over from one family to another requires a major setup. The line segmentation problem determines an allocation of machines at each production stage to families so as to minimize the time to complete all jobs. As a result of segmenting the line, several minilines are formed which are dedicated to the production of items in each family. Forming dedicated minilines and producing the items in a family on the same line captures the benefits of group technology and focused factory. We first formalize the line segmentation problem as a quadratic integer programming problem, and establish its NP-completeness. Since the problem is NP-complete, we propose several heuristics to find a good solution. Lower bounding procedures are developed to show the quality of the feasible solution. We also provide bounds on the performance of the heuristic solutions, and then empirically evaluate their performance.