Parallel machine scheduling under a grade of service provision

We consider the problem of scheduling parallel machines that process service requests from various customers who are entitled to many different grades of service levels. We propose and analyze one simple way to ensure such differentiated service. In particular, we investigate how the longest processing time first algorithm (LPT) would perform in the worst case and show that a slight modification of LPT could significantly improve its worst-case performance.