We propose an ATS, for a class of optimal allocation problems, that uses various types of memory to make the search effective. To improve efficiency, our tabu search (TS) uses a combination of objects, rather than moves, as memory elements, simplifying search constraints and improving search efficiency. The ATS is applied to optimal allocation of irregular shapes on a sheet to minimize waste. The effectiveness of the proposed method is compared to other metaheuristics in a simulation whose results show the ATS to be superior.