Study On Task Sequencing And Scheduling Problems With Time D-subsets

Task sequencing and scheduling problems of single machine and multi-machine are special and basic cases of shop scheduling problem. They are studied with Dioid algebra. in the thesis.Firstly, on basis of task sequence function and time D-subset, task scheduling models of single machine and multi-machine are built in Max-algebra to describe the relationship of on-stream time, completion time, arrival time and process time. For multi-machine, task allocating and sequencing problem are figured in task sequence function. Furthermore, optimal programming models are built for task sequencing and scheduling of single and multi machine.Secondly, some heuristic algorithms are studied respectively for optimal task sequencing and scheduling problem of single machine and multi-machine. The heuristic dynamic programming algorithm with k-means process time and the multi-rules hybrid heuristic algorithm are proposed for single machine. These algorithms approach the mechanism of the problem and thereby have the merit of SPT, ERD and ECD rules. Meanwhile, a preferable task sequencing and scheduling of single machine can be obtained with these algorithms. And for multi-machine, the dynamic programming heuristic algorithm under parallel machine is also given.Finally, by comparative analysis, the validity of the heuristic algorithm proposed in the paper is demonstrated with some examples. And the disadvantage and advantage of corresponding algorithms are pointed out.