RAIRO - Operations Research

Table of Contents - October 2007 - Volume 41, Issue 04  

Research Article

Towards optimal formwork pairing on construction sites

Thierry Benoist

Bouygues e-lab, 32 av Hoche, 75008 Paris, France; tbenoist@bouygues.com

Abstract

Minimizing shutterings assembling time on construction sites can yield significant savings in labor costs and crane moves. It requires solving a pairing problem that optimizes the ability for the crane to move chains of shutterings as a whole when they can be later reused together to frame another wall of the site. In this paper, we show that this problem is NP-hard in the strong sense as well as both its multiflow and ordering aspects. We also introduce a linear relaxation that computes reasonably good lower bounds of the objective, and describe a Tabu Search based on pairings insertion and ejection that builds promising solutions.

(Received January 1 2002)

(Accepted February 6 2007)

(Online publication October 11 2007)

Key Words:

  • Pairing;
  • Russian dolls;
  • tabu;
  • fixed-charge multi-commodity flow

Mathematics Subject Classification:

  • 90B90