Scheduling Problems With Two Competing Agents About Total Weighted Late Work On A Single Machine

Scheduling problem is determine an efficient allocation when the number of jobs are processed.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 to minimize the objective function of their own set of jobs,and them objective function is only associated with the completion time.In order to satisfy the distinct requirement of the agents,the problems that processing order of jobs belonging to the two agents are being research.This paper mainly studies the following questions:1)Two-agent non-preemptive scheduling problem with the total weighted late work.The objective functions of first agent is the total weighted late work,and the objective functions of second agent is the maximum delay,the total completion time or number of tardy jobs.It is prove that the two-agent scheduling is binary NP-hard by partition problem or knapsack problem,and give the optimal schedule rules.Finally,we set the dynamic programming algorithm for minimizing the objective function.2)Two-agent preemptive scheduling problems with the total weighted late work.The objective functions of first agent is the total weighted late work,and the objective functions of second agent is the maximum cost function or total late work.The corresponding polynomial time algorithm is proposed.