Inventory control of deteriorating items constitutes a large part of the world’s economy and covers various goods including any commodity, which loses its worth over time because of deterioration and/or obsolescence. Vendor managed inventory (VMI), which is a win-win strategy for both suppliers and buyers gains better results than traditional supply chain. In this research, we study an economic order quantity (EOQ) with shortage in form of partial backorder under VMI policy. The model is concerned with multi-item subject to multi-constraint including storage space, time period and budget constraints. Two metaheuristic algorithms, namely Simulated Annealing and Tabu Search, are used to find a near optimal solution for the proposed fuzzy nonlinear integer-programming problem with the objective of minimizing the total cost of the supply chain. Furthermore, the sensitivity analysis of the metaheuristic parameters is performed and five numerical examples containing different numbers of items are conducted in order to evaluate the performance of the algorithms.