Single-machine Two-agent Scheduling With Constraints

Scheduling with job rejection and multi-agent scheduling are two modern scheduling models received extensive attentions and the known literature has presented deep and systematic research.On the other hand,there are not many studies that combine the two scheduling models.In the published papers of such research,the algorithm presented in one paper is incorrect.This inspired us to further study the two-agent scheduling problem with job rejection.The main content of this paper is divided into two parts.The first part studies the single-machine two-agent scheduling with job rejection under unilateral constraint,in which one of the two agents has an upper bound Q of the objective function.Aiming at the algorithm errors in the literature,we restudied the problem and designed the new algorithm.In the second part we study the single-machine two-agent scheduling under bilateral constraints,in which there exists upper bounds(Q1,Q2)of the objective functions of two agents respectively.Polynomial-time algorithms are proposed for the selection of different objective functions.In Chapter 2,we study the following two scheduling problems:·Two agent scheduling problem with rejection on a single machine in which we shall minimize the sum of the maximum completion time and the total rejection penalty of the jobs in agent A,under the constraint limit of agent B:(?)· Two agent scheduling problem with rejection on a single machine,in which we shall minimize the sum of the total completion time and the total rejection penalty of the jobs in agent A,under the constraint limit of agent B:(?)For the above two problems,we discuss and analyze the existing flaws in the original presentation,and give the corresponding dynamic programming algorithms again.In Chapter 3,we study the following two scheduling problems:· Two agent scheduling problem with bilateral constraints on a single machine,in which we shall minimize the total completion time of all the jobs of agent A and agent B,but there exist a upper bound of the maximum completion time of jobs for both agent A and agent B:(?).· Two agent scheduling problem with bilateral constraints on a single machine,in which we shall minimize the total completion time of all the jobs of agent A and agent B,but there exist two upper bounds of the maximum lateness of jobs for both agent A and agent B:(?)For the above two problems,we present polynomial-time algorithms respectively.For the second problem,firstly,we further extended the two agents to multiple agents;then,we expanded the constrained objective function(LmaxA,LmaxB)to(fmaxA,fmaxB),which is related to the completion times of jobs.