Toward a Distributed Paradigm for Manufacturing Logistics
Abstract: Most planning and optimization methods in manufacturing logistics assume centralized or hierarchical decision making using monolithic models. Motivated by increasing needs in the industry to coordinate diverse decision processes and systems, we investigate distributed paradigms for planning and optimization problems. The new paradigm addresses decision processes and mechanism design issues such as asynchronism, incentive compatibility, preference elicitation, information asymmetry, and solution robustness. Our efforts to-date focus on structural mappings exist between optimization and competitive market mechanisms wherein agents or coalitions of agents compete base on local utilities, payoff methods, and market clearing methods. Building upon the rich literature in optimization, game theory, and market equilibrium analysis, we investigate the advantages and limitations of this distributed paradigm on a variety of problems in manufacturing logistics. Topics of study include distributed scheduling, multi-facility production coordination, supply chain demand modeling, forecasting, incentives and intra-company capacity allocation, and production/transportation coordination. We develop our analyses based on realistic scenarios in the semiconductor and the automotive industries.
Introduction: Manufacturing competitiveness has escalated globally in the past two decades. Manufacturing firms experience increasing pressure to improve production efficiency, responsiveness to market changes, and substantial cost reduction. This increasing pressure is particularly evident in industries that have short product life cycles and complex supply structures, as is the case in automotive, electronics and semiconductor manufacturing. While the productivity and efficiency of manufacturing systems have been studied extensively, broader logistical issues spanning multiple levels of manufacturing facilities or multiple firms are not well understood. Manufacturing logistics is an emerging area of research that refers to "all planning, coordination and support functions required to carry out manufacturing activities between the point where end-item customer demands are determined, and the point where they are fulfilled."[1] Among various topics in manufacturing logistics are planning and coordination of production across multiple facilities, and integration issues between manufacturing and other functional areas such as marketing, transportation, distribution and warehousing.
This research focuses on the study of a distributed decision paradigm for manufacturing logistics. As a manufacturing entity seeks coordination with their internal or external customers and suppliers, it is quickly confronted with difficulties associated with different operational conventions, locally specific constraints, conflicting objectives, and misaligned incentives. If some form of centralized coordination is to be formed, significant time and resources must be first devoted to iron out these differences. However, as the level and the scope of coordination increase, the notion of centralized coordination breaks down at a point where the system complexity reaches its limit, and some form of decentralized coordination with local autonomy become unavoidable. Hierarchical decision making has been suggested to cope with the system complexity through decomposition, aggregation and feedback mechanisms. We propose a different approach to this problem using the notion of distributed decision making and market equilibrium. We believe that most decision entities in manufacturing have their own unique perspectives and economic incentives. Rather than forcing all decision entities into some unified decision structure, it may be helpful to view them as autonomous agents acting on their own behalf. Through the use of competitive market mechanisms these decision agents may be coordinated based on a much simpler set of policies while their long-term behavior can be predicted and modeled by various equilibrium conditions.
A main advantage of the new approach is the drastic simplification in information management. A basic paradigm in conventional Enterprise Resource Planning (ERP) system is one that seek "total visibility" of system details in a top-down, hierarchical manner. This is accomplished by maintaining painfully detailed information of all perceivable aspects of the organization using sophisticated information and database management systems. This information must be kept up-to-date since it serves as a basis for decision making throughout the organization. In a distributed system, since agents make locally autonomous decisions based on privately owned information and local preference/constraints, centralized information management can be decoupled and the monitoring and maintenance of information can be segmented and manipulated at a far more efficient manner. Analogous to the fast growing World Wide Web platform, this new paradigm facilitates interconnected software agents to communicate and to reconciliate their decisions through a universally agreed upon domain of information exchange.
Research Topics and Progress To-Date: Our research to-date focuses on three main aspects (1) theoretic foundations of distributed decisions, (2) specific topics in manufacturing logistics, and (3) industry case study. In the following, we summarize the essence of these activities and provide further details in working papers and technical publications that can be viewed on-line.
Theoretic Foundations:
Mapping between Optimization and Distributed Market Mechanisms [2][3][4]: Starting with a NP-hard combinatorial optimization problem in resource scheduling, we show that a market mechanism called combinatorial auction can be used to generalize this problem from its classical setting. Viewing the system as coalitions of resource and job agents in a competitive market, we establish linkages between combinatorial auction and two Lagrangian-based decomposition methods, propose an incentive compatible auction and market clearing mechanism, and explore the implications of equilibrium and global optimal solutions in practice. Using the same constructs, we examine the multi-level multi-facility lot sizing models, vehicle routing and scheduling models, capacity planning and capacity expansion models, and we explore the implication of distributed decision in scenario based stochastic programming models.
Theoretical Analysis of Distributed vs. Centralized Planning [5]: Using an extension of an organizational model by Malone and Smith, we derive conditions under which one would prefer a centralized planning system to that of a distributed system. Under a specific construct, we show that as one varies the arrival rates of work, failure rate of agents, etc., one can map out the regions in these parameter spaces where the distributed approach is preferred to the centralized one. These results establish basic insights for us to understand the advantages and limitations of distributed decision using market based systems.
Incentive and Mechanism Design Problems in Distributed Decision Making [6]: Consider multiple decision entities in a manufacturing setting each has different economic incentives and each owns different subset of information relevant to decision making, we propose a game theoretic framework to model the strategic behavior of these decision entities. Our aim is to develop an incentive mechanism that enforces truthful information exchange among these decision entities. We characterize the structure of a reward function under different solution concepts and under different conditions of information availability.
Topics in Manufacturing Logistics:
Distributed Scheduling [2], [7], [8]: We examine the use of different market mechanisms for job shop scheduling and compare our results to conventional optimization-based benchmark. In [2], we define a combinatorial auction mechanism for due-date based scheduling where job agents compete for resources. We characterize combinatorial auction by selling procedures (price directed vs. winner coalition), auction protocols (standard Walrasian vs. adaptive t tonnement), and payment functions (regular vs. augmented t tonnement) and show that the well-known Lagrangean Relaxation approach can be viewed as a specific version. We show potential advantages of these different versions of combinatorial auction using job shop scheduling examples. In [7] we study methods that improve scheduling robustness under uncertain disturbances and dynamic shop conditions. We introduce stochastic constraints to the job agent subproblem which capture a priori information concerning future uncertainty. Intensive computational testing show that the proposed scheme significantly outperform its deterministic counterpart without significant computational burden. In [8] we propose a market-based system for job shop scheduling. Instead of having job agents competing for resource we examine the setting where resource agents bid for jobs. This particular perspective is important for service-oriented scheduling where worker resources bid for work given their availability. Currently we are investigating other distributed scheduling models such as track scheduling in railroad applications, and production line scheduling. We are also investigating software implementation issues of distributed scheduling in a web-based environment.
Multi-Facility Production Coordination [3] [9]: In this study we focus on production planning problems that requires the coordination of mutliple manufacturing facilities sharing similar production capabilities. Motivated by the need for a responsive production and capacity management framework in the electronic and semiconductor industries, we study lot sizing type models which facilitate these decisions. We organize this line of study by a three-stage process. In the first stage, we focus on a medium-range production planning model which coordinate the production of multiple alternative facilities [3]. We propose item-based and facility-based decompositions to the model which form the basis for decision making from the viewpoints of product managers and production managers. In the second stage, we revise the deterministic model to include randomness using a scenario-based stochastic programming model [9]. We develop the notion of local scenario analysis which allows local decision entities to contemplate their own local constraints and possible scenarios while taking into account the scenarios confronted by others. In the third stage, we propose a distributed decision environment designed based on mathematical decomposition and a form of equilibrium established among product (item) and resource (capacity) agents. Main issues include reducing communications among decision agents, asynchronism, and the correspondence between global optimality and equilibrium conditions.
Supply Chain Demand Modeling [10] [11] [12]: In this study we focus on the information aspects of coordination. In specific, we are interested in the way demand information is processed, and its impact on supply chain order behavior. Since the demand and order information are controlled by various decision entities in the supply chain, different policies adopted in interpreting the information, and in projecting future trends from this information could have tremendous impact on the way a supply channel behaves. Our objectives in this study are three-fold. First is to define and develop the demand analysis required to analyze manufacturing supply chains that are driven by structured order processing and production planning systems. Second is to provide insights to the planning and operation within manufacturing supply chains confronted with structured interactions and dependencies. And third is to examine demand behaviors in technology driven markets where a more volatile market demands dominates while an integrated order processing and planning system do not exist. We concentrate our efforts on the demand dynamics of manufacturing supply chains. The demand dynamic is analyzed at each tier of the supply chain, and across multiple tiers as demand propagates. We first model supply chain demand process attempting to gain insight into its overall effect on production operations. In [10], we present a model which describes the decision process that drives supply chain operations, while providing the basis for analyzing the effects of various policies on supply chain performance. Specifically, we look at the effects of order batching, multiple schedule releases, product structure and component sharing, and capacity levels in manufacturing facilities. We study how and when the variation in orders along a supply chain increases, and identify the management implications related to these planning and operation issues. The analyses in [10] are theoretical by nature. In [11], we report on a set of computational experiments that further explore the above issues. In addition, we explore how manufacturing planning decisions can be made robust to disturbances by exploiting the information embedded at both preceding and succeeding tiers in the supply chain. A more robust estimation of demand is needed in intra-supply chain integration because it is the critical piece of information that is communicated along a supply chain. This piece of data is known to vary randomly and dynamically over time.
The development in [10] and [11] assume the existence of an integrated order processing and production planning system, as is the case in the automotive industry. In [12] we further our demand modeling by concentrating on a distinctly different, technology driven market, where a subset of leading indicator products provides an advance indication of demand swings. Based on a realistic need in the semiconductor industry, we develop a demand model which make use of the leading indicator to construct future demand scenarios. Quite different in sprit from the above demand models, this model defines a scenario tree that can be used for decision making using stochastic programming. We demonstrate the use of this scenario construction procedure using real semiconductor data.
Production and Transportation Coordination [4]: In this line of study, we consider the notion of distributed decision making in the context of functional coordination. In specific, we consider the integration of production and transportation logistics. We focus our attention on the fundamental tradeoff between costs and level-of-service in production and transportation coordination. We first propose a model that integrates production planning and transportation routing at the operational level. Our method allows optimization to reconcile the viewpoints from transportation and production planning. The process of optimization operates similar to a negotiation process between a set of interrelated production facilities and a thrid party logistic provider. We introduce basic production and transportation models that are tailored to this particular integration and show the value of the integration using a Lagrangean decomposition scheme. The above analysis provides another form of mapping between optimization and distributed decision-making. We are currently studying coordination issues associated with different types of production and transportation models at a strategic level.
Industry Applications: We developed and implemented a strategic capacity planning model at the microelectronics division of Lucent Technologies. According to the administrative structure of the firm there are several strategic business units (SBU) associated with major product lines. These SBUs are responsible for marketing and providing input to demand forecasting activities performed at the headquarters. The facilities produce silicon wafer for various IC products. The firm owns and operates several plants located around the world capable of producing a wide range of microelectronics technologies. The products span a wide range of ICs that are used in network communications, wireless communications, consumer electronics, PCs, and Workstations. The capacity planning decisions involve two important parameters: demand forecasts by technology types, and capacity estimations by facilities. Due to the short product life cycles, capacity expansion is not always justified and one must consider outsourcing. The capacity planning problem at Lucent can be described as determining the capacity configuration (i.e., the mix of allocating existing technologies, setting up capacity expansions, and outsourcing agreement) for the next k planing period such that the total cost of meeting future demand is minimized.
The capacity planning decisions are used for planning purposes such as purchasing raw materials, machinery and personnel acquisition. Capacity expansion decisions must be made way ahead of time and expansions are to be completed before planned production begins. This means that these decisions are implemented before uncertainty unfolds. Similarly, purchasing and outsourcing decisions lead to contracts with suppliers before the beginning of the planning period. Nonetheless, capacity configuration decisions must be adjusted throughout the year in order to accommodate unforeseen changes in both capacity and demand. Demand uncertainties come not only from the dynamic nature of the semiconductor market but also from biases of the SBUs. On the other hand, capacity uncertainties can be attributed to regular disturbances in system operations as well as biases introduced by production management at the facilities.
The above capacity-planning problem introduces several interesting real-world issues concerning incentives and distributed decision making. For instance, since the SBUs are evaluated on the basis of their yearly revenue (regardless of the accuracy relative to the forecast), product managers may have the incentive to inflate the demand figures in order to reserve capacity for his products. On the other hand, production managers at some facilities may have the incentive to underestimate their capacity in order to avoid over committing themselves in the case of uncertain yields or unexpected failures, whereas others may overestimate their capacity in order to paint a rosier picture of their profitability. The information distortion invariably leads to higher operating cost. In [6], a theoretical analysis is provided for the analysis of different incentive mechanisms. We are currently evaluating capacity planning and rewarding schemes that eliminate the incentive to distort information.
Acknowledgements:
The research is supported by National Science Foundation grant DMI-9634808, U.S. Air Force, Lucent Technologies, and Ford Motor Company.