Fitness landscapes of buffer allocation problem for production lines with unreliable machines

We study the structural properties of the buffer allocation problem from the fitness landscape perspective. We consider manufacturing flow lines with series-parallel network structure. The machines are supposed to be unreliable, their time to failure and repair time are exponentially distributed. Tentative solutions are evaluated by means of an approximate method based on the Markov models aggregation. We carry out computational experiments with local search and genetic algorithms in order to evaluate the fitness landscape properties of previously published instances and their modifications. It turns out that the so-called 'massif central' or 'big valley' structure of the fitness landscape is present but only partially: The fitness of local optima is negatively correlated with the distance to the best found solution, yet the set of local optima cannot be encompassed by a ball of relatively small size with respect to the size of solution space. Moreover, we show that in many problem instances, several clusters of local optima can be identified. The performance of genetic algorithms is discussed with respect to population clustering and the permanent usage of crossover is recommended.