This work focuses on the scheduling of refinery operations from crude oil processing to the blending and dispatch of finished products. A new algorithm for Lagrangian decomposition (LD) is proposed and applied to realistic large scale refinery scheduling problem to evaluate its efficiency. A novel strategy is presented to formulate restricted relaxed sub-problems based on the solution of the Lagrangian relaxed sub-problems that take into consideration the continuous process characteristic of the refinery. This new algorithm, referred to as restricted Lagrangian decomposition algorithm, the best lower bound is obtained amongst the restricted-relaxed sub-problems and relaxed sub-problems in each iteration. The goal of the decomposition is to produce better solutions for those integrated scheduling problems that cannot be solved in reasonable computation times. The application of the proposed algorithm results in substantial reduction in CPU solution time, duality gap, and the total number of iterations compared to classical LD. (C) 2015 Elsevier Ltd. All rights reserved.