Dynamic hierarchical packing of wireless switches using a seed, repair and replace genetic algorithm

Suppose that items of equipment are to be added to a supply station (e.g., new switch modules are to be added to a telecommunications switch) over time to meet growing demand requirements. Both supply and demand have multiple components: an item of equipment supplies different amounts of several resources, and demand may be expressed in terms of the vector of resources required. There are several different types of equipment to choose among, each type supplying known amounts of each resource per unit of equipment. The supply station is organized into bays, shelves, or other capacitated ‘containers’ so that when the cumulative amount of equipment added exceeds the holding capacity of the installed containers, new containers must be added, creating a relatively large jump in cumulative costs. Thus, it is desirable to sequentially ‘pack’ items of equipment into the available containers, by choosing which types of equipment to install when, so as to minimize the total cost of covering demand in each period. We discuss an instance of this problem arising from wireless telephony and describe the performance of a conventional branch-and-bound optimization algorithm for solving it. The branch-and-bound approach works well on small instances of the problem, and has been used successfully in practical planning. However, it can take CPU-days to run, thus preventing development of a useful interactive planning tool. Therefore, we introduce a novel ‘seed, repair, and replace’ genetic algorithm (SRR-GA) for solving dynamic packing problems of this type. We contrast its performance with the branch-and-bound algorithm’s on both hand-generated and randomly created dynamic packing problems, finding that the SRR-GA is two to three orders of magnitude faster and produces solutions of equal or better quality on practical problems. Variations of the dynamic packing problem and of the SRR-GA for solving it are mentioned, and the paper concludes by suggesting other potential applications of the SRR-GA to hard combinatorial optimization problems.