Several Two-agent Open Shop Scheduling Problems Research On Two-Machine

Scheduling is an efficient allocation to process a number of jobs.Whether the schedul-ing is good or bad directly affects the cost and profit.In the classical scheduling problems,the number of the objective function is always only one and the job only belongs to one agent.This studies some two-agent scheduling problems on single machine.Each agent has its own job set and objective function,the agents have to process all jobs on two machine.Each agent is to minimize the objective function of theirself own set of jobs,and the objective function is only associated with the completion time.The problem is to schedule the processing order of jobs belonging to the two-agent,so that the distinct requirements of the agents are satisfied.This paper mainly studies the following questions:1)The objective is to minimize one of two agents' makespans,the other agent's at most a positive integer.We address the problem in which the agent A wants to minimize the makespan of A-jobs,while the agent B only accepts schedules in which at most Q.First,a complexity proof is presented for this problem.Furthermore,a pseudo-polynomial-time algorithm using the largest alternate processing time(LAPT)rule is presented.2)The objective is to minimize the weighted sum of the makespans of two competitive agents.First,a complexity proof is presented for minimizing the weighted combination of the makespan of each agent if the weight a belonging to agent B is arbitrary.Furthermore,twopseudo-polynomial-time algorithms using the largest alternate processing time(LAPT)rule are presented.Finally,two approximation algorithm are presented if the weight is equal to one.Additionally,a another approximation algorithm is presented if the weight is larger than one.