Name: GILDASIO LECCHI CRAVO
Publication date: 03/08/2021
Advisor:
Name |
Role |
|---|---|
| ANDRÉ RENATO SALES AMARAL | Advisor * |
Examining board:
| Name |
Role |
|---|---|
| ANDRÉ RENATO SALES AMARAL | Advisor * |
| LUCIANO LESSA LORENZONI | External Examiner * |
| MARIA CLAUDIA SILVA BOERES | Internal Examiner * |
| MARIO MESTRIA | External Examiner * |
Summary: The study of layout of facilities aims to determine the best use of available space, resulting in
more effective manufacturing processes in the context of industry. This thesis addresses four
facility layout problems, categorized as row layout, in which facilities must be arranged in one
or two straight lines, respecting some allocation constraints. Initially, the problem of single-row
facility layout (SRFLP) is addressed, which consists of arranging facilities along a straight line,
in order to minimize the weighted sum of the distances between all pairs of facilities. The other
three problems addressed in this study are SRFLP extensions, in which the facilities are
arranged in two lines, namely: the double-row layout problem (DRLP), the parallel row
ordering problem (PROP) and the bi-objective corridor allocation problem (bCAP). An
algorithm called GRASP-F is proposed for SRFLP. The computational experiments show the
efficiency of the method by improving the known-values for 29 out of 93 instances in the
literature with up to 1000 facilities. To date, this is the second work to consider problems of
this magnitude. For DRLP, a purely heuristic approach, called PSO-DRLP, is proposed based
on the Particle Swarm Optimization meta-heuristic. The PSO-DRLP presented values equal to
or better than the known-values for 35 of 51 instances in the literature, and, for the remaining
16, the values found are very close to the best-known values. The solution algorithm for PROP,
called AILS, is based on the ILS meta-heuristic, but unlike the standard, two phases with
different intensification and diversification characteristics were used, in addition to using
techniques to accelerate the calculation of the gain in the objective function in the neighborhood
move used in the local search. The results found improved 49 out of 100 instances with previous
known results and for the remaining 51 instances the best-known results were achieved. In
addition to these tests, experiments were carried out using 6 instances with up to 300 facilities,
unprecedented in the context of PROP. For bCAP, an algorithm similar to AILS-PROP was
proposed, also in two phases and with techniques to accelerate the calculation of the gain in the
objective function in the neighborhood movements used in the local search, having obtained
excellent results for 76 tested instances. In general, the proposed solutions for the four problems
can be considered excellent alternatives to solve layout problems in single and double lines,
being possible to obtain high quality results for large problems in low computational times.
Keywords: Facility Layout, SRFLP, DRLP, PROP, bCAP, Meta-heuristics.
