Scheduling Problems With Periodic Maintenance To Minimize Makespan

This paper mainly considers machine scheduling problemwith (single or periodic) maintenance activities. Given a sequence J={J₁, J₂,...,J_n} of independent jobs, each with a positive processing time(size) p_i, i=1,...,n, all jobs must be non-preemptively scheduling on one or several identical machines. The paper consists of three chapters.Chapter 1 gives some introduction and preliminaries for scheduling problems.Chapter 2 introduces single-machine scheduling problem with one maintenance, there are two sorts: fixed maintenance, optional maintenance.Chapter 3 discusses machine scheduling problem with periodic maintenance. This chapter prove that LS is the optimal online algorithm of P₁|periodic-mainten ance|Cmax. The competitive ratio of LS algorithm is 2. The algorithm with constant bound of P₂|periodic-mainten ance|Cmax doesn't exist. Besides, we give a offline polynomial algorithm with parameter bound.