Approximation Algorithms For Agent Scheduling Problems

Agent scheduling problems are new kinds of scheduling problems which are developed in decade. Different from classical scheduling problems, the jobs in agent scheduling problems belong to two or more agents. All agents have their own objectives while they compete common processing resources. In this paper, we mainly consider complexities, approximation and online algorithms for agent scheduling problems. The performance ratios of the approximation algorithms or competitive ratios of the online algorithms are analyzed.Chapter1first introduces some preliminary concepts and necessary knowledge about combinatorial optimization problems and scheduling problems. Then a review of agent scheduling is presented.Two models of two-agent scheduling problem on identical machines are considered in Chapter2. In both models, the objective is to minimize the makespan or the total com-pletion time of agent A respectively, subject to an upper bound on the makespan of agent B. We prove that the two problems are NP-hard and can be solved in pseudo-polynomial time. Furthermore, we design the fully polynomial time approximation schemes for both problems, respectively.In Chapter3, we further study the first model in Chapter2, i.e., minimizing the makespan for agent A while keeping the makespan for agent B under a threshold value. Two approximation algorithms are designed. When the number of machines, denoted by m, is chosen arbitrarily, we provide an O(n) algorithm with performance ratio2-1/m, i.e., the makespan for agent A generated by the algorithm is no more than2-1/m times the optimal value, while the makespan for agent B is no more than2-1/m times the threshold value. This ratio is proved to be tight. Moreover, when m=2, we present an O(nlogn) algorithm with performance ratio (?)1.28which is smaller than3/2. The ratio is weakly tight.A multi-agent scheduling problem on two identical machines is studied in Chap-ter4. Each agent aims at minimizing the makespan. We present a(1+1/6,2+1/6,...,g+1/6)-approximation algorithm which produces a schedule such that the ratio of the makespan of the i-th completed agent to its minimum makespan is no more than i+1/6for i=1,2,..., g. This performance ratio vector is proved to be tight.Chapter5considers an on-line two-agent scheduling problem on single machine. The jobs of two agents arrive over time. The objective is to minimize the linear combination of the makespans for both agents, i.e., CmaxA+θCmaxB, where θ≥1. We present an on-line algorithm with competitive ratio of (?)-competitive for the problem. For the special case of (?), we provide a best possible on-line algorithm. Finally, we make a summary of our paper in Chapter6.