Date of Award
2007
Degree Type
Thesis
Degree Name
Doctor of Philosophy
Program
Electrical and Computer Engineering
Supervisor
Dr. Hamada H. Ghenniwa
Second Advisor
Dr. Weiming Shen
Abstract
This thesis investigates computational and modeling issues in developing solutions for decentralized scheduling problems. Compared with their centralized counterparts decentralized scheduling problems differentiate themselves in the distribution of scheduling knowledge and control, which introduces new levels of complexities in additional to the traditional computational complexity of centralized scheduling problems, namely: the coordination complexity due to the interaction problems among agents and the mechanism design complexity due to the self-interested nature of agents. These complexities intertwine and need to be addressed concurrently. The approach taken here is to map decentralized scheduling problems into combinatorial allocation problems for which combinatorial auctions have been adopted as a solution approach. Auctions offer great promise as mechanisms for optimal resource allocation in decentralized environments. However, their applicability to the scheduling problems depends on managing their computational complexities. To this end, the central theme of this thesis is to address the complexity aspect of valuation, communication, and winner determination in the context of decentralized scheduling system design. Our approach is to integrate concepts and principles of computational mechanism design and classical scheduling theory and enrich both fields by (1) extending classical centralized scheduling problem models to decentralized models; (2) embedding scheduling specific problem solving structures and heuristics as an integral part of combinatorial auction model. In light of this, we first present a generic model of decentralized scheduling problems along with a formal mapping to combinatorial allocation problems. We, then, provide a family of requirement-based bidding languages that are appropriate for the scheduling domain. Furthermore, we propose constraint-based winner determination algorithms using a bid-driven depth first branch and bound search and an iterative auction framework, which embeds the requirement-based languages and constraint-based winner determination. Finally, we demonstrate the applicability of the framework for the decentralized promotion scheduling problems and the due date negotiation problems
Recommended Citation
Wang, Chun, "Economie Models for Decentralized Scheduling" (2007). Digitized Theses. 5020.
https://ir.lib.uwo.ca/digitizedtheses/5020