viii
Contents
3.2 Multi-Row Facility Layout .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 38
3.2.1 Initial Mixed-Integer Linear Optimization Model . . . . . . . . . . . 39
3.2.2 Mixed-Integer Linear Optimization Model
with Continuous Row Assignments . . . . . .. . . . . . . . . . . . . . . . . . . . 40
3.2.3 Proof of the Integrality of Row Assignments
at Optimality .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 42
3.2.4 Alternative Optimization Approaches for the MRFLP . . . . . . 43
3.3 Fixed-Row Multi-Row Facility Layout .. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 44
3.4 Multi-Row Facility Layout with Departments of Equal Length .. . . . 46
3.4.1 Properties of Optimal Solutions for the MREFLP . . . . . . . . . . . 46
3.4.2 Integer Linear Optimization Model . . . . . .. . . . . . . . . . . . . . . . . . . . 48
3.5 Additional Special Cases of Multi-Row Facility Layout . . . . . . . . . . . . 50
3.5.1 Corridor Allocation Problem . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 50
3.5.2 k-Corridor Allocation Problem . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 51
3.5.3 Parallel Row Ordering Problem . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 52
3.5.4 k-Parallel Row Ordering Problem . . . . . . . .. . . . . . . . . . . . . . . . . . . . 52
3.6 Semidefinite Optimization Formulations . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 53
3.7 References and Further Reading . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 54
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 55
4 Layout of a Single Floor .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 57
4.1 Nonconvex Continuous Optimization Formulation . . . . . . . . . . . . . . . . . . 57
4.2 Mixed-Integer Second-Order Conic Optimization Formulation .. . . . 60
4.3 Sequence-Pair Formulation . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 62
4.4 Two-Stage Approaches .. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 65
4.4.1 First Stage: Method Based on Nonlinear Optimization . . . . . 65
4.4.2 First Stage: Method Based on Genetic Algorithm . . . . . . . . . . . 68
4.4.3 Second Stage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 70
4.5 Flexible Bay Structure .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 70
4.6 References and Further Reading . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 73
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 73
5 Extensions and Related Problems . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 75
5.1 Quadratic Assignment Problem .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 75
5.2 Re-Layout Problems .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 76
5.3 Layout on Several Floors .. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 77
5.3.1 MISOCO Formulation of the MF-FLP . . .. . . . . . . . . . . . . . . . . . . . 77
5.3.2 Two-Stage Approach for the MF-FLP. . . .. . . . . . . . . . . . . . . . . . . . 80
5.3.3 Multi-floor Layout with Evacuation Requirements .. . . . . . . . . 82
5.4 Dynamic Facility Layout .. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 83
5.4.1 QAP Formulation.. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 84
5.4.2 MISOCO Formulation . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 85
5.5 References and Further Reading . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 86
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 87
Contents
3.2 Multi-Row Facility Layout .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 38
3.2.1 Initial Mixed-Integer Linear Optimization Model . . . . . . . . . . . 39
3.2.2 Mixed-Integer Linear Optimization Model
with Continuous Row Assignments . . . . . .. . . . . . . . . . . . . . . . . . . . 40
3.2.3 Proof of the Integrality of Row Assignments
at Optimality .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 42
3.2.4 Alternative Optimization Approaches for the MRFLP . . . . . . 43
3.3 Fixed-Row Multi-Row Facility Layout .. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 44
3.4 Multi-Row Facility Layout with Departments of Equal Length .. . . . 46
3.4.1 Properties of Optimal Solutions for the MREFLP . . . . . . . . . . . 46
3.4.2 Integer Linear Optimization Model . . . . . .. . . . . . . . . . . . . . . . . . . . 48
3.5 Additional Special Cases of Multi-Row Facility Layout . . . . . . . . . . . . 50
3.5.1 Corridor Allocation Problem . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 50
3.5.2 k-Corridor Allocation Problem . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 51
3.5.3 Parallel Row Ordering Problem . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 52
3.5.4 k-Parallel Row Ordering Problem . . . . . . . .. . . . . . . . . . . . . . . . . . . . 52
3.6 Semidefinite Optimization Formulations . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 53
3.7 References and Further Reading . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 54
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 55
4 Layout of a Single Floor .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 57
4.1 Nonconvex Continuous Optimization Formulation . . . . . . . . . . . . . . . . . . 57
4.2 Mixed-Integer Second-Order Conic Optimization Formulation .. . . . 60
4.3 Sequence-Pair Formulation . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 62
4.4 Two-Stage Approaches .. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 65
4.4.1 First Stage: Method Based on Nonlinear Optimization . . . . . 65
4.4.2 First Stage: Method Based on Genetic Algorithm . . . . . . . . . . . 68
4.4.3 Second Stage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 70
4.5 Flexible Bay Structure .. . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 70
4.6 References and Further Reading . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 73
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 73
5 Extensions and Related Problems . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 75
5.1 Quadratic Assignment Problem .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 75
5.2 Re-Layout Problems .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 76
5.3 Layout on Several Floors .. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 77
5.3.1 MISOCO Formulation of the MF-FLP . . .. . . . . . . . . . . . . . . . . . . . 77
5.3.2 Two-Stage Approach for the MF-FLP. . . .. . . . . . . . . . . . . . . . . . . . 80
5.3.3 Multi-floor Layout with Evacuation Requirements .. . . . . . . . . 82
5.4 Dynamic Facility Layout .. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 83
5.4.1 QAP Formulation.. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 84
5.4.2 MISOCO Formulation . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 85
5.5 References and Further Reading . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 86
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 87