Project topics and materials
Get Complete Project Material File(s) Now! »
Problem Statement
The problem to be solved is described as follows:
Given a multi-facility manufacturing enterprise manufacturing discrete parts in an Make-To-Order (MTO) production environment, and given the customer demand for a particular time horizon, to find a plan of allocating production of various components required according to the exploded BOM for each product, such that the planning function is integrated with the scheduling function of various production facilities, which operate to optimize their individual objectives, while meeting customer deadlines. The production facilities considered can be either a part of the enterprise itself or sister facilities to whom production can be out-sourced. The main characteristic of this scenario is that exact resource capacity at each of these facilities may not be known to the enterprise. The facilities act as autonomous entities with finite production capacity, and carry out production targets set by the planning function of the enterprise to meet their own objectives which can change with time. The planning function should be agile enough to take care of unforeseen disturbances such as order cancellations, order updating, material and resource unavailability at production facilities etc., so that plans can be changed dynamically to solve current demand problem using the current production resources. It is also preferable to incorporate the concept of priority between customer orders in order to expedite processing of rush orders. Given demand for a particular period for all the end products, we need to allocate this demand in terms of production of constituent components to competing production facilities. The production of these components has to follow the rigid precedence order as indicated in the exploded BOM for the particular product. These production facilities have overlapping capacities, i.e., the same facility can produce more than one component as well as the same component can be produced at more than one facility which compete with one another to secure production of these components so as to maximize the utilization of their available capacities and also profit. The objective of the solution approach is to minimize the total cost of production, incurred by the system, while at the same time satisfying all of the projected demand in a given planning period. The solution methodology is supposed to have a two-pass approach. In the first pass, it determines the feasibility of fulfilling the projected demand given the current level of limited production capacity and due dates. If the production can be feasibly scheduled on the production facilities, the next step is to create a master production plan to allocate entire production (fabrication/assembly/inspection etc.) over the given production facilities while trying to optimize the total cost of production given individual objectives of various entities (orders and production facilities).
Literature Review
This chapter discusses previous research efforts and state of the art in various domains related to this research study.
Advanced Planning and Scheduling Systems
Turbide, offers an overview of APS capabilities. A detailed description of APS functionalities is provided in Eck. It also provides a list of commercially available APS solutions and a brief comparison of their features. Lee, et al. [37] considers the APS problem in a production environment with finite capacity resources, multiple products with precedence constraints and the option of outsourcing. The main objective of the research study is to produce an APS model that minimizes make-span by considering alternative machines and operation sequences with precedence constraints and outsourcing. The authors develop a GA-based approach to obtain near-optimal solutions in this environment for an integrated process plan and production schedule. The model does not consider multiple in-house production facilities. Even though precedence constraints between operations are considered, the quantity relationships between components are not addressed. This limits the applicability of the solution procedure presented in view of a real-world production system. In our work, we increase the applicability of APS solution procedure by including these extensions. Lee and Kim [38] consider a similar problem of multi-period, multi-product and multi-shop production and distribution problem in a supply chain to satisfy retailer demand. The authors propose a hybrid analytical and simulation based approach to find near-optimal solutions to minimize overall cost of production, distribution, inventory holding and shortages while maintaining due date and capacity constraints. The main drawback of this model is that it does not consider overlapping production capacity between different facilities which limits its application in modern industrial environments. Also, the emphasis on analytical model makes it inapplicable for complex production and distribution networks.
Enterprise Integration using Multi-Agent Systems
With an increase in global competition and uncertainty, agility has become an important requirement of success for enterprises. New models are needed to capture the complex and dynamic operating environment which is beyond the capability of the mathematical programming and simulation based approaches to model and solve effectively. Multi-agent systems are a branch of Distributed Artificial Intelligence (DAI) which are a logical framework for developing distributed applications to support production network modeling and management (Nigro, et al. [43]). Noori and Mavaddat [44] discussed some of the contemporary issues and solutions in enterprise integration. Similarly, Vernadat [64] and Lim et al. presented good reviews of integration methodologies and their significance. A good reference for current standards for enterprise integration as well as a comprehensive comparison is given in Chen and Vernadat. The reviewers note the lack of satisfactory use of available standards in industry and suggest applicability of these standards only to upper levels of system lifecycle as the disincentive for their restricted use. Use of application specific multi-agent systems which are themselves based on standards prevalent in distributed artificial intelligence community as well as heterarchical manufacturing system design, seem to offer a solution. Multi-agent system based solutions for enterprise integration was first proposed by Pan and Tenenbaum. According to Jain, et al. Autonomous agents provide a good way to coordinate the activities of various entities in a supply chain network. To avoid unrestricted autonomy degenerating into chaos, the authors propose to restrict autonomy of individual agents through the concepts of flexible commitments in a SoCom (Sphere of Commitments). The case of leveled commitments as an approach to coherence in contract net based multi-agent systems for iterative task allocation is discussed in Sandholm and Lesser[56]. The Integrated Supply Chain Management System (ISCM) project (Barbuceanu and Fox[10]) considered manufacturing enterprise as a network of operational nodes, enabling decentralization of control using agent technology. A significant result of ISCM was the development of a generic Agent Building Shell (ABS) to support agent construction by providing several layers of reusable services and languages (Barbuceanu and Fox[10]). According to Sandholm [55] virtual enterprises which are formed in real-time to take advantage of economies of scale and complementary expertise can use multi-agent systems for negotiations at operative decision making level. In Sandholm [55] the authors discuss different types of contracts possible between agents in a contract net based framework. According to authors in Pancerella and Berry[46] by incorporating agents with their inherently distributed characteristics of autonomy, reasoning and goal-driven behavior, existing EI frameworks can be enhanced to support the paradigm of adaptive virtual enterprises. Integration of manufacturing systems control is an important part of any enterprise integration effort. To that end, Authors in Lin[40] and Lin and Solberg[41] show that multi-agent systems based on the contract net protocol with monetary transactions can be successfully implemented in a shop-floor environment. AARIA Baker, et al. [7] and Parunak, et al. [48] investigated large-scale resource allocation and system simulation using autonomous agents, in the context of factory scheduling. ADDYMS (Butle and Ohtsubo [14]) was one of the earliest applications of agent technology to distributed dynamic manufacturing scheduling. In this framework agents represented physical resources and a dynamic local resource allocation mechanism for dynamic scheduling was used. Lee and Lau [36] discussed a multi-agent model to enhance the performance of a dispersed manufacturing network, involving companies with different core competencies. The multi-agent model enables monitoring the information flow and task allocation among the network companies. One interesting agent-based framework for intelligent enterprise integration called CIIMPLEX was introduced by Peng et al. [51]. The system was geared towards only higher level interactions between entities, and ignored lower level activities. Chalmeta et al. [15] discussed reference architectures proposed for carrying out enterprise integration. Methods proposed to date are not mature enough and are still improving. A new reference architecture ARDIN was also introduced in Chalmeta et al. [15]. Authors also argue that a parameterized standard solution is better than a totally customized solution for a particular enterprise. It helps in future extensions and adaptation to decision frameworks of other enterprises (this counters the claim of customized solutions for every enterprise Patankar and Adiga [49]). We have developed a generic architecture which can be applied to various manufacturing enterprises for intra-enterprise integration with minor modifications. The architecture would be discussed in the next chapter. Virtual Enterprises (VEs) are a new paradigm in enterprise integration where production networks are created in real-time to service a particular customer request between different enterprises. According to Fischer, et al. [22], a virtual enterprise is a temporary, cooperative network that is formed by independent, autonomous companies to exploit a particular market opportunity. As the problems faced in formation and coordination of virtual enterprises are very similar to the ones faced in the formation of a production network between multiple production facilities and outsourcing destinations to meet customer demand, we are interested in solutions proposed in this domain. In Nigro, et al. [43] authors state that an enterprise giving autonomy to each plant in decision-making process in the planning domain, acts as a Virtual Enterprise. Petersen, et. al. [52] provide an agent-based modeling procedure for modeling virtual enterprises using the AGORA multi-agent architecture. Zhou, et al. [71] present an object-oriented technology to support production planning and control in virtual enterprises. Gjerdrum et. al. [25] apply multi-agent modeling techniques to simulate and control demand-driven supply chain network. Authors in Sadeh, et al. [53] introduce the MASCOT agent architecture for modeling and coordination of virtual enterprises which they call dynamic supply chains. Similarly, Wagner, et al. [65] describe the TAEMS agent framework for creation and management of dynamic supply chains. Zhou [70] introduce a learningbased approach for agent-oriented supply chain management. Walsh, et. al. [66] describe a combinatorial auction framework for creation of a virtual enterprise.
Auction Frameworks in Manufacturing
In a free-market based economic environment scarce resources are allocated to entities who value them the most. The mechanism which decides pricing of goods and actual allocations is called the market mechanism. In a free-market mechanism prices of goods are supposed to rise with increase in demand and fall with a decrease in demand. Most complex decision-making problems encountered in the manufacturing planning and scheduling as well as other domains involve formulation of an efficient mechanism that can be used to allocate limited resources to tasks which usually have due dates or deadlines. Free-market style mechanisms can help us in coming up simple methodologies to solve such problems (Clearwater [17]). provides a good reference to market-based systems used for resource allocation in manufacturing and allied fields. Kaihara [31] [32] introduce a virtual market-based system which can be used for supply chain management in a dynamic environment. Auctions are the most frequently used allocation mechanisms in market-based control systems. The contract-net protocol, as described in the first chapter does not stipulate a way for the manager nodes to select a particular contractor node or group of contractor nodes to accomplish tasks. Auctions provide a means to achieve that allocation in a simple and efficient manner. A very lucid description of various auction formats and their formal analysis is given in Krishna [34]. In its simplest form an auction is a mechanism in which interested parties submit bids for an item of interest which is offered for sale by a seller. The seller at the end of the bidding process selects the best bid based on a weighing criteria and the object is sold to the bidder who submitted that bid. The price at which the item is sold to the winning bidder is also decided as a part of the auction mechanism. A new type of auction mechanism known as combinatorial auctions has been recently introduced Parkes. Combinatorial auctions allow bidders to consider more than one parameter of interest as well as multiple items simultaneously. Iterative combinatorial auctions allow bidders to submit multiple bids during the course of an auction. The auction in this case, takes place in multiple rounds, where bidders are allowed to submit one bid for each round based on their eligibility to take part in that round as decided by the rules of the auction. The problem of allocating multiple goods through a single auction is covered in (Ausubel [3]; Ausubel and Cramton). The focus of our research study is to design an auction mechanism which can be used to allocate multiple components to different competing production facilities in a single efficient auction. The presence of product due dates and component precedence relations further complicate the process. Thus, combinatorial auctions provide a good way to design our auction framework. (Klemperer[33]; Krishna [34]) provide very good references on how to design a new auction mechanism for a particular application.
1. Introduction
1.1 Advanced Planning and Scheduling
1.2 Multi-Agent Systems
2. Problem Statement
3. Literature Review
3.1 Advanced Planning and Scheduling Systems
3.2 Enterprise Integration using Multi-Agent Systems
3.3 Auction Frameworks in Manufacturing
3.4 Previous Work in Multi-Facility Production Planning Problem
4. Solution Approach
4.1 Generic Contract Net Based Multi-Agent System
4.2 Hierarchical Multi-Agent Model for Planning and Scheduling
4.3 Mathematical Model of the Multi-Facility Planning Problem
4.4 The Iterative Combinatorial Auction Procedure
4.5 Accommodation of Changes in Demand Forecast during Planning Cycle
5. Results and Discussion
5.1 Validation of the Auction Mechanism
5.2 Validation of the Production Planning Approach
6. Conclusions and Future Work
7. Summary and Recommendations
GET THE COMPLETE PROJECT
A Multi-Agent System and Auction Mechanism for Production Planning over Multiple Facilities in an Advanced Planning and Scheduling System
