In this paper, we address the general multiperiod production/inventory problem with nonstationary stochastic demand and supplier lead time under service-level constraints. A replenishment cycle policy is modeled. We propose two hybrid algorithms that blend constraint programming and local search for computing near-optimal policy parameters. Both algorithms rely on a coordinate descent local search strategy; what differs is the way this strategy interacts with the constraint programming solver. These two heuristics are first, compared for small instances against an existing optimal solution method. Second, they are tested and compared with each other in terms of solution quality and run time on a set of larger instances that are intractable for the exact approach. Our numerical experiments show the effectiveness of our methods.