Research on the Application of Time Dependent Scheduling Method and Scheduling Problem in Single Machine Task Planning

Aiming at solving the problem of mass scheduling in the single machine task planning, a time dependent scheduling method is studied in this paper. We study some inverse problems of scheduling. Firstly, we study two inverse scheduling problems on identical parallel machines: the inverse scheduling problem of the total weighted completion time problem with unit processing time on identical parallel machines; the inverse scheduling problem of the total completion time objective on identical parallel machines. We have presented the necessary and sufficient conditions for optimality of the maximum tardiness problem on single machines; also have given the mathematical formulations of the inverse scheduling and method of solving this inverse scheduling problem. For some special cases of the inverse scheduling problems, we have obtained the formulations for the optimal solutions. The experiment result shows it can improve the performance substantially.