Prioritizing and Scheduling Service Requests under Time Constraints

This paper presents a game theoretic model and an iterative bidding framework for the service request prioritizing and scheduling problem in Software as a Service (SaaS) environments. We focus on a type of settings in which the service provider's existing capacity is over demanded and customers' service requests are constrained with completion times. To gain more profit, the provider needs to prioritize customers' requests based on their profitability and schedule as many profitable requests as possible. The prioritizing and scheduling problem is considered in a strategic setting in which customers' values on the service requests are their private information that is not known to the provider, which calls for economic based models. The key issue here is how to maximize economic social welfare across all customers given the presence of customers' self-interests. We propose an iterative bidding framework as a multilateral negotiation platform for the service provider and its customers to allocate compute capacity among service requests. The proposed bidding framework is evaluated by a computational study. The data from the experiments show that the proposed approach produces near optimal solutions with moderate information revelation. It also scales well to large size problem instances.