In order to reduce the time and cost of production, and in agreement with the view of "design for production, we develop a model to simulate the planning problems that appear in workshop production blocks.
The blocks are very large and therefore, once placed on the area of manufacturing, they can not be moved until their full completion. Each block is characterized quantitatively and geometrically (length, width, height, weight, etc..) And has time parameters (time of manufacture, date of delivery to the later date of commencement at the earliest).
The goal is to provide a tool for decision on scheduling the workshop for a predetermined time horizon, and within certain constraints (overlapping time windows, especially based positioning tools available in the workshop, ...). The space for the blocks is divided into finite areas of identical size, and our research focuses on methods that determine the layout of blocks (position, orientation, commencement date) to produce to the greatest number. Beyond the quality of response in terms of number of blocks, we are focusing our efforts to provide a tool for the pragmatic decision, in agreement with the habits and customs of the schedulers of this type of workshop and provides solutions in a reasonable time.
The techniques used are derived from research on a similar problem, called "Three Dimensional Bin Packing Problem" (3D-BPP), within which to "store" boxes in the smallest number of containers (Both problems are in fact similar on many points). In particular, we use to solve this problem a heuristic local search called "Guided Local Search (GLS)" we have coupled with another technique called "Fast Local Search.
The figure above illustrates briefly the approach used: from a random starting position, where the blocks have a satisfactory position individually but they may overlap one another, the algorithm determines the "movements" that improve the solution, since they reduce the amount of overlap. The procedure stops after finding a solution containing no more no overlap. A complementary step allows then to increment the number of blocks available in the shop to finally find the schedule that will generate the maximum block.
This study led to the implementation of a software called OptiView
(COMPIT''05 - Yves Langer, Maud Bay, Yves Crama, Frédéric Bair, Jean-David Caprace, Philippe Rigo, 2005)