On combinatorial auction and Lagrangean relaxation for distributed resource scheduling

Most existing methods for scheduling are based on centralized or hierarchic al decision making using monolithic models. In this study, we investigate a new method based on a distributed and locally autonomous decision structur e using the notion of combinatorial auction. In combinatorial auction the b idders 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 au ction and Lagrangean-based decomposition. Exploring some of these propertie s, we characterize combinatorial auction using auction protocols and paymen t functions. This study is a first step toward developing a distributed sch eduling framework that maintains system-wide performance while accommodatin g local preferences and objectives. We provide some insights to this framew ork by demonstrating four different versions of the auction mechanism using job shop scheduling problems.