برنامه ریزی تولید کل مبتنی بر فعالیت با گسترش ظرفیت در سیستم های تولید

This paper builds a mixed integer linear programming (MILP) model to mathematically characterize the problem of aggregate production planning (APP) with capacity expansion in a manufacturing system including multiple activity centers. We use the heuristic based on capacity shifting with linear relaxation to solve the model. Two linear relaxations, i.e., a complete linear relaxation (CLR) on all the integer variables and a partial linear relaxation (PLR) on part of the integer variables are investigated and compared in computational experiments. The computational results show that the heuristic based on the capacity shifting with CLR is very fast but yields low-quality solution whereas the capacity shifting with PLR provides high-quality solutions but at the cost of considerable computational time. As a result, we develop a hybrid heuristic combining beam search with capacity shifting, which is capable of producing a high-quality solution within reasonable computational time. The computational experiment on large-scale problems suggests that when solving a practical activity-based APP model with capacity expansion at the industrial level, the capacity shifting with CLR is preferable, and the beam search heuristic could be subsequently utilized as an alternative if the relaxation gap is larger than the acceptable deviation.

Aggregate production planning (APP) is used to determine optimal production and inventory levels to meet the demand for all products over a finite planning horizon with limitations of capacities or resources (Graves, 2002 and Nam and Logendran, 1992). As a planning task at upper level in hierarchical planning systems, APP is usually made at an aggregate level, where all products are grouped into several aggregated items and the model is often a linear optimization problem. Although some production plans are integrated with lot-sizing and scheduling problems (Gelders & Van Wassenhove, 1981), APP seldom considers the limitation of the detailed planning problem and focuses instead on relevant long-term factors (Axsäter, 1986), typically the monthly or quarterly demand and the production of aggregated items. Most APP models assume that production capacity remains unchanged and seldom concern themselves with capacity planning issues. However, capacity changes often take place in practical production systems and therefore lead to the capacity expansion problem. Since Manne (1961) proposed the first model for the capacity expansion problem, this topic has been extensively studied in recent decades (Julka et al., 2007 and Rajagopalan, 1998). Examples can be found in the automobile industry (Eppen, Kipp, & Schrage, 1989), communication networks (Gendreau, Potvin, Smires, & Soriano, 2006), the chemical industry (Ahmed and Sahinidis, 2000, Liu and Sahinidis, 1995 and Liu and Sahinidis, 1997), the semiconductor industry (Chou, Cheng, Yang, & Liang, 2007), etc. Capacity expansion models mainly consider capacity adjustment and do not focus their attention on resource allocation, product mix, and inventory level, which are often the concern of production plans. As a strategic-level plan, a capacity expansion decision cannot be used directly as an instruction for the medium-term APP. As a result, quite a few studies combine the aggregate production planning problem with the issue of capacity expansion (Rajagopalan and Swaminathan, 2001 and Van Mieghem, 2003). Bradley and Arntzen (1999) proposed an APP model to make a tradeoff between inventory level and capacity expansion in a multi-stage manufacturing system. Their model does not require that products be aggregated but assumes that capacity scenarios are predetermined. Rajagopalan and Swaminathan (2001) proposed a coordinated production planning model to optimize capacity expansion, production planning, lot-sizing and inventory management simultaneously. In their model, the production system is modeled as a single-stage production line. Atamtürk and Hochbaum (2001) presented capacity acquisition models considering subcontract, production, and inventory to satisfy non-stationary deterministic demand over a finite horizon. Generally, the model of production planning with capacity expansion focuses on either the capacity adjustment or the allocation of the changeable resources to production activities with the aim of yielding products that satisfy customer demand. This builds a better connection between the capacity investment at strategic level and the production plans at operational level. However, most of the existing models of APP with capacity expansion do not take into account product structure or manufacturing processes. Moreover, they restrict themselves to a single-product environment or a one-stage case, and they frequently assume that all items have been transferred to equivalent final products without consideration of inventory, semi-manufactured products, or work in process (WIP). However, this is not applicable to multi-stage production systems where multi-level structures of products and production processes should be considered. With the development of manufacturing technologies and analytical methods such as activity-based costing (ABC) (Cooper and Kaplan, 1988 and Gupta and Galloway, 2003) and cellular manufacturing (Balakrishnan & Cheng, 2007), several production planning models have considered production processes based on the production network of activity centers. Malik and Sullivan (1995) developed a mixed integer programming model that utilizes ABC information to determine the optimal product mix without the assumption of a known unit cost for each product before solving the product mix problem. Schneeweiss (1998) presented a general production-investment problem based on ABC and evaluated the applicability of ABC as a planning instrument. Shapiro (1999) built a comprehensive model that uses ABC and mathematical programming to determine strategic resource planning including facility opening and activity operation level. Kee and Schmidt (2000) modeled the selection of production-mix with the capacity constraints of production-related activities integrating ABC. Singer and Donoso (2006) developed a model to assess the feasibility of prospective production plans. In the model, the unit product cost is calculated through ABC and the production system is regarded as a network of activities connected by physical flows. The above studies show that under the ABC system, the APP model can optimize product mix policy for final products and semi-manufactured products simultaneously, with manufacturing processes, activity capacity constraint, and product structure considered. Similarly, all of these factors can also be integrated in APP with capacity expansion if we regard activity centers as manufacturing nodes whose capacity is expanded. A few studies on this topic can be found in the literature. Tsai and Lin, 2004 and Tsai and Lai, 2007 developed ABC-based product mix decision models incorporating capacity expansion, where process-level activity costs are assumed as the stepwise fixed cost and the costs of facility-level activities as the common fixed cost. Kee (2008) examined the usefulness of product and variable costs for pricing, product mix, and capacity expansion taking into consideration economies of scope in an ABC system. These models did not consider the product structure or semi-manufactured items because they are based on the ABC accounting system, not on production process systems. Gupta (2001) pointed out that a process map, i.e., a product-process structure, can be constructed to show graphically the relationship of each activity to the products if a process-oriented activity-based management system is developed. Zhang and Wang (2009) proposed a scenario-based stochastic capacity planning model taking account of product structure, production and inventory levels, and activity processes. However, they did not consider fixed costs of capacity expansion and an algorithm for solving their model has not been developed. In this study, we first formulate an MILP model for the problem of APP with capacity expansion in a manufacturing system with multiple activity centers, and then develop an effective approach to solving the proposed model. In the model formulation, the product configuration and the physical production flows among activity nodes are brought together, which provides a tool that supports decision makers in considering the product-process structure when determining APP plan with capacity expansion. Moreover, we divide the investment cost for expanding capacities into two parts: fixed cost and variable cost, and we constrain the amount of expanded capacity to be an integer multiple of one unit of activity cell. Next, we investigate the capacity shifting approach with linear relaxation for the solution. A computational study shows that in some cases, the capacity shifting with complete linear relaxation (CLR) on all the integer variables does not always result in a high-quality solution because the relaxation does not yield a tight lower bound. Therefore, we consider relaxing only part of the integer constraints, called partial linear relaxation (PLR), to yield a tight lower bound albeit at the cost of much greater computational time. Finally, we develop a hybrid heuristic by combining capacity shifting with beam search for solving the PLR of large-scale problems. Computational experiments show that the hybrid heuristic can yield very high-quality solutions within acceptable CPU time. The rest of the paper is organized as follows. In Section 2, we describe the manufacturing system with multiple activity centers and build the model of activity-based APP with capacity expansion. Section 3 briefly explains the basic framework of the beam search algorithm. In Section 4, the detailed heuristics are introduced, including the capacity shifting with LP relaxation and the hybrid heuristic combining the capacity shifting approach with the beam search algorithm. In Section 5, computational experiments are conducted to evaluate the performances of the proposed heuristics. In the final section, we present some conclusions.

In this paper, we build an aggregate production planning model considering capacity expansion for the activity-based manufacturing system. The factors considered in our model include production and inventory costs, purchasing cost and the storage cost of activity cells, the common and individual fixed costs of capacity expansion, time-varying activity parameters, and age effect on activity cells, etc. Our model is a general formulation of the APP with capacity expansion in activity-based manufacturing system, which can be adapted to different cases. For instance, fixing the capacity parameters yields a pure APP model for the activity-based manufacturing system. Omitting At can be used in the case of no common fixed cost considered during capacity expansion and constraining parameters do not change with time periods and cell age can be adaptive to the case of a static environment. Or the model omitting Hkt can be employed in cases without the storage cost of idle cells. To solve the model, we firstly investigate the heuristics based on capacity shifting with complete linear relaxation (CLR) and partial linear relaxation (PLR), respectively. A computational study shows that the capacity shifting with CLR is very efficient in terms of computational time but cannot guarantee a high-quality solution. By contrast, the capacity shifting with PLR can yield high-quality solution but is time-consuming. Therefore, we propose a hybrid heuristic combining the beam search algorithm with the capacity shifting approach, which results in a better tradeoff between computational time and solution quality. Especially, the proposed beam search tree constructed through shifting the capacity of individual activity center can also be applied to constructing beam search-based heuristics for other models of APP with capacity expansion. Moreover, the computational study suggests that to solve a practical APP problem with capacity expansion, the capacity shifting approach with CLR should be employed to perform a test at first, and then the beam search heuristic can subsequently be used if the relaxation gap of CLR is larger than the acceptable deviation. The most possible extension of the proposed model is to integrate more detailed planning, e.g., lot-sizing and scheduling. This will lead to a mixed integer nonlinear programming model that is more intractable because of entanglement with capacity expansion, where some new solution algorithms are needed. Moreover, although this study is capacity expansion relevant, the proposed APP model is not recommended for making the long-term capacity planning decision because capacity planning is more concentrated in factors of longer time period, e.g., the development of technologies, uncertainties from market, etc. As a result, adapting the model fit for the long-term capacity planning decision leads to another possible extension of this study.