In this paper a novel optimal scheduling model and its algorithm are developed for task scheduling problems. A novel annealing-inspired genetic algorithm is applied to solve the scheduling model. The effectiveness of the algorithm is shown for a number of test problems and performance comparisons with the genetic algorithm, simulated annealing are also discussed.