Study On Scheduling Algorithm With Deteriorating Jobs And Multiple Maintenance Activities

Scheduling problems has become an important part of computer science over the years. The analysis of computational complexity, the choice of CPU scheduling algorithm, the resource scheduling and task scheduling in cloud computing and grid computing are all hot topics. All of them are closely tied to the traditional scheduling problems.Communication between different disciplines is constant with the development of scheduling. There is more and more contact between different areas in scheduling theory. Now, more and more scholars consider classical scheduling theory and the application of computer together. They try to use the classic scheduling model to simulate the true circumstances of the computer. And then they use the classical analytical methods to design algorithms and solving problems.This paper begins with the relationship between the disk cleanup and computer’s processing speed. We formulate a Scheduling problem in reality and analysis its model. Then we find the model is very common in real life. The problem has much theoretical value and practical significance. We show that the considered problems are all polynomially solvable.We design algorithm for the single-machine problem and parallel-machine problem respectively after building the model. For the single-machine case, the objectives are to minimize makespan and to minimize total completion time. For the parallel-machine case, we consider the objective to minimize total completion time. For each objective, we need to schedule the job sequence and maintains activities.Main work of this paper is following:(1)We study the scheduling model at home and abroad. The study includes the sub models and the related various algorithms. The former main work is summarizing the model’s different expressions which formulated by the scholars. Then we may understand the difference between the models and their significance.(2)We build the model for the problem which extends from the disk cleanup. The parallel-machine is the extension of the single-machine case. Then we give some mathematical symbols.(3)We consider the single-machine case first and then extend to the parallel-machine problem. We design algorithm for the single-machine problem and parallel-machine problem respectively through the preliminary work. For the single-machine case, the objectives are to minimize makespan and to minimize total completion time. For the parallel-machine case, we consider the objective to minimize total completion time. For each objective, we need to schedule the.job sequence and maintains activities.(4)We use our algorithm to solve an example. In the process, we use LINGO software to solve the problem. And the result shows that the considered problems are all polynomially solvable through our algorithm.