no. 4
Towards optimal formwork pairing on construction sites
RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 4, pp. 381-398.

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.

DOI : 10.1051/ro:2007035
Classification : 90B90
Mots clés : pairing, russian dolls, tabu, fixed-charge multi-commodity flow 
@article{RO_2007__41_4_381_0,
     author = {Benoist, Thierry},
     title = {Towards optimal formwork pairing on construction sites},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {381--398},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {4},
     year = {2007},
     doi = {10.1051/ro:2007035},
     mrnumber = {2361292},
     zbl = {1165.90556},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro:2007035/}
}
TY  - JOUR
AU  - Benoist, Thierry
TI  - Towards optimal formwork pairing on construction sites
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2007
SP  - 381
EP  - 398
VL  - 41
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2007035/
DO  - 10.1051/ro:2007035
LA  - en
ID  - RO_2007__41_4_381_0
ER  - 
%0 Journal Article
%A Benoist, Thierry
%T Towards optimal formwork pairing on construction sites
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2007
%P 381-398
%V 41
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro:2007035/
%R 10.1051/ro:2007035
%G en
%F RO_2007__41_4_381_0
Benoist, Thierry. Towards optimal formwork pairing on construction sites. RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 4, pp. 381-398. doi : 10.1051/ro:2007035. http://www.numdam.org/articles/10.1051/ro:2007035/

[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. | Zbl

[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). | MR | Zbl

[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. | MR | Zbl

[7] G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization. Wiley Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons (1988). | MR | Zbl

[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. | Numdam | MR | Zbl

Cité par Sources :