یک راه حل برنامه ریزی پویا محدود برای مشکل بچینگ در سیستم های تولید مدل مخلوط زمان تولید
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|25322||2006||22 صفحه PDF||سفارش دهید||محاسبه نشده|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : International Journal of Production Economics, Volume 103, Issue 2, October 2006, Pages 841–862
The batch production smoothing problem (BPSP) aims at finding appropriate batch sizes for a variety of products and sequencing the batches in such a way that their appearances are uniformly dispersed over the planning horizon. Extending the previous research work on the BPSP, this paper introduces a bounded dynamic programming (BDP) approach. Computational experiments prove that the BDP approach reduces the computational time needed to solve the problem significantly and allows larger-size problems to be solved within practical times
Mixed-model production systems enable manufacturers meet demand for a variety of products in an efficient way. The demand for each product is too low to use dedicated manufacturing lines or facilities, therefore a versatile facility is used to produce many similar but not identical products. Planning and scheduling such a mixed-model system is an important challenge that has gathered significant interest since 1960s, starting with balancing and sequencing mixed-model assembly lines (Thomopoulos, 1967 and Thomopoulos, 1970; Macaskill, 1972, Dar-el and Cother, 1975, Chakravarty and Shtub, 1985 and Dar-el and Rabinovitch, 1988). We address the operation of these systems under the just-in-time (JIT) philosophy. JIT manufacturing is based on the employment of a pull system on the shop floor, and the entire system is controlled by a schedule of the final level of operations. The schedule of the final operation determines the demand and schedule of the immediate upstream operation. Application of the pull system at every stage of the shop floor implies that the final schedule determines the demand pattern for all the operations. In the literature the problem of scheduling the final level, such that demand for the other operations are stabilized, is known as the production smoothing problem (PSP). Ideally, production smoothing aims at reducing batch sizes and creating a leveled one-piece-flow of products, parts and materials through the entire system. This ideal flow requires the end products to be dispersed over the final schedule, as uniformly as possible. For a given end product, this goal is achieved if its cumulative production amount at any time is proportional to time elapsed since the beginning of the planning horizon. In Fig. 1, the straight line demonstrates this ideal schedule concept for a given product. The actual production amount, on the other hand, increases at times devoted to that product and remains constant at times when some other products are produced. The deviation of an actual schedule from the ideal schedule is demonstrated by the gap between the lines in the figure. The PSP aims at minimizing this gap. Full-size image (24 K) Fig. 1. Ideal and actual schedules. Figure options The PSP has gathered significant interest in the last two decades. In Miltenburg's (1989) seminal paper, the problem is formulated as an integer non-linear programming problem where the objective function measures the total squared deviation between the actual and ideal schedules, for each product at each stage in the sequence. Several heuristic and exact solution methods for the problem are available in the literature (Miltenburg, 1989, Miltenburg et al., 1990, Kubiak and Sethi, 1991 and Ding and Cheng, 1993; McMullen, 1998, McMullen, 2001a, McMullen, 2001b and McMullen, 2001c; McMullen and Frazier, 2000, McMullen et al., 2000 and McMullen and Tarasewich, 2005). The most efficient exact method known so far is Kubiak and Sethi's (1991) transformation to assignment problem. In all these papers the problem has been studied for synchronized assembly lines only, where each product takes exactly one unit of processing time on every station and setup times are ignored. A variant of the PSP is batch PSP (BPSP). The seminal work addressing the BPSP is due to Yavuz and Tufekci (2004). The authors analyze mixed-model JIT production systems, where a single machine is critical in the system. The single machine can either be the final level of the production system, or a bottleneck operation that all the products go through. In contrast to the former literature on the PSP considering synchronized assembly lines, the authors generalize processing times to be arbitrary non-zero numbers and also allow setup times, which were previously ignored, to take arbitrary non-zero values. The total available time is limited, such that the ideal one-piece-flow (manufacturing the end products in quantities of one) is infeasible. Therefore, any feasible production plan should collect several copies of products into batches and decrease the amount of productive time devoted to setups. In order to create an easily implementable system and also make use of the well-established literature on the PSP, the authors develop a two-phase solution method to the problem. The first phase determines batch sizes and number of batches for the products and the second phase finds a sequence for these batches. We refer to these phases as batching problem (BP) and sequencing problem (SP), respectively. The key to this two-phase solution approach is a takt-time, which is obtained by dividing the total available time into the total number of batches to be produced. Every product, no matter if it is produced in a batch of one or multiple number of products, is processed within the takt-time. It is shown in Yavuz and Tufekci (2004) that the SP is efficiently solvable as an assignment problem. The BP, on the other hand, is NP-complete. Therefore, the authors focus on the BP, and propose a heuristic procedure for its solution. Yavuz et al. (2004) extend this work to medium-sized problems, where they propose three meta-heuristic techniques and a dynamic programming (DP) procedure for the solution of the problem. However, the authors state that the DP procedure may require excessive computational effort, and therefore may not be suitable for large-size problems. The heuristic solution methods for the BP are reviewed in Section 3. The definition of the takt-time gives the BPSP a periodic structure and makes it somewhat similar to some dynamic lot-size planning problems. To prevent any confusions, we briefly review some of the dynamic lot-size models and state several ways in which the BPSP differs from them. Two main classes of dynamic lot-size models are so-called big-bucket and small-bucket models. The capacitated lot-sizing problem (CLSP) ( Barany et al., 1984) is an example of the big-bucket models. In the CLSP, one decides what to produce in each period. Several products can be produced in the same period, if the capacity allows. Thus, products can be produced in advance in order to save setup costs obeying the capacity constraints. Amongst the small-bucket models are the discrete lot-sizing and scheduling problem (DLSP) ( Salomon et al., 1991), the continuous setup lot-sizing problem (CSLP) ( Karmarkar and Schrage, 1985), the proportional lot-sizing and scheduling problem (PLSP) ( Drexl and Haase, 1995) and the general lot-sizing and scheduling problem (GLSP) ( Fleischman and Meyr, 1997). These small-bucket models differ from each other in (1) the number of products that can be produced in a period, and (2) the flexibility in consuming the productive time in each period. The DLSP and CSLP allow production of at most one product in a period, while the PLSP allows up to two products and in the GLSP, the number of products is limited to a user-defined parameter. The DLSP requires consuming all the productive time in a period, while the other models allow idleness of the resources. A more recent model combining the properties of big- and small-bucket problems is the CLSP with linked lot sizes (CLSPL) ( Suerie and Stadtler, 2003). In the CLSPL, multiple products can be produced in a period and a setup state can be carried from one period to the next. The dynamic lot-size models are advanced MRP-based planning tools which minimize the summation of the setup and inventory carrying costs, whereas the BPSP is a JIT-based planning tool which assures viability of the JIT system at all levels. In this regard, the BPSP differs from all the dynamic lot-size models, in the objective function. The BPSP aims at smoothing the appearances of the products in the schedule, thus stabilizing the demand for the parts, components and materials at the sub-levels. The BPSP is a tool that helps JIT manufacturers to achieve the ultimate goals of stable production plans and low inventory levels. Another difference between the BPSP and the above models is related to the planning horizon and demand structures. All the dynamic lot-size models assume a planning horizon, which is already divided into periods and the demands for the products vary between the periods, where both the periods and demands are known a priori. The BPSP, on the other hand, assumes known demands for the entire planning horizon, not the periods. The periods are established by the BPSP as a part of the decision. This is a key difference which hinders us from using a modeling and solution approach developed for a dynamic lot-size model. This paper extends the earlier work on the BPSP. We propose a bounded DP (BDP) solution method that combines features of DP and branch-and-bound methods to successfully handle much larger size problems (see Morin and Marsten, 1976 for details on BDP). In implementing the DP procedure as suggested by Yavuz et al. (2004), we propose several bounding strategies which eliminate significant amount of states at each stage and reduce the computational burden significantly. This paper is structured as follows. In Section 2, we first introduce the problem based on a real-life example and then formulate the problem as an optimization model. In Section 3, we review currently existing heuristic solution procedures to the BP. In Section 4, we develop our solution method, consisting of a DP formulation and several bounding strategies. In Section 5, we present our computational study. We conclude with Section 6 where we summarize our research findings.
نتیجه گیری انگلیسی
This paper presents an improved solution method to the BPSP, which is a problem encountered in the context of planning and control of mixed-model JIT manufacturing systems. The BPSP is a computationally hard problem. The paper adopts a two-phase solution methodology, where finding appropriate batch sizes is the harder phase. The paper first builds a mathematical formulation of the problem, and then presents a DP approach to solve the problem. Analyzing the DP procedure and structural properties of the problem, an improved solution procedure, BDP, is proposed. The computational results show that the improved method solves the problem approximately 8 times faster than the original DP method. This is a significant improvement, proving the efficacy of the proposed bounding strategies. The results also show that the improved method can be used to solve larger size problems. Up to 50 product problems are solved in the computational study, yielding a maximum solution time of approximately an hour. The comparison of the proposed BDP method to the existing heuristic methods brings a trade-off problem between computation time and solution quality. In cases where the production planning is static, i.e. the batching decisions are given only once in a planning period, the proposed BDP approach is practical and can be successfully applied by the practitioners in the field. In the dynamic production planning cases, using one of the heuristic solution methods, is a good way of re-solving the batching problem in short time. The computational study analyzes the experimental factors with respect to their effects on the solution time, as well. An important finding is that the computational time of the BDP procedure increases with the diversification level of the products. We consider two distinct production systems, one producing a collection of products with similar setup and processing time requirements, whereas the products in the other system largely vary in time requirements. Our computational results show that the BDP approach takes less computational time on the first type of the systems described above. That is, a mixed-model manufacturing system is controlled easier, if the products are similar. In the extreme case, the products would be identical, and planning such a system could be even easier. Our final concluding remark is on the relationship between the flexibility in planning and computational time of the BDP procedure. Subtracting the time required to process all the products from the total available time, we obtain total time that can be devoted to setups. The ratio between this time and the average setup time of the products is critical in determining the flexibility we have in planning the system. As this ratio increases, the number of batching options also increase. Due to the enumerative nature of all the DP approaches, the BDP procedure also takes more time in this case. As the critical ratio decreases, on the other hand, finding a feasible solution becomes more important. The planner loses flexibility as not many feasible solutions can be found. However, the BDP procedure is found to work faster in this case, as well.