Abstract: The Olympics scheduling problem is modeled as constraint satisfaction problem, which is transformed into a constrained optimization problem by softening the time constraints of the final matches. A decomposition methodology based on Lagrangian relaxation is presented for the constrained optimization problem. For the dual problem optimization the sub-gradient projection method with variable diameter is studied. The method can converge to the globally optimal solutions and the efficiency is given. Numerical results show that the methods are efficient and the phase transition domain can be recognized by the algorithm.