${\bf A}{\mbi d}{\bf SCHE}$: An Auction-Based Decentralized Scheduling Framework

This paper presents an auction-based framework for scheduling problems in decentralized environments. The framework consists of an iterative bidding protocol, requirement-based bidding languages, and a constraint-based winner determination approach. Without imposing a time window discretization on resources the requirement-based bidding languages allow bidders to bid for the processing of a set of jobs with constraints. Prices can be attached to quality attributes of schedules. The winner determination algorithm uses a depth first branch and bound search. A constraint directed scheduling procedure is used at each node to verify the feasibility of the allocation. The bidding procedure is implemented by an ascending auction protocol. We show that this framework has improved computational properties compared with existing combinatorial auctions for decentralized scheduling. A case study of applying the framework to decentralized media content scheduling in narrowcasting is also presented.