Abstract:
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 the 3-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.