Research Of Related Problems Of Multi-objective And Multi-agent Scheduling

Scheduling theory has rich theoretical value.Scheduling can be divided into classical and modern.Comparison with classic scheduling,modern scheduling breaks through basic assumptions of the classic scheduling.For multi-objective scheduling,people usually focus on four kinds of models,layered optimization,constrained optimizationl,linear combination optimization and Pareto optimization.And the other three models will be solved after Pareto optimization being solved.The multi-agent scheduling is specific multi-objective scheduling,and traditional multi-objective scheduling can be understood as the multi-agent scheduling which have a common job sets with each agent having its own objective function.In recent years,batch scheduling has developed rapidly,which has a strong application background.A lot of practical problems can be appropriately refined or adjusted as multi-objective and multi-agent batch scheduling to solve,so research on multi-objective and multi-agent scheduling has positive practical significance.The main contents of this thesis consist of the following three chapters.The first chapter mainly introduces the classification and current situation of scheduling problem.In the second chapter,we consider the two-agent scheduling problem on an unbounded parallel-batching machine to minimize makespan of agent A and maximum cost of agent B simultaneously.We present aO(n_B~7(10)n_A)polynomial-time algorithm for finding all Pareto optimal points of the problem.The third chapter studies two two-agent scheduling problems on a serial-batch machine.The first problem is about minimizing makespan of agent A and total completion time of agent B simultaneously.We solve the bounded model inO(n_B~3(10)n_A)time and present an improved polynomial-time algorithm for the unbounded model which had a known O(n_B~4(10)n _A n_B)polynomial-time algorithm.We also consider a bounded serial-batching scheduling problem with two-agent jobs to minimize makespan of agent A and maximum lateness of agent B simultaneously,in the case that the processing times and due dates of agent B are agreeable,we present aO(n_B~4(10)n_A)polynomial-time algorithm for finding all Pareto optimal points of the problem.