Due to production customization and diversification, many manufacturing companies face greater challenges to cope with uncertainties related to material supply, market demands and increased cost. The purpose of this study is to optimize the production process in a multi-product heat treatment shop to reduce production cost. We consider a multi-item multi-level production planning and scheduling problem in this research with production cost related to the waiting time of the components to be processed. A non-linear integer programming model is developed to describe the considered problem. After linearization, the model is solved to optimality using IBM® ILOG® CPLEX® Optimization Studio. We also propose a heuristic solution method to solve the considered problem for fast solutions of much larger problem sizes. Computational results of numerical examples indicate the mathematical model generates optimal results in capturing detailed problem features such as larger product variety which can be missed in using the heuristic method. The results also show that the developed mathematical model can be used to solving various production planning and scheduling problems with practical considerations such as timerelated manufacturing cost functions.