Research On Hybrid Parallel Machine Scheduling Problem With Maintenance And Preemptive Jobs

Scheduling with maintenance has become a research hotspot in the field of combinatorial optimization. This thesis considers a hybrid parallel machine scheduling problem where the processing times of all the jobs are equal, jobs can be preempted and the number of jobs is not greater than that of the machines, some machines need periodic maintenance while the rest of the machines do not need any maintenance. The objective is to schedule all jobs to the machines such that makespan is minimized.This thesis studies this scheduling problem theoretically. Firstly, it analyzes some special cases and propose a polynomial-time optimal algorithm for each of the special cases. Then, for the general case, it proposes a lower bound of the optimal makespan based on the establishment of a affusion model. Thereafter, for each of the two cases of the water level of the general case, it proposes a polynomial-time algorithm with an objective value equals to the lower bound, and therefore obtaining a polynomial-time optimal algorithm for the general case of the scheduling problem. Meanwhile, in order to make the reader better understand the ideas of the thesis and the proposed algorithms, a lot of examples with analyses and validations are provided.