Online and Offline Scheduling with Grade of Service Levels

摘要

The problem of scheduling parallel machines with a particular eligibility constraint is considered, which is motivated by the situations where the machines have different expertise levels with respect to the jobs. Jobs and machines are labeled with specified grade of service (GoS) levels. Each machine can process only the jobs whose GoS levels are not less than the level of this machine. The objective is to minimize makespan (the maximum completion time). The majority of the known results deal with the offline setting. The existing online algorithms consider only the special case of two different GoS levels, and all of them are for the ordinary online model where the processing requirement of each job is known at its release date. A more general online model is that the processing requirement of each job is not known until it is processed to completion. A (4-2/m)- competitive algorithm is presented for the general online model, where m is the number of machines. Algorithms with competitive ratio better than 4-2/m are also obtained for the ordinary online model. Moreover, for the offline problem, a simple and fast 4/3-approximation algorithm is presented.