Research On Machine Scheduling Problems With Consideration Of Preventive Maintenance

In classical scheduling models, it is usually assumed that machines are always available for processing throughout the whole scheduling period. However, in real industry settings, manufacturers usually plan preventive maintenance in advance before the scheduling period as machine failure or breakdown should be prevented to guarantee products quality, reduce maintenance costs and improve production efficiency. In this regard, it is necessary to consider such preventive maintenance in scheduling problems.In this dissertation, single machine scheduling problems with consideration of preventive maintenance are considered in detail firstly, which include the problems with a deterministic maintenance and constant jobs, the problems with a deterministic maintenance and deteriorating jobs, the problems with a flexible maintenance and constant jobs, and the problems with a flexible maintenance and deteriorating jobs. For the multi-machine scheduling problems, the emphasis lies in the problem with a deterministic maintenance and constant jobs, based on which, the idea to extend the method for single machine problem to the corresponding multi-machine problem is introduced, and with this idea, the other three multi-machine problems can be solved in a similar way. Affected by maintenance periods, jobs may be interrupted during processing. In view of the different case in real industry, three cases, i.e., resumable, nonresumable and semiresumable cases are considered in this dissertation.It is assumed that the objective functions of these problems are makespan and total (weighted) completion time, both of which are related to production efficiency. According to the complexity of the problems, different methods to generate solutions are applied: for the NP-hard problems, on one hand, exact algorithms are developed to derive an optimal solution for the problem within a reasonable size, on the other hand, in view of the deficiency of these exact algorithms, effective heuristics are proposed to obtain a near-optimal solution for the large-sized problem within a reasonable time period; in some special cases, the problem is polynomially solvable, which is proved by the fact that a polynomial algorithm can generate optimal solutions for such a problem.The main contributions of the dissertation are summarized as follows.(1) For the single machine scheduling problems with a deterministic maintenance and constant jobs, two objective functions are considered as follows with the assumption that the disrupted job is semiresumable: A) For the makespan minimizing problem, after a brief explanation of the fact that the problem is NP-hard, the worst-case relative error bound of the LPT rule is analyzed, based on which, two heuristics, i.e., LPT-PI and MLPT, are proposed. Specifically, LPT-PI considers the LPT rule as the initial solution, which is then improved by a neighborhood search based on Pairwise Interchanges; while MLPT improves the LPT algorithm when a class of special cases happens. In addition, the worst-case relative error bound of the MLPT is also shown. To compare the performance of LPT-PI and MLPT, a large number of experiments with random data are conducted. B) When the objective is to minimize the total weighted completion time, it is easily shown that the problem is NP-hard. Then, a property of the optimal solution is proposed, based on which, a dynamic programming algorithm and a branch-and-bound algorithm are developed. Experiment results show that the algorithms are effective, and that the branch-and-bound outperforms the dynamic programming in both the size of the problem solved and the time needed to find the optimal solution. (2) For the single machine scheduling problems with a deterministic maintenance and deteriorating jobs, two objective functions, i.e., the total completion time and the makespan, are considered. When the disrupted job is resumable, the problems with linear increasing or linear decreasing processing times under the two different objectives mentioned above are shown to be polynomially solvable. As for the nonresumable case, the problem with linear increasing processing times with respect to minimize the total completion time is considered in detail. For such a problem, its NP-hardness is briefly discussed and then, a property of the optimal solution is proposed, based on which, a dynamic programming algorithm is developed to derive the optimal solution. Due to the limitations of the algorithm in its application, the worst-case error bound of the Shortest Normal Processing Time (SNPT) rule is given. Based on the SNPT rule and Interchange Technique, a heuristic is proposed to find the near-optimal solution. Experiment results show that the heuristic is excellent not only in its running time but also in the quality of solution, as regarding all the instances, the average and maximum relative error between the results generated by the heuristic and those genertated by dynamic programming are only 0.082% and 3.448% respectively, in addition, the solution is optimal for almost half of the instances in the experiments. Further, the analysis shows that there are similarities between the methods solving the problems mentioned above and the methods solving the problems under other objectives and processing time functions, and such methods are also given in the dissertation briefly.(3) For the single machine scheduling problems with a flexible maintenance, the emphasis lies in the problem with constant jobs, in which the total completion time is minimized. For the resumable case, a set of properties of the optimal solution are identified first. Then an SPT algorithm is proposed and the solution generated by the algorithm is shown to be optimal, which implies that the problem is polynomially solvable. As for the nonresumable case, its NP-hardness is explained briefly. Similar to the resumable case, a set of properties of the optimal solution and a SPT algorithm are presented. Additionally, the conditions under which the SPT algorithm is optimal are also specified. Furthermore, the relative error bound of the SPT algorithm is provided as well. Based on the properties of the optimal solution, a dynamic programming and a branch-and-bound algorithm are developed. For the branch-and-bound algorithm, its initial solution is based on the SPT algorithm, then, such a solution is improved by swapping the last job before the maintenance with jobs after the maintenance according to the two new properties proposed; in addition, the proposed lower bounds are generated based on the corresponding problems with deterministic maintenance. Experimental results show that the dynamic programming and the branch-and-bound algorithm are effective and complementary in dealing with different instances of the problem. And for the problem with deteriorating jobs, its resumable case is shown to be polynomially solvable, then the similarity between the methods to solve the problem with deteriorating jobs and the corresponding one with constant jobs is discussed, based on which, the method to solve the nonresumable case is given.(4) For the multi-machine scheduling problems, the focus is the problems with deterministic maintenances and constant jobs. With the assumption that the disrupted job is semiresumable, two objectives, i.e., minimizing the makespan and minimizing the total weighted completion time, are considered as follows: A) For the problem to minimize the makespan, its NP-hardness is explained firstly. Subsequently, an integer programming model is developed, and four properties of swapping jobs between two machines are introduced. Based on the properties, a heuristic is proposed, which takes the LPT schedule as its initial solution and improves the solution by repeatedly swapping the jobs between two machines with the maximal and minimal makespan respectively. Experiment results regarding the comparison between the heuristic and the LPT algorithm show that the proposed heuristic is efficient and effective. B) For the problem to minimize the total weighted completion time, following the discussion of the problem's NP-hardness, a property of the optimal solution is proposed. Based on the property, a dynamic programming algorithm is developed to derive the optimal solution for the small-sized problems. Additionally, a heuristic based on the WSPT rule and Interchange Technique is proposed to obtain the near-optimal solution for the medium-to-large-sized problems. Experiment results show that the average and the maximum relative error of the heuristic are 0.463% and 5.094% respectively, which indicate the effectiveness of the heuristic. After the analysis of the difference and similarity between the methods to solve the above two problems and the corresponding single machine problems, the idea to extend the method for single machine problem to multi-machine problem is introduced. With this idea, the other three multi-machine problems can be solved accordingly.