Semi-Online Machine Covering Problems With Tightly-Group Times On Three Parallel Hierarchical Machines

Hierarchical scheduling is one of the hottest problems of combinatorial optimization,and it has important applications in production and commercial activities,such as the reasonable allocation of waiting ports and runways in airports.We mainly studies machine covering problems with tihgtly-group times on three parallel hierarchical machines in this thesis.Given three parallel machines M₁,M₂ and M₃,n jobs J₁,J₂,...,J_n.Each machine has a service hierarchy g(M_i)? {1,2},i = 1,2,3;each job J_j has a processing time p_j ? [1,? ] and hierarchy g_j ? {1,2},j = 1,2,...,n,where ? is a fixed constant.The n jobs arrive one by one,and they will be allocated as soon as they arrive.For any machine M_i and job J_j,i ? {1,2,3},j ? {1,2,...,n},when g(M_i)? g_j,the job J_j can be processed on the machine M_i.The goal is to maximize the minimum load on the machine(machine coverage problem).Given a set of artifacts J = {J₁,J₂,J₃,...,J_n}and a machine set M = {M₁,M₂,...,Mm}.All workpieces can only be processed by one machine,and once the machine is occupied,other workpieces cannot be processed.The goal is to maximize the minimum machine completion time.This problem was named machine covering problem.Chapter 3,one machine has service hierarchy 1,and the other two machines have service hierarchy 2.It is proved that the lower bound of the problem is 1 + ?.The algorithm A₁ is designed by controlling the load of the hierarchy 2 jobs processed on M₁,and it is proved that the competition ratio of the algorithm A₁ is 1 + ?.Chapter 4,two machines have service hierarchy 2,and the other one has service hierarchy 1.It is proved that the lower bound of the problem is 1 + 2?.The algorithm A₂ is designed by controlling the threshold of the load of M₃,and it is proved that the competition ratio of the algorithm A₂ is 1 + 2?.The last chapter summarizes the research results of this article,and gives questions that can be studied in the future.