Faculty & Staff Scholarship
2010
The Generalised Machine Layout Problem
Juan Jaramillo
Farmingdale State University of New York,
Alan McKendall
West Virginia University,
Follow this and additional works at: https://researchrepository.wvu.edu/faculty_publications
Part of the Operations Research, Systems Engineering and Industrial Engineering Commons
Digital Commons Citation
Jaramillo, Juan and McKendall, Alan, "The Generalised Machine Layout Problem" (2010). Faculty & Staff
Scholarship. 3045.
https://researchrepository.wvu.edu/faculty_publications/3045
This Article is brought to you for free and open access by The Research Repository @ WVU. It has been accepted
for inclusion in Faculty & Staff Scholarship by an authorized administrator of The Research Repository @ WVU. For
more information, please contact .
, International Journal of Production Research
ISSN: 0020-7543 (Print) 1366-588X (Online) Journal homepage: https://www.tandfonline.com/loi/tprs20
The generalised machine layout problem
J.R. Jaramillo & A.R. McKendall Jr
To cite this article: J.R. Jaramillo & A.R. McKendall Jr (2010) The generalised machine
layout problem, International Journal of Production Research, 48:16, 4845-4859, DOI:
10.1080/00207540903117840
To link to this article: https://doi.org/10.1080/00207540903117840
Published online: 12 Aug 2009.
Submit your article to this journal
Article views: 238
View related articles
Citing articles: 4 View citing articles
Full Terms & Conditions of access and use can be found at
https://www.tandfonline.com/action/journalInformation?journalCode=tprs20
, International Journal of Production Research
Vol. 48, No. 16, 15 August 2010, 4845–4859
The generalised machine layout problem
J.R. Jaramilloa* and A.R. McKendall Jrb
a
Department of Business Administration, Albany State University, 504 College Drive,
Albany, GA 31705, USA; bDepartment of Industrial and Management
Systems Engineering, West Virginia University, 325A Mineral Resources Building,
Morgantown, WV 26506, USA
(Received 18 December 2008; final version received 10 June 2009)
The Generalised MAchine Layout Problem (GMALP) is a generalisation of the
integrated machine and layout problem, which is an extension of the machine
layout problem. More specifically, the GMALP is the designing of a facility
layout by defining the product mix, selecting the number of machines to be used,
assigning these machines to the plant floor, and assigning products to machines
such that total profit is maximised. Moreover, the GMALP integrates the
quadratic assignment problem with a multicommodity flow problem. Therefore,
the GMALP is a computationally intractable problem. Consequently, a mixed-
integer nonlinear programming model was developed and used to solve small
problem instances. Also, two simple construction algorithms and a tabu search
(TS) heuristic were developed for solving large GMALP instances in acceptable
computation times. In addition, a test dataset was used to evaluate the
performances of the TS heuristic using the different construction algorithms.
The results show that the TS heuristic perform slightly better with the second
construction algorithm.
Keywords: optimisation; operational research; meta-heuristics; logistics; facility
layout; supply chain management
1. Introduction
The problem of assigning machines to locations in a facility (i.e. a manufacturing plant)
such that material handling cost (MHC) is minimised is known as the machine layout
problem (MLP). Moreover, the MLP commonly assumes that flow amounts between
machines are known beforehand, that the plant floor is represented as an array of equal
size grid units, and that the plant floor has enough capacity to allocate all machines.
Therefore, the MLP can be modeled as a Quadratic Assignment Problem (QAP). The QAP
was introduced by Koopmans and Beckmann (1957), and was proven NP Hard by Sahni
and Gonzales (1976). For an extensive review of solution techniques for the QAP, refer to
Burkard et al. (1998) and Loiola et al. (2007).
An extended version of the MLP includes machine replicas (i.e. more than one machine
of the same type). Considering machine replicas implies that flows between machines
assigned to locations become part of the problem output, since static flows restrict the
problem too much. Notice that the extended MLP can be modeled as a combination of the
QAP and a multicommodity flow problem (MFP). As a consequence, MLP with machine
*Corresponding author. Email:
ISSN 0020–7543 print/ISSN 1366–588X online
ß 2010 Taylor & Francis
DOI: 10.1080/00207540903117840
http://www.informaworld.com
2010
The Generalised Machine Layout Problem
Juan Jaramillo
Farmingdale State University of New York,
Alan McKendall
West Virginia University,
Follow this and additional works at: https://researchrepository.wvu.edu/faculty_publications
Part of the Operations Research, Systems Engineering and Industrial Engineering Commons
Digital Commons Citation
Jaramillo, Juan and McKendall, Alan, "The Generalised Machine Layout Problem" (2010). Faculty & Staff
Scholarship. 3045.
https://researchrepository.wvu.edu/faculty_publications/3045
This Article is brought to you for free and open access by The Research Repository @ WVU. It has been accepted
for inclusion in Faculty & Staff Scholarship by an authorized administrator of The Research Repository @ WVU. For
more information, please contact .
, International Journal of Production Research
ISSN: 0020-7543 (Print) 1366-588X (Online) Journal homepage: https://www.tandfonline.com/loi/tprs20
The generalised machine layout problem
J.R. Jaramillo & A.R. McKendall Jr
To cite this article: J.R. Jaramillo & A.R. McKendall Jr (2010) The generalised machine
layout problem, International Journal of Production Research, 48:16, 4845-4859, DOI:
10.1080/00207540903117840
To link to this article: https://doi.org/10.1080/00207540903117840
Published online: 12 Aug 2009.
Submit your article to this journal
Article views: 238
View related articles
Citing articles: 4 View citing articles
Full Terms & Conditions of access and use can be found at
https://www.tandfonline.com/action/journalInformation?journalCode=tprs20
, International Journal of Production Research
Vol. 48, No. 16, 15 August 2010, 4845–4859
The generalised machine layout problem
J.R. Jaramilloa* and A.R. McKendall Jrb
a
Department of Business Administration, Albany State University, 504 College Drive,
Albany, GA 31705, USA; bDepartment of Industrial and Management
Systems Engineering, West Virginia University, 325A Mineral Resources Building,
Morgantown, WV 26506, USA
(Received 18 December 2008; final version received 10 June 2009)
The Generalised MAchine Layout Problem (GMALP) is a generalisation of the
integrated machine and layout problem, which is an extension of the machine
layout problem. More specifically, the GMALP is the designing of a facility
layout by defining the product mix, selecting the number of machines to be used,
assigning these machines to the plant floor, and assigning products to machines
such that total profit is maximised. Moreover, the GMALP integrates the
quadratic assignment problem with a multicommodity flow problem. Therefore,
the GMALP is a computationally intractable problem. Consequently, a mixed-
integer nonlinear programming model was developed and used to solve small
problem instances. Also, two simple construction algorithms and a tabu search
(TS) heuristic were developed for solving large GMALP instances in acceptable
computation times. In addition, a test dataset was used to evaluate the
performances of the TS heuristic using the different construction algorithms.
The results show that the TS heuristic perform slightly better with the second
construction algorithm.
Keywords: optimisation; operational research; meta-heuristics; logistics; facility
layout; supply chain management
1. Introduction
The problem of assigning machines to locations in a facility (i.e. a manufacturing plant)
such that material handling cost (MHC) is minimised is known as the machine layout
problem (MLP). Moreover, the MLP commonly assumes that flow amounts between
machines are known beforehand, that the plant floor is represented as an array of equal
size grid units, and that the plant floor has enough capacity to allocate all machines.
Therefore, the MLP can be modeled as a Quadratic Assignment Problem (QAP). The QAP
was introduced by Koopmans and Beckmann (1957), and was proven NP Hard by Sahni
and Gonzales (1976). For an extensive review of solution techniques for the QAP, refer to
Burkard et al. (1998) and Loiola et al. (2007).
An extended version of the MLP includes machine replicas (i.e. more than one machine
of the same type). Considering machine replicas implies that flows between machines
assigned to locations become part of the problem output, since static flows restrict the
problem too much. Notice that the extended MLP can be modeled as a combination of the
QAP and a multicommodity flow problem (MFP). As a consequence, MLP with machine
*Corresponding author. Email:
ISSN 0020–7543 print/ISSN 1366–588X online
ß 2010 Taylor & Francis
DOI: 10.1080/00207540903117840
http://www.informaworld.com
