This paper proposes a symbolic deduction based scheduling algorithm for the problem of complex production scheduling under time uncertainty. In the proposed algorithm, time uncertainty is regarded as symbolic data and an uncertain interval based symbolic deduction method is proposed to deal with these data. Then, genetic algorithm is combined with the uncertain interval based symbolic deduction method and a scheduling method including scheduling plan and dispatching rules is proposed to solve the above problem. Numerical computational results show that the proposed scheduling algorithm is effective for the complex production scheduling problems under time uncertainty.