A Study On Online Hierarchical Scheduling And Two-agent Scheduling

The hierarchical scheduling(also called scheduling with grade of service el-igibility)is an important research direction in scheduling theory,and has re-ceived high attention because of its practical and theoretical significance.In some scheduling setting,jobs are only allowed to be processed on some pre-defined ma-chines.In such a case,each job Jj has a non-empty subset of machines(denoted by Mj)that can process the job,referred to as the eligible set of the job.In this thesis,we only consider the inclusive sets.This restriction is also called grade of service eligibility(shortly,GoS eligibility),or hierarchical scheduling.In this thesis this scheduling model is called the hierarchical scheduling.Hierarchical scheduling has many applications in different areas.For example,in the service industry in which a service provider has customers categorized as platinum,gold,silver,and regular members,where those special members are entitled to premi-um services;in wireless communication networks,messages can be classified by their importance,more urgent messages will be sent first.We study in this thesis some hierarchical scheduling problems and two-agent scheduling problems.The thesis consists of four chapters:In Chapter 1,we first introduce the background,development history,com-mon notations and terminologies etc.on scheduling theory,and emphatically introduce the fundamental notions and methods on hierarchical scheduling and scheduling problem with multi-agent.Then we give a review of the related re-search results.In Chapter 2,we consider the hierarchical scheduling problem on two iden-tical machines to minimize the lp-norm.In this chapter,we study the online and semi-online scheduling problems in the settings of fractional assignment,and de-sign best possible algorithms for them,where semi-online means that the total processing time of the jobs is known in advance.In Chapter 3,we consider the hierarchical scheduling problem on two identi-cal machines to minimize the lp-norm in the settings of integral assignment.We also consider online and some semi-online scheduling problems and design best possible algorithms for them,where we study three semi-online versions:in the first version,knowing the total processing time of the jobs in advance,in the second version,knowing the total processing time Ti of the jobs of hierarchy i for i= 1,2 in advance,and in the last version,buffer or arrangement being allowed.In Chapter 4,we consider two-agent scheduling.By a counterexample,we show that the algorithm SDMP presented in Yin et al.[109]for problem 1|s-batch|?CjA+mA?A:LmaxB+mB?B ? U is incorrect.Then we further show that the algorithm presented in Kovalyov et al.[65]for problem 1|s-batch| ? CjA:LmaxB? U can be used to solve problem 1|s-batch| CjA +mA?A:LmaxB+mB?B?U in O(nnA2nB3)time.Finally,by guessing and enumerating the possible max-imum lateness of agent B,we show that the two Pareto scheduling problem-s 1|s-batch|?(?CjA,LmaxB)and 1|s-batch|?(?CjA+mA?A,LmaxB+mB?B)are solvable in((nnA4nB5)time.