Date of Graduation


Document Type



Businesses, including manufacturing companies, must reduce cost to survive in today’s economy. During the last several decades, to reduce cost, many companies began to focus on labor optimization and/or increasing productivity. This may require an increase in investment cost (e.g., equipment costs). Among the consequences of these policies is a significant reduction in direct labor cost. The necessity to reduce direct labor cost has made material handling cost more important than ever. Material handling cost reductions can be obtained by designing efficient layouts. Efficient layouts are obtained by solving machine and facility layout problems effectively. Commonly, facility and machine layout problems assume that product flows are either known or estimated before hand, and that the layout solution has enough capacity to satisfy all product demands. When product demands exceed capacities of planned production systems, it is important to select a feasible product mix that maximizes company profits. In addition, when identical machines are considered, determining material flows as well as the layout always lead to better solutions. Integrating these issues leads to the generalized machine layout problem (GMALP). 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 maximized. Moreover, the GMALP integrates the quadratic assignment problem (QAP) and the maximum profit multicommodity flow problem (MPMFP). Therefore, the GMALP is a computationally intractable problem. Consequently, a mixed integer nonlinear programming model was developed and used to solve small problem instances. In addition, construction algorithms and metaheuristics (i.e., tabu search and memetic algorithms) were developed for solving large GMALP instances in acceptable computation times. Also, a test dataset was used to evaluate the performances of the heuristics presented. Finally, the memetic algorithms performed better than the tabu search heuristics for the dataset.