The Line Segmentation Problem

Reza H. Ahmadi and Hirofumi Matsuo
Additional contact information
Reza H. Ahmadi: University of California, Los Angeles, California

Operations Research, 1991, vol. 39, issue 1, 42-55

Abstract: 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.

Keywords: manufacturing; automated systems: populating printed circuit boards; production/scheduling: approximations/heuristics; production/scheduling; planning: formation of dedicated lines (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.1.42 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:39:y:1991:i:1:p:42-55

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().