Two Kinds Of Scheduling Problems With Maintenance Activity

Scheduling plays an important role in Operational Research, which is widely used in modern industry. With the development of economy and the progress of the society, scheduling problems are also emerging new models to meet the actual needs. In this paper, we consider two kinds of scheduling problems with controllable maintenance activity and fixed maintenance activity. The controllable maintenance activity refers to that the time or location of the maintenance activity is a decision variable, such as the deteriorating maintenance activity, the rate-modifying activity and so on. The fixed maintenance activity refers to that the maintenance location is given in advance, and the machine is unavailable during the maintenance interval. The main content is organized as follows:In the first chapter, we introduce the related background knowledge, the research status and the main content of scheduling problems discussed in this paper. In the second chapter, we study a single machine scheduling problem with general position-dependent and job-dependent aging effect, where all jobs share a common due window, and we consider a new maintenance model-optional maintenance activity. Both the location and the duration of the maintenance activity are decision variables, and the length of the maintenance activity affects the processing time of jobs scheduled after the maintenance activity. We need to decide whether and when to implement the maintenance activity, how long the duration of maintenance activity is. For the problem, we show the property of the optimal solution, and give a polynomial time algorithm. In the third chapter, we focus on the single machine multiple due windows assignment scheduling problem under a rate-modifying activity. The processing time of a job is a function of its position in a sequence, its deteriorating rate and its resource allocation. The objective is to determine the optimal position of the maintenance activity, the optimal due windows assignment, the optimal resource allocation and the optimal job sequence so as to minimize the total of earliness, tardiness, due windows and resource consumption related costs. We make a detailed analysis and construct a polynomial time algorithm for the problem. The fourth chapter explores two NP-hard problems with a fixed maintenance (non-availability) interval. First, we consider the time-dependent deteriorating jobs under the single machine circumstance. Each job has a release date and can be rejected by paying a penalty cost. The objective is to seek a sequence to minimize the makespan of the accepted jobs and the total rejection penalties of the rejected jobs. Second, we study the scheduling problem in which each job has a delivery time under the parallel-machine circumstance, where only one machine has a fixed maintenance interval, and other machines are available all the time. The objective is to minimize the makespan. We present a fully polynomial-time approximation scheme respectively for the two NP-hard problems. The last of this paper summarizes the whole dissertation and puts forward the future research.