Publication Type

Journal Article

Publication Date

10-2011

Abstract

In this paper, we consider the problem of allocating machine resources among multiple agents, each of which is responsible to solve a flowshop scheduling problem. We present an iterated combinatorial auction mechanism in which bid generation is performed within each agent, while a price adjustment procedure is performed by a centralized auctioneer. While this approach is fairly well-studied in the literature, our primary innovation is in an adaptive price adjustment procedure, utilizing variable step-size inspired by adaptive PID-control theory coupled with utility pricing inspired by classical microeconomics. We compare with the conventional price adjustment scheme proposed in Fisher (1985), and show better convergence properties. Our secondary contribution is in a fast bid-generation procedure executed by the agents based on local search. Putting both these innovations together, we compare our approach against a classical integer programming model as well as conventional price adjustment schemes, and show drastic run time improvement with insignificant loss of global optimality.

Keywords

Auction, decentralized decision making, flow shop, resource allocation

Discipline

Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Decision Analytics

Publication

IEEE Transactions on Automation Science and Engineering

Volume

8

Issue

1

First Page

732

Last Page

743

ISSN

1545-5955

Identifier

10.1109/TASE.2011.2160536

Publisher

IEEE

Additional URL

http://dx.doi.org/10.1109/TASE.2011.2160536