Towards optimal formwork pairing on construction sites

Thierry Benoist

RAIRO - Operations Research (2007)

  • Volume: 41, Issue: 4, page 381-398
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Benoist, Thierry. "Towards optimal formwork pairing on construction sites." RAIRO - Operations Research 41.4 (2007): 381-398. <http://eudml.org/doc/250104>.

@article{Benoist2007,
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. },
author = {Benoist, Thierry},
journal = {RAIRO - Operations Research},
keywords = {Pairing; Russian dolls; tabu; fixed-charge multi-commodity flow; pairing; fixed-charge multi-commodity flow},
language = {eng},
month = {10},
number = {4},
pages = {381-398},
publisher = {EDP Sciences},
title = {Towards optimal formwork pairing on construction sites},
url = {http://eudml.org/doc/250104},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Benoist, Thierry
TI - Towards optimal formwork pairing on construction sites
JO - RAIRO - Operations Research
DA - 2007/10//
PB - EDP Sciences
VL - 41
IS - 4
SP - 381
EP - 398
AB - 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.
LA - eng
KW - Pairing; Russian dolls; tabu; fixed-charge multi-commodity flow; pairing; fixed-charge multi-commodity flow
UR - http://eudml.org/doc/250104
ER -

References

top
  1. J. Agnèse, N. Bataille, E. Bensana, D. Blumstein and G. Verfaillie, Exact and Approximate methods for the Daily Management of an Earth Observation Satellite, in Proc. of the 5th ESA Workshop on Artificial Intelligence and Knowledge Based Systems for Space (1995).  
  2. T. Benoist and F. Chauvet, Complexity of some FPP related Problems, E-lab Technical Report (2001).  
  3. Y. Caseau and F. Laburthe, Improved CLP Scheduling with Task Intervals, in Proc. of the 11th International Conference on Logic Programming, MIT Press (1994).  
  4. M.R. Garey and D.S. Johnson, Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput.4 (1975), 397–411.  
  5. M.R. Garey and D.S. Johnson, Computers and intractability, a guide to the theory of NP-completeness. W.H. Freeman, New York (1979).  
  6. Z. Gu, G.L. Nemhauser and M.W.P. Savelsbergh, Lifted flow cover inequalities for mixed 0-1 integer programs. Math. Program.85 (1999) 439-467.  
  7. G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization. Wiley Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons (1988).  
  8. G. Verfaillie, M. Lemaître and T. Schiex, Russian Doll Search for Solving Constraint Optimization Problems, in Proc. of AAAI-96, Portland, OR, (1996) 181–187.  
  9. M. Vasquez, A. Dupont and D. Habet. Consistency checking within local search applied to the frequency assignement with polarization problem. RAIRO Oper. Res.37 (2003) 311-323.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.