QUADRATIC ASSIGNMENT ALGORITHMS FOR THE DYNAMIC LAYOUT PROBLEM

被引：82

作者：

LACKSONEN, TA

ENSCORE, EE

机构：

[1] Department of Industrial and Systems Engineering, Ohio University, Athens, OH, 45701

[2] The Pennsylvania State University, PA

来源：

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH | 1993年 / 31卷 / 03期

关键词：

D O I：

10.1080/00207549308956741

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

In a dynamic facilities layout problem, the objective is to minimize total costs: the flow costs over a series of discrete time periods plus the rearrangement costs of changing layouts between time periods. By assuming unit department sizes, the problem is modelled as a modified quadratic assignment problem. Five algorithms are modified to include the dynamic aspects. A cutting plane algorithm found the best solutions to a series of realistic test problems, outperforming exchange, branch and bound, dynamic programming and cut tree algorithms. It was able to solve a 30-location 5-time-period problem in 200 CPU seconds.

引用

页码：503 / 517

页数：15

共 50 条

[1]

Apple J., Deisenroth M., A Computerized Plant Layout Analysis and Evaluation Technique, pp. 112-117, (1972)

[2]

Armour G.C., Buffa E.S., A heuristic algorithm and simulation approach to relative location of facilities, Management Science, 9, pp. 294-309, (1963)

[3]

Block T.E., On the complexity of facilities layout problems, Management Science, 25, pp. 280-284, (1979)

[4]

Burkard R.E., Bonniger T., A heuristic for quadratic boolean problems with applications to quadratic assignment problems, European Journal of Operations Research, 13, pp. 374-386, (1983)

[5]

Burkard R.E., Stratman K.H., Numerical investigations of quadratic assignment problems, Naval Res Logistics Quart, 25, pp. 129-148, (1978)

[6]

Connolly D.T., An improved annealing scheme for the QAP, European Journal of Operations Research, 46, pp. 93-100, (1990)

[7]

Drezner Z., DISCON: A new method for the layout problem, Operations Research, 28, pp. 1375-1384, (1980)

[8]

Drezner Z., A heuristic procedure for the layout of a large number of facilities, Management Science, 33, pp. 907-915, (1987)

[9]

Edwards H., Gillett B., Hale M., Modular allocation technique, Management Science, 17, pp. 151-169, (1970)

[10]

Foulds L.R., Techniques for facilities layout: Deciding which pairs of activities should be adjacent, Management Science, 29, pp. 1414-1426, (1983)

← 1 2 3 4 5 →