This paper proposes a new generation scheduling algorithm which can consider total quantity of contamination and energy limits based on Lagrangian Relaxation. First, we formulate a Lagrangian function which consider quantity of contamination including substitution of fuel, and quantity of fuel. Second, we developed Multi-state S.U.D.P. which can treat multiple fuels. Third, we propose an effective generation scheduling algorithm including Multi-state S.U.D.P.. As a results, unit commitment and generating power can be obtained to meet the environmental and fuel constraints with fuel substitution. By applying it to the test system, effectiveness of the method is verified.