The maintenance of cigarette formulations directly affects product flavor stability and continuous manufacturing. However, traditional manual maintenance, which relies heavily on experience, struggles to address the complex constraints arising from fluctuations in raw material inventories and quality degradation during storage. We formulate the inventory-constrained cigarette formulation maintenance problem as a mixed-integer program built on two quality metrics: the Formulation Reliability Index and the Formulation Maturation Index. To effectively solve this model, we propose a Mutual Information-based Adaptive Large Neighborhood Search algorithm that integrates the historical co-occurrence information of different formulations. We design multiple removal and insertion operators and incorporate a simulated annealing mechanism to enhance the global search capabilities of the algorithm. Multi-scenario industrial tests show that our approach significantly improves objective values under inventory limits while remaining computationally efficient.