Research On Two-agent Scheduling Problems

In this thesis,several scheduling problems are studied.Firstly,we study two-agent scheduling problems on a single machine or parallel machines in which the jobs have release time and the objection functions are makespan.Approximation algorithms,exact algorithms and FPTAS are designed for these problems.Secondly,we research scheduling game problems on a single machine.We discuss time complexity of finding fairness solutions and give the price of fairness.Finally,we study the scheduling problems on a proportionate flow shop machine where a learning effect and the option of job rejection are considered,we find that the algorithms given by the predecessors were wrong and correct it.The thesis consists of six parts.In Chapter 1,we introduce some basic knowledge of combinatorial optimization and scheduling problems.We also provide the background of scheduling problems related to this thesis including two-agent scheduling problems,price of fairness in scheduling problmes,scheduling problems with learning effect and job rejection.Literature review and the structure of this thesis are given in this chapter.In Chapter 2,we focus on two-agent scheduling problems on a single machine in which jobs have release time.The objection functions of both two agents are makespan.We consider the combinatorial model and the constrained model.For the former,an improved 1+θ/(1+θ)2approximation algorithm is given.For the latter,we design a 3/2-approximation algorithm,dynamic programming algorithm and FPTAS.Besides,a MIP model for the problem is provided and numerical experiments show that the approximation algorithm is effective in large-scale instances.In Chapter 3,two-agent scheduling problem with release time on parallel machines is considered.The objection functions of both two agents are makespan.We study the weighted sum model,for which a 2-approximation algorithm,pseudo polynomial time algorithm and FPTAS are given.In Chapter 4,we study price of fairness in two-agent scheduling problems on a single machine.These problems were first proposed by Agnetis et al.The objection functions of two agents are total completion time,total weighted completion time or maximum tardiness.We give the time complexity of finding fair solutions and price of fairness.We carry out an open problem proposed by them and some problems that they expected to be solved.In Chapter 5,scheduling problems on a proportionate flow shop are studied,in which a learning effect and the option of job rejection are considered.The objective is to minimize the makespan,the total completion time of all accepted jobs,or the total load of all machines while the total rejection cost cannot exceed an upper bound.These problems were first studied by Mor et al.They provided pseudo polynomial time algorithms for these problems.However,we find these algorithms are wrong by counterexamples.Besides,we propose new pseudo polynomial time algorithms to solve these problems.In Chapter 6,our research results are concluded and several topics are presented for future study.