Several Two-agent Scheduling Problems Research On Single 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 share a common machine to process all jobs.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 dissertation mainly studies the following questions:1)scheduling problem that minimizing the total late workThe first agent has total late work as its objective function,while the second agent consider either the total complete time or the number of tardy jobs as its objective func-tion.The goal is to find a schedule that minimize the objective of the first agent while keeping the objective of the second agent cannot exceed a giving upper bound.We present pseudo-polynomial time algorithms for these two scheduling problem,respectively.2)scheduling problem with rejectionThe objective function of the first agent are the sum of the makespan and total rejection penalty,the sum of the lateness and total rejection penalty,the sum of the total late work and total rejection penalty,respective.The total weight number of late jobs as its objective function of the second agent.For the several scheduling problems,ordinary NP-hard is proved,and pseudo-polynomial time algorithms for the scheduling problem are presented,respectively.3)scheduling problem with release time and preemptionThe total late work is the objective function of the first agents.The jobs belonging to the first agent has its own release time and preemption is allowed.The job belonging to the second agent does not allow preemption and has to be scheduled in fixed time window.In the end,a algorithm for this scheduling problem is present.