Knapsack-Based Algorithms for Designing Cellular Manufacturing Systems
本文用0-1线性规划模型解决单元制造中的机器分配问题，考虑多种制造因素，证明问题为NP完全，并提出两种背包算法，报告了计算经验。
AbstractIn 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.Keywords: cellular manufacturinglayoutknapsack algorithms