Complexity And Algorithm Design For Some Multi-Agent Network Scheduling And Batching Scheduling Problems

In this thesis,we consider some multi-agent network scheduling and batching scheduling problems,including multi-agent network scheduling problems and batching scheduling problems with the constraint that the processing time in each batch is no more than a threshold value.Firstly,a polynomial time algorithm for the problem with the weekly constraints is proposed.Secondly,we prove the complexity for the general problem and investigate an approximation algorithm and analysis the worst case performance of the algorithm.Finally,numerical experiments are carried out to further analysis performance of the algorithm.This paper is divided into the following five chapters.In Chapter 1,we first introduce some basic knowledge of combinatorial optimization and scheduling problems.Then the background of multi-agent and network scheduling problems is provided.Meanwhile,literature review and the structure of this thesis are given in this chapter.Finally,the main results in this thesis are presented.In Chapter 2,we consider single vehicle scheduling problems with two agents on a line-shaped network.There are two agents A and B and each of two agents has some customers that are situated at some vertices on the network.A vehicle has to start from v0 to serve all customers.The objective is to schedule the customers to minimize CmaxA+θCmaxB,where CmaxX is the latest completion time of the customers for agent X and X ∈{A,B}.We first propose a polynomial time algorithm for the problem without release time.Next,the problem with release time is proved to be NP-hard despite of a network with only two vertices.Then,we propose a 5/3-approximation algorithm for the single agent problem and further present a(?)-approximation algorithm for the general problem.Finally,numerical experiments are carried out to verify the approximation algorithm is effective.In Chapter 3,we study the two-agent vehicle scheduling problems on a line with a threshold value constraint.Similar to the previous chapter,there are two agents A and B whose customers need to be served by a vehicle,and the vehicle is beginning from the depot v0,but agent B has a special constraint,that is,the makespan of agent B is no more than the threshold value Q.The objective of the problem is to find a route of the vehicle so as to minimize the makespan of agent A under the threshold value constraint condition.This problem can be expressed by the 3-field scheduling notations as line-1|r(vj),CmaxB≤Q|CmaxA.For the problem without release time,we show this problem is solvable in polynomial time and an O(n2)time algorithm is provided.For the problem with release time,we prove this problem is NP-hard by the Partition-problem and then,a(?)-approximation algorithm is presented.Finally,we conclude the numerical experiments to evaluate the performance of the approximation algorithm.In Chapter 4,the two-agent serial batch scheduling problem on a single machine are consider under the constraint optimization model.Compared with the traditional multi-agent batch scheduling problem,the problem in this chapter has a special capacity constraint that the processing time of each batch is no more than a fixed value.For the case that the objective is to minimize sum of the maximum lateness and the cost of agent A,under the constraint that sum of the makespan and the cost of agent B is no more than the threshold value Q,we prove this problem is NP-hard and present a(2,3/2)-approximation algorithm.For the case that the objective is to minimize sum of the maximum lateness and the cost of agent A,under the constraint that sum of the maximum lateness and the cost of agent B is no more than the threshold value Q,we propose a 2-progressive approximation algorithm.In Chapter 5,we conclude the results and present several topics for future research.