Research On Single-machine Scheduling Problem With Processing Time Deterioration

Scheduling problem is indispensable part in the manufacturing and services, in which single-machine scheduling problem is a core part. A study of single-machine scheduling plays a very important role for improving enterprises efficiency, reducing waste of resources, improving customer satisfaction, and optimizing the allocation of resources.In classical scheduling problem, the processing time of a job is assumed to be a constant. However, in realistic scheduling problem, since the influence of external environment and its characteristics exists, the processing time of the job will need longer time than that of jobs before it. This phenomenon is known as deterioration. Therefore, in this dissertation, single-machine scheduling problem with processing time deterioration is considered.Firstly, the emerging background, characteristics, classifications and present researches of single-machine problem, which is a reference for the study of single-machine scheduling problem with deterioration, are reviewed. Simultaneously, the branch and bound algorithm, the nested partitions method, and their applications in optimization problems are also reviewed. It proposes ideas of the algorithm design for solving single-machine scheduling problem with deterioration. Based on above theorey foundation and motivated ideas, in this dissertation, according to the processing time of a job depending on different deterioration model, single-machine scheduling problem with deterioration depending on starting time, single-machine scheduling problem with deterioration depending on waiting time, single-machine scheduling problem with deterioration depending on accumulative processing times, and due date assignment problem with deterioration depending on accumulative processing times are mainly studied.For single-machine scheduling problem with deterioration depending on starting time, it is studied according to whether deterioration rates are identical or not, respectively. (1) For the case of identical deterioration rates, the single-machine scheduling problem with different release times and identical deterioration rates is considered, in which the objective is to minimize makespan. Firstly, the mixed integer programming model is proposed and solved using ILOG soft package. The results show that the model is effective by comparing it with algorithms proposed in existing literature. (2) For the case of different deterioration rates, the single-machine scheduling problem with different release times and deterioration rates is considered, in which the objective is to minimize makespan. Firstly, the mixed integer programming model is proposed and solved using ILOG soft package. Secondly, the branch and bound algorithm integrated with dominated properties and lower bounds is proposed to obtained optimal solutions of the problem. Because of its limitations for large scale problem, rules guided nested partitions method is proposed to obtain near-optimal solutions of the problem. Finally, the results show that the model and algorithms proposed are effective.For single-machine scheduling problem with deterioration depending on waiting time, it is studied according to whether the deterioration model is linear or not, respectively. (1) For the case of linear deterioration model, the problem with minimizing makespan is considered. Firstly, the linear deterioration model is proposed, in which the processing time of a job is linear increasing depending on waiting time. Secondly, the branch and bound algorithm integrated with dominated properties and lower bounds is proposed to obtained optimal solutions of the problem. Then, rules guided nested partitions method is proposed to obtain near-optimal solutions of the problem. Finally, the results show that algorithms proposed are effective by comparison and analysis. (2) For the case of piece-wise linear deterioration model, the problem of minimizing makespan is also considered. Firstly, the piece-wise linear deterioration model is proposed, in which the processing time of a job is piece-wise linear increasing depending on waiting time. Similarly, the branch and bound algorithm integrated with dominated properties and lower bounds and the rules guided nested partitions method are proposed to solve the problem. Finally, the results show that algorithms proposed are effective.For single-machine scheduling problem with deterioration depending on accumulative processing times, it is studied to consider multi-rate-modifying activities and recovery function, respectively. (1) For the case of considering multi-rate-modifying activities based on the job processing time deterioration depending on accumulative processing times, the problem of minimizing makespan is considered. Firstly, the dominated properties and lower bounds are proposed; secondly, the branch and bound algorithm based on properities and lower bounds and the heuristic algorithm based on properities are given. And the experiment results show the algorithms proposed are effective. Finally, it is proved that two special cases can be solved within polynomial time. (2) for the case of considering recovery function based on the job processing time deterioration depending on accumulative processing times, the problem of minimizing makespan and the total completion times are considered, respectively. Firstly, the recovery function based on time is proposed according to the characteristics of labor recovery depending on time. Based on it, polynomial algorithms are given for the above problems. Finally, the experiment results show that the model and algorithms proposed are effective.For due date assignment problem with deterioration depending on accumulative processing times, it is studied to be subject to allowing earlier jobs and assign multi-rate-modifying activities (multi-RMAs), respectively. (1) For the case of being subject to allowing earlier jobs, the problem of minimizing total tardiness penalties is considered. It is proved that the problem can be solved in polynomial time. And the polynomial algorithm and an example are given. (2) For the case of assigning multi-rate-modifying activities, the problem of minimizing total earliness and tardiness penalties is considered based on the job processing time deterioration depending on accumulative processing times and assign multi-RMAs. Firstly, several different cases of the problem are analyzed according to its characteristics. Secondly, the optimal slack time is given. Finally, it is proved that the problem is solvable in polynominal time.Finally, a summary conclusion of the dissertation is given and some suggestions are proposed for the future research.