Author(s)

Y. Langer, M. Bay, Y. Crama, F. Bair, J. D. Caprace & Ph. Rigo

Abstract

In this paper, we present a scheduling problem that arises in factories producing large building blocks (in our case, a shipyard workshop producing prefabricated keel elements). The factory is divided into several equally size areas. The blocks produced in the factory are very large, and, once a building block is placed in the factory, it cannot be moved until all processes on the building block are finished. The blocks cannot overlap. The objective is to maximize the number of building blocks produced in the factory during a certain time window. To solve this problem, we propose heuristics inspired by techniques initially developed for the three-dimensional bin packing problem, since constraints for both problems are quite similar. Starting from an unfeasible solution, where blocks can overlap, a Guided Local Search (GLS) heuristic is used to minimize the sum of total overlap. If a solution with zero overlap is found, then it is a feasible solution; otherwise the block with the biggest overlap is removed and the procedure is restarted. The GLS algorithm has been improved by Fast Local Search (FST) techniques in order to speed up convergence to a local minimum. Additionally, neighborhoods are restricted to their smallest size so as to allow their evaluation in polynomial-time. In a last step, we explain the additional real-life issues arising in the industrial application and how firm-specific constraints can be conveniently considered by the model. Keywords: scheduling, simulation, surface utilization, Guided Local Search, three-dimensional bin-packing, building blocks, shipyard.

Keywords

scheduling, simulation, surface utilization, Guided Local Search, three-dimensional bin-packing, building blocks, shipyard.