Design of unidirectional cyclic layouts

This work is concerned with the unidirectional cyclic layout problem, which is known to be NP-complete. The type of problem arises, for example, in the determination of workstation locations around a closed loop conveyor system, in the allocation of cutting tools on the sites around a turret, in the positioning of stations around a unidirectional single loop AGV path. Although it can be formulated as a Quadratic Assignment Problem, in general there are two special cases satisfying additional assumptions. In the Balanced Unidirectional Cyclic Layout problem, the material flow is conserved at every workstation. In the Equidistant Unidirectional Cyclic Layout Problem, distances between circular candidate locations are all equal. It is known that both problems are equivalent, which makes any valid formulation of the balanced flow problem also valid for the equidistant problem and vice versa. We first analyse and show new features of the existing formulations. Then we discuss and propose new heuristics using ideas originally introduced for two well-known combinatorial optimization problems: the Asymmetric Travelling Salesman Problem and the Linear Ordering Problem. Based on the computational tests we can say they are both accurate and efficient.