A market-based approach to resource allocation in manufacturing.

摘要

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.