ND Two-agent Scheduling Problems With Rejection On A Single Machine

Scheduling with job rejection and two-agent scheduling are two modern scheduling models with strong application background,and so,have attracted extensive attention and research in the past two decades.However,only a few of literature studied the combination problems of the two models,i.e.,the two-agent scheduling problems with job rejection.In the scheduling with job rejection,each job is either accepted and processed on the machine,or rejected by paying a corresponding rejection cost.In the classical competitive two-agent(CO two-agent)scheduling,the job sets of two agents are disjoint.However,in the non-disjoint two-agent(ND two-agent)scheduling,it is allowed that the two agents have common jobs.Thus,the ND two-agent scheduling is an extension of the CO two-agent scheduling.In this thesis,we study some ND two-agent scheduling problems with job rejection on the single machine.According to the three-parameter method to denote scheduling problems,the problems studied in this thesis can be uniformly denoted by 1|ND,rej,fB+∑JjB∈RBejB≤Q|fA+∑JjA∈RAejA,which aims to minimum the sum of the scheduling cost and the rejection cost of the jobs of agent A under the restriction that the sum of the scheduling cost and the rejection cost of the jobs of agent B does not exceed its threshold value.According to the different choices of(fA,f B),we study the following four problems:The main results of this thesis are as follows:(1)For problem(P1),we show its NP-hardness,and then provide a pseudopolynomial-time algorithm and a fully polynomial-time approximation scheme.(2)For problem(P2),we show its NP-hardness and provide a pseudo-polynomialtime algorithm.(3)For problem(P3),we show its NP-hardness,and then provide a pseudopolynomial-time algorithm and a fully polynomial-time approximation scheme.(4)For problem(P4),we show its NP-hardness,and then provide a pseudopolynomial-time algorithm and a fully polynomial-time approximation scheme.