Auction-based distributed scheduling in a dynamic job shop environment

Developments in computing and communication technology coupled with the inability to address real-time issues in scheduling algorithms based on central control, has led to an interest in solving the problem of a distributed decision-making environment. This paper presents a new job shop formulation that schedules jobs using auctions for distributing control. A theoretical basis is presented for problem decomposition, bid construction, and bid evaluation for the auction using standard mathematical programming tools. Numerical results show that the auction-based approach outperforms the distributed dispatching approaches and can be used to create schedules for a wide range of scheduling objectives.