Early Work Maximization Problem Under Hierarchical Constraints

Scheduling theory has a rich practical background and plays an important role in manufacturing and service industries.In recent years,scheduling theory has developed rapidly and the early work maximization problem is an important branch of scheduling theory,which has been widely concerned by related scholars.In this thesis,we consider the problem of early workload maximization under hierarchical constraints.The full text is divided into five chapters.In Chapter 1,we introduce the research background and related work.The problem in this thesis is described as follows:give a j ob set J and two parallel machines M1,M2,the hierarchy of Jj∈J is gj∈｛1,2}.The machine M1 can process all jobs and M2 can only process jobs of hierarchy 2.The goal is finding a feasible schedule to maximize the total early work.In Chapter 2,we study the online case of early work maximization problem with hierarchical constraints.Firstly,we prove that the lower bound is(?).Then,design an optimal online algorithm with a competitive ratio of(?).In Chapter 3,we design an optimal semi-online algorithm with the competitive ratios of 6/5 and(?)respectively for two semi-online cases including:the largest job is known to be a low-hierarchy job and the largest job is known to be a high-hierarchy job.In Chapter 4,we design an optimal semi-online algorithm with the competitive ratios of 4/3,(?)and 6/5 respectively for four semi-online cases including:the total processing time of j obs is known,the total processing time of low-hierarchy jobs is known,the total processing time of high-hierarchy jobs is known and the total processing time of two-hierarchy jobs is known.In Chapter 5,we summarize the results of this thesis and discuss the future research direction.