Production planning problems are generally modeled as mixed integer programming problems; and solved through heuristic algorithms, because of their innate high computational complexity. In this paper, a mixed integer nonlinear programming (MINLP) model is designed for multi-item, multi-period production planning to replenish orders of the buyer and minimizing the supplier’s costs. It is supposed that the order quantity is constant, and ordering occurs at once. This model has been developed according to the realistic assumptions of SAPCO Company, which is a major supplier of automotive parts in Iran, and one of its partner companies. In addition, an efficient heuristic algorithm based on A* search has been proposed to solve this mathematical model. The proposed search algorithm does not need an initial solution; also, it can overcome the memory overhead through bounding the stored states in its open-list. Actually, in spite of the simplicity of the proposed algorithm, which is established based on the simple inventory management equations; it is able to generate efficiently optimal or near-optimal solutions in comparison with an exact solution method, a greedy search algorithm, and simulated annealing algorithm as a metaheuristic algorithm.