Heuristic-based approach for an industrial three-dimensional layout problem

Abstract

In this paper, we consider a particular three-dimensional layout problem in a steel sheet manufacturing workshop. The products are laid in a machine according to packs and stacks. Constraints determine if a product or a pack can be laid above another product or another pack. For this NP-complete problem, we propose two kinds of method: heuristic method (based on enumeration) and combination between heuristic and metaheuristic. The proposed methods are validated and compared on real instances. The results are of good quality.

Keywords:

• Three-dimensional layout
• Industrial problem
• Metaheuristics
• Heuristic

Acknowledgements

The authors would like to thank the two anonymous referees for their helpful comments that led to this final version.

Sylvie Norre is Associate Professor in computer science at the University of Clermont-Ferrand. She teaches Operational Research in the Technological Institute of Montluçon. She is affiliated with the CNRS, UMR 6158, LIMOS laboratory. She is a member of the Modelling and Decision Aid team. Her research interests are in combinatorial optimization, especially planning and scheduling problems: task assignment in multiprocessor architecture, hoist scheduling problem (HSP), stochastic flow-shop scheduling problem, hybrid Flow-shop scheduling problem, bin packing problem, line balancing problem …

Nathalie Grangeon is Associate Professor at the University of Clermont-Ferrand. She teaches computer science in the Technological Institute of Montluçon. She is affiliated with the CNRS, UMR 6158, LIMOS laboratory. She is a member of the Modelling and Decision Aid team. Her research interests are in combinatorial optimization, especially planning and scheduling problems: stochastic flow-shop scheduling problem, hybrid flow-shop scheduling problem, bin packing problem, line balancing problem …

Nikolay Tchernev is Associate Professor in computer science at the Auvergne University of clermont-Ferrand. He teaches information system, enterprise engineering, business process planning and supply chain management in the Business school of Management. He is affiliated with the CNRS, UMR 6158, LIMOS laboratory. He is a member of the Modelling and Decision Aid team. His research interests are in techniques and tools for industrial engineering and production management modelling and simulation, planning and scheduling of manufacturing and logistics systems: hybrid flow-shop scheduling problem, job shop with time lags scheduling problem, supply chain planning and supply chain performance evaluation …