Knapsack-based Algorithms for Designing Cellular Manufacturing Systems
研究了单元制造中的机器分配问题，建立0-1线性规划模型，考虑机器利用成本、单元间移动成本等因素，证明问题为NP完全，并提出两种基于背包问题的设计算法。
In this paper, we use a 0–1 linear programming model for the machine assignment problem in cellular manufacturing. The formulated machine assignment problem considers many manufacturing factors such as machine utilization cost, cost of intercellular moves, part demand, and operating time capacity. The problem is shown to be NP-complete. Two designing algorithms are proposed to exploit the problem structure of the knapsack problem. Computational experience of the two algorithms is also reported.