David and the vegetable factory

Abstract

In this thesis a two-stage model is proposed, combining the idea of a two-stage model from Anjos and Vieira [1] with a gradient descent approach, much like proposed in Sikaroudi and Shahanaghi [42], in order to solve the facility layout problem for problems consisting of 8 and 12 departments . This method was chosen after analyzing the criteria for a vegetable processing factory and combining this with a literature research to previous methods applied to solve these "facility layout problems". The gradient descent approach uses the partial derivatives of a multi-variable objective, the flow-cost, in order to get a vector which is the direction of greatest descent. Computing this vector for all departments and then moving them creates an iterative improving loop. In addition to the gradient descent approach a swapping procedure and a shooting procedure is introduced in order to reduce the effect of random starting position. From the result of the first-stage model, relative location constraints are extracted to be used in the second-stage model, a linear constraint programming solver capable of running optimizations by google or-tools [36], to greatly reduce the solution space. The proposed method was tested on two toy-problems from Tam and Li [44] and compared to results existing in literature. Additionally, the effect of including a first-stage model was tested as well. When looking directly at the results, the proposed method is consistent and shows good results. Especially the inclusion of the first-stage model helps finding better solutions. Compared to other results found in the literature, the method shows slightly less good results based purely on the objective value. However, the final layouts found in this thesis are more compact.