Advanced Metering Infrastructure (AMI) initiatives are a popular tool to incorporate changes for modernizing the electricity grid, reduce peak loads, and meet energy-efficiency targets. There is the looming issue of how to communicate and handle consumer data collected by electric utilities and manage limited communication network resources. Several data relay points are required to collect data distributedly and send them through a communication backhaul. This work studies the smart meter message concatenation (SMMC) problem of how to concatenate multiple small smart metering messages arriving at data concentrator units (DCUs) in order to reduce protocol overhead and thus network utilization. This problem needs to deal with the added constraint that each originating message from its source may have its own stated deadline that must be taken into account during the concatenation process. Six heuristic algorithms are proposed and evaluated to gain a better understanding of the best data volume reduction policies that can be applied at data concentrators of smart grids.