In an environment of global competition, the success of a manufacturing corporation is directly related to how it plans and executes production in particular as well as to the optimization level of its process in general. This paper proposes a production planning algorithm for the Multi-Level, multi-item Capacitated Lot Sizing Problem (MLCLSP) in supply chain network considering back-order. MLCLSP corresponds to a mixed integer programming (MIP) problem and is NP-hard. Therefore, this paper proposes an effective algorithm, GRHS (GRASP-based Rolling Horizon Search) that solves this problem within reasonable computational time and evaluates its performance under a variety of problem scenarios.