Research On Single Machine And Parallel Machine Scheduling Problems With Machine Maintenance Requirements

Scheduling problems are a type of resource optimal configuration problems. They are widely used in the fields of engineering, computers, management, and so on. Particularly, they play important roles in manufacturing industry and service industry. In the current competing environment, scientific and reasonable schedules can not only help companies use their resources to the maximum limits, but also improve the productivity of the companies, and hence provide strong technical support to put the companies in the advantageous position in the market competition.For the past few years, research on scheduling problems increases quickly and new models are constantly emerging. Meanwhile, scheduling problems with maintenance considerations have become a research focus in the field of scheduling. This thesis mainly studies two scheduling problems with maintenance.The first scheduling problem is a single-machine scheduling problem with a machine workload dependent and machine idle time dependent maintenance. We consider a single-machine scheduling problem with a maintenance where jobs are non-preemptive, the start time of the maintenance is given but the duration of the maintenance is an increasing function of the machine workload and the machine idle time before the maintenance, the objective is to minimize the makespan. We divided the problem into three cases for discussion. For each of the first two cases, a polynomial time optimal algorithm is proposed. For the last case, the performance of the classic LPT algorithm is analyzed and the method to obtain an FPTAS for the case from any FPTAS for the classical knapsack problem is provided.The second scheduling problem is a parallel machine scheduling problem with special jobs and machine maintenance requirements. We consider the two-machine case, where the first one needs periodic maintenance while the second one needs tool change maintenance. Special jobs can only be processed on the first machine. Jobs are non-preemptive. The objective is to minimize the makespan. We propose a heuristic algorithm named LPTS based on the classic LPT algorithm and a lower bounds of the optimal scheduling scheme. Numerical experiment shows that the average error of LPTS algorithm is less than 10%.