An exact penalty function method for optimising QAP formulation in facility layout problem
© 2016 Informa UK Limited, trading as Taylor & Francis GroupA quadratic assignment problem (QAP), which is a combinatorial optimisation problem, is developed to model the problem of locating facilities with material flows between them. The aim of solving the QAP formulation for a facility layout...
| Main Authors: | , , , |
|---|---|
| Format: | Journal Article |
| Published: |
Taylor and Francis
2017
|
| Online Access: | http://hdl.handle.net/20.500.11937/58395 |
| _version_ | 1848760249215877120 |
|---|---|
| author | Zhou, Jingyang Love, Peter Teo, Kok Lay Luo, H. |
| author_facet | Zhou, Jingyang Love, Peter Teo, Kok Lay Luo, H. |
| author_sort | Zhou, Jingyang |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | © 2016 Informa UK Limited, trading as Taylor & Francis GroupA quadratic assignment problem (QAP), which is a combinatorial optimisation problem, is developed to model the problem of locating facilities with material flows between them. The aim of solving the QAP formulation for a facility layout problem (FLP) is to increase a system’s operating efficiency by reducing material handling costs, which can be measured by interdepartmental distances and flows. The QAP-formulated FLP can be viewed as a discrete optimisation problem, where the quadratic objective function is optimised with respect to discrete decision variables subject to linear equality constraints. The conventional approach for solving this discrete optimisation problem is to use the linearisation of the quadratic objective function whereby additional discrete variables and constraints are introduced. The adoption of the linearisation process can result in a significantly increased number of variables and constraints; solving the resulting problem can therefore be challenging. In this paper, a new approach is introduced to solve this discrete optimisation problem. First, the discrete optimisation problem is transformed into an equivalent nonlinear optimisation problem involving only continuous decision variables by introducing quadratic inequality constraints. The number of variables, however, remains the same as the original problem. Then, an exact penalty function method is applied to convert this transformed continuous optimisation problem into an unconstrained continuous optimisation problem. An improved backtracking search algorithm is then developed to solve the unconstrained optimisation problem. Numerical computation results demonstrate the effectiveness of the proposed new approach. |
| first_indexed | 2025-11-14T10:12:46Z |
| format | Journal Article |
| id | curtin-20.500.11937-58395 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T10:12:46Z |
| publishDate | 2017 |
| publisher | Taylor and Francis |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-583952017-11-24T05:47:21Z An exact penalty function method for optimising QAP formulation in facility layout problem Zhou, Jingyang Love, Peter Teo, Kok Lay Luo, H. © 2016 Informa UK Limited, trading as Taylor & Francis GroupA quadratic assignment problem (QAP), which is a combinatorial optimisation problem, is developed to model the problem of locating facilities with material flows between them. The aim of solving the QAP formulation for a facility layout problem (FLP) is to increase a system’s operating efficiency by reducing material handling costs, which can be measured by interdepartmental distances and flows. The QAP-formulated FLP can be viewed as a discrete optimisation problem, where the quadratic objective function is optimised with respect to discrete decision variables subject to linear equality constraints. The conventional approach for solving this discrete optimisation problem is to use the linearisation of the quadratic objective function whereby additional discrete variables and constraints are introduced. The adoption of the linearisation process can result in a significantly increased number of variables and constraints; solving the resulting problem can therefore be challenging. In this paper, a new approach is introduced to solve this discrete optimisation problem. First, the discrete optimisation problem is transformed into an equivalent nonlinear optimisation problem involving only continuous decision variables by introducing quadratic inequality constraints. The number of variables, however, remains the same as the original problem. Then, an exact penalty function method is applied to convert this transformed continuous optimisation problem into an unconstrained continuous optimisation problem. An improved backtracking search algorithm is then developed to solve the unconstrained optimisation problem. Numerical computation results demonstrate the effectiveness of the proposed new approach. 2017 Journal Article http://hdl.handle.net/20.500.11937/58395 10.1080/00207543.2016.1229068 Taylor and Francis restricted |
| spellingShingle | Zhou, Jingyang Love, Peter Teo, Kok Lay Luo, H. An exact penalty function method for optimising QAP formulation in facility layout problem |
| title | An exact penalty function method for optimising QAP formulation in facility layout problem |
| title_full | An exact penalty function method for optimising QAP formulation in facility layout problem |
| title_fullStr | An exact penalty function method for optimising QAP formulation in facility layout problem |
| title_full_unstemmed | An exact penalty function method for optimising QAP formulation in facility layout problem |
| title_short | An exact penalty function method for optimising QAP formulation in facility layout problem |
| title_sort | exact penalty function method for optimising qap formulation in facility layout problem |
| url | http://hdl.handle.net/20.500.11937/58395 |