A large number of process synthesis, design and control problems in chemical engineering can be formulated as a mixed integer nonlinear programming (MINLP) model, involving continuous variables and integer decisions. In this paper, we present an MINLP formulation for production scheduling of multi-product batch plants. The binary (0/1) integer variables of the non-convex MINLP problem make it impossible to use the general purpose algorithms for solution. In order to overcome this difficulty, a semi-heuristic algorithm for production scheduling was developed. Using this approach, the non-convex MINLP problem is first considered as an MILP problem without dividing the orders. Thus, the order that causes prolonged delivery time can be identified. Constraints for this order are then relaxed and MILP problem is re-solved using the new constraints. Having reached the new schedule, the quantitative distribution of the specific order to different units can be determined by solving the LP problem that does not contain integer variables since allocation of the orders to the units and processing order are known. The results obtained with some example problems indicate improvements over previous schedules and therefore, give promise that the suggested strategy might be used in moderately-sized industrial applications.