On combinatorial auction and Lagrangean relaxation for distributed resource scheduling

On combinatorial auction and Lagrangean relaxation for distributed resource scheduling

0.00 Avg rating0 Votes
Article ID: iaor20021174
Country: United States
Volume: 31
Issue: 9
Start Page Number: 813
End Page Number: 826
Publication Date: Jan 1999
Journal: IIE Transactions
Authors: ,
Abstract:

Most existing methods for scheduling are based on centralized or hierarchical decision making using monolithic models. In this study, we investigate a new method based on a distributed and locally autonomous decision structure using the notion of combinatorial auction. In combinatorial auction the bidders demand a combination of dependent objects with a single bid. We show that not only can we use this auction mechanism to handle complex resource scheduling problems, but there exist strong links between combinatorial auction and Lagrangean-based decomposition. Exploring some of these properties, we characterize combinatorial auction using auction protocols and payment functions. This study is a first step toward developing a distributed scheduling framework that maintains system-wide performance while accommodating local preferences and objectives. We provide some insights to this framework by demonstrating four different versions of the auction mechanism using job shop scheduling problems.

Reviews

Required fields are marked *. Your email address will not be published.