The scheduling problem with machine maintenance is a kind of problem which has been studied more and more in recent years and has important practical application background.This paper cosiders a two-agent scheduling problem on single machine with preemptive jobs and workload-dependent maintenance durations,in which the duration of a machine maintenance is a non-decreasing function of the continuous working time of the machine.The goal is to find a schedule to minimize the maximum completion time of one agent when the maximum completion time of the other does not exceed a given upper bound T.The whole paper is divided into four chapters.The first chapter introduces the background of the scheduling problem and the related research status.In chapter 2,we discuss the two-agent scheduling problem when the maintenance time function is concave.This paper considers two situations where the work piece of agent A is completed first and the work piece of agent B is completed first.In different constraints,we discuss the variation trend of the two agents' makespan when changing from agent A's optimal schedule to agent B's optimal schedule.The optimal schedule is judged according to the graphs of function changes,and the optimal algorithm is designed.In chapter 3,we discuss the problem when the maintenance time function is convex.We also consider two situations where the work piece of agent A is completed first and the work piece of agent B is completed first.The variation trend of the two agents' makespan under different constraints are discussed,and the optimal algorithm is designed.Finally,the fourth chapter summarizes the whole text and gives the future research direction. |