The Study Of Two-Agent Scheduling Problems

Scheduling problems have a lot important applications in many fields, such as computer science, control science, management science, etc. Multi-agent scheduling problems are receiving increasing attention in recent ten years. As kinds of multi-objective optimization, Multi-agent scheduling problems can be solved by game theory, combinational optimization model or some other methods. In this paper some two-agent scheduling problems are considered on single machine or identical machines.For single machine environment, we consider the problem of scheduling jobs with release dates for two agents. The objective is to minimize the makespan for agent A, where the makespan of agent B has an upper bound. We address the complexity of the problem and provide a PTAS for restricted problem. For the environment of identical machines, we research two scheduling models. In the first model, the goal is to minimize the total completion time of agent A where the total completion time of agent B has an upper bound. As the problem is NP-hard, we provide a pseudo-polynomial time algorithm for it and a FPTAS for restricted case.In the second model the number of machines is chosen to be arbitrary. We try to minimize the makespan of agent A with the makespan of agent B having an upper bound. By the dynamic programming algorithm for bin packing problem with fixed number of objective sizes, we present a PTAS for restricted scheduling problem.