The rectilinear block packing problem is a problem of packing a set of rectilinear blocks into a larger rectangular container, where a rectilinear block is a polygonal block whose interior angle is either 90 degrees or 270 degrees. There exist many applications of this problem, such as VLSI design, timber/glass cutting, and newspaper layout. In this paper, we design efficient implementations of two construction heuristics for rectilinear block packing. The proposed algorithms are tested On a series of instances, which are generated from nine benchmark instances. The computational results show that the proposed algorithms are especially efficient for large instances with repeated shapes. (C) 2014 Elsevier Ltd. All rights reserved.