In this thesis, a framework for market-based resource allocation in manufacturing is
developed and described. The most salient feature of the proposed framework is that
it builds on a foundation of well-established economic theory and uses the theory to
guide both the agent and market design. There are two motivations for introducing
the added complexity of the market metaphor into a decision-making environment
that is traditionally addressed using monolithic, centralized techniques. First, markets
are composed of autonomous, self-interested agents with well defined boundaries,
capabilities, and knowledge. By decomposing a large, complex decision problem along
these lines, the task of formulating the problem and identifying its many conflicting
objectives is simplified. Second, markets provide a means of encapsulating the many
interdependencies between agents into a single mechanism—price. By ignoring the
desires and objectives of all other agents and selfishly maximizing their own expected
utility over a set of prices, the agents achieve a high degree of independence from one
another. Thus, the market provides a means of achieving distributed computation.
To test the basic feasibility of the market-based approach, a prototype, system is used
to generate solutions to small instances of a very general class of manufacturing
scheduling problems. The agents in the system bid in competition with other agents
to secure contracts for scarce production resources. In order to accurately model the
complexity and uncertainty of the manufacturing environment, agents are
implemented as decision-theoretic planners. By using dynamic programming, the
agents can determine their optimal course of action given their resource requirements.
Although each agent-level planning problem (like the global level planning problem)
induces an unsolvably large Markov Decision Problem, the structured dynamic
programming algorithm exploits sources of independence within the problem and is
shown to greatly increase the size of problems that can be solved in practice.
In the final stage of the framework, an auction is used to determine the ultimate
allocation of resource bundles to parts. Although the resulting combinational auctions
are generally intractable, highly optimized algorithms do exist for finding efficient
equilibria. In this thesis, a heuristic auction protocol is introduced and is shown to be
capable of eliminating common modes of market failure in combinational auctions.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:BVAU.2429/11113 |
| Date | 11 1900 |
| Creators | Brydon, Michael |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Relation | UBC Retrospective Theses Digitization Project [http://www.library.ubc.ca/archives/retro_theses/] |
Page generated in 0.0019 seconds