Abstract

This thesis investigates the computational and modeling issues involved with developing solutions for distributed service scheduling problems. Compared with traditional manufacturing scheduling, service scheduling poses additional challenges due to the significant customer involvement in service processes. The first challenge is that the service scheduling environment is a distributed environment in which scheduling-related information is scattered among individual identities, such as service providers and customers. The second challenge is that the service scheduling environment is a dynamic environment. Uncertainty in customer demand, customer cancellations and no-shows make the scheduling of services a complex dynamic process. Service scheduling has to be robust and prepared to accommodate any contingencies caused by customer involvement in service production. The third challenge concerns customers’ private information. To compute optimal schedules, ideally, the scheduler should know the complete customer availability and preference information within the scheduling horizon. However, customers may act strategically to protect their private information. Therefore, service scheduling systems should be designed so that they are able to elicit enough of a customer’s private information that will make it possible to compute high quality schedules. The fourth challenge is that in a service scheduling environment, the objectives are complicated and they may even be in opposition. The distributed service scheduling environment enables each agent to have their own scheduling objectives. The objectives of these agents can vary from one to another. In addition to multiple objectives, since agents are self-interested, they are likely to behave strategically to achieve their own objectives without considering the global objectives of the system. Existing approaches usually deal with only a part of the challenges in a specific service domain. There is a need for general problem formulations and solutions that address service scheduling challenges in a comprehensive framework.
In this thesis, I propose an integrated service scheduling framework for the general service scheduling problem. The proposed framework uses iterative auction as the base mechanism to tackle service scheduling challenges in distributed and dynamic environments. It accommodates customer’s private information by providing appropriate incentives to customers and it has the potential to accommodate dynamic events. This framework integrates customers’ preferences with the allocation of a provider’s capacity through multilateral negotiation between the provider and its customers. The framework can accommodate both price-based commercial settings and non-commercial service settings. Theoretical and experimental results are developed to verify the effectiveness of the proposed framework. The application of the framework to the mass customization of services and to appointment scheduling are developed to demonstrate the applicability of the general framework to specific service domains. A web-based prototype is designed and implemented to evaluate the scalability of the approach in a distributed environment.