有服务等级约束的同类机在线排序问题的可分算法

An Optimal Fractional Algorithm for Online Hierarchical Scheduling on Uniform Machines

研究了一类有四个服务等级的可分排序问题,在一定条件下改进了下界,并且提出了一种最优算法。在该问题中,工件和机器都带有各自的服务等级约束,当且仅当工件的服务等级比机器的服务等级高或者相同时,该机器才被允许对该工件进行加工,并且每个工件都被允许在所有机器之间按照任意的比例分割后进行加工,同一个工件的各个部分被允许同时放在各台机器上进行加工,优化目标是找到最小时间表长。

In this paper,we investigate the parallel machine scheduling problem under a grade of service provision where the jobs and the machines are both graded.A job can be processed by a machine if and only if its grade is not lower than that of the machine.We discuss the online version of fractional scheduling,where the jobs arrive one by one and the information of the job is unknown before it arrives,and each job can be arbitrarily split,and the obtained fragments can be processed on different machines simultaneously.The objective is to minimize the makespan,i.e.,the maximum completion time of the machines.According to the3-field notation,we denote the problem by Qm|online,frac,g=l|Cmax,where g=l indicates that the jobs have l different hierarchies.We present an optimal algorithm for the problem with four hierarchies under certain conditions.In some service system,customers are classified as ordinary and special.All service facilities can serve ordinary customers,but only some of them can serve special customers.Customers arrive over time,forming a queue in order of their arrivals,and their needs become known upon arrival.A service policy is applied to serve the customers.This kind of operation occurs in many service and manufacturing systems,such as banks,web service,airplane checking in,product processing,etc.The hierarchical scheduling problem is an important practical paradigm.It has many applications in diverse areas,such as assigning classes of service to calls in wireless communications networks,routing queries to hierarchical databases,signing documents by ranking executives,and upgrading classes of cars by car rental companies.Considering a wireless communication network,customers arrive one by one in an arbitrary order similar to that of cellular phone system.Upon arrival each customer discloses the extent of service it requires and must be assigned a base station,from those within range,to service it.Improper station assignment may cause overloading of some station.Thus it is desirable to spread the load as evenly as possible.