A novel approach is presented for the solution of production planning problems for multiproduct processes. A mixed-integer programming (MIP) scheduling model is analyzed off-line to obtain a convex approximation of feasible production levels and a convex underestimation of total production cost as a function of production levels. The two approximating functions are expressed via linear inequalities that involve only planning variables yet provide all the relevant scheduling information necessary to solve the planning problem with high quality. A rolling horizon algorithm is also presented for generation (if necessary) of detailed schedules. (c) 2007 American Institute of Chemical Engineers.