| The machine covering problem is one of the hot topics in the field of combinatorial optimization.It has been widely used in the fair allocation of resources,public service industry and team performance evaluation.This thesis studies the machine covering problem on two machines under the hierarchical constraint,which is defined as follows.Given n jobs and two machines,each job has a processing time pi and a service level gi?{1,2};the first machine can handle all the jobs,and the second machine can only handle jobs with service level 2.The objective is to maximize the minimum machine load.In third chapter,the semi-online machine covering problem on two machines with discrete processing time is proposed,where the processing time of all jobs is known to be in {1,2,...,2k?,before processing the job.By using contradiction,it is proved that there is no online algorithm with a competition ratio less than 2k.Fork?2,an optimal semi-online algorithm with a competition ratio of 2k is proposed.In fourth chapter,the semi-online machine covering problem on two machines with known the total processing time of part jobs is proposed.When the total processing times of the jobs with the service level of I is known,it is proved that there is no online algorithm with a competition ratio less than 2,and an optimal semi-online algorithm with a competition ratio of 2 is proposed;when the total processing times of jobs with service level of 1 and service level of 2 are known,it is proved that there is no online algorithm with a competition ratio less than 3/2,and an optimal semi-online algorithm with a competition ratio ofvis proposed.In the last chapter,the results obtained in this thesis are summarized and the prob-lems that can be studied in the future are proposed. |
PDF Full Text Request