راه حل برنامه ریزی پویا برای مسئله بچینگ در جریان کارگاهی زمان تولید

Mixed-model manufacturing systems are widely used by companies, in order to meet the customers’ demand for a variety of products, in an efficient way. This paper is concerned with a special class of mixed-model manufacturing systems: flow-shops. In a flow-shop, each product has to be processed by a number of machines, following a common route. We study the production smoothing problem under presence of non-zero setup and processing times which also vary among the products. We split the master problem into two sub-problems which are concerned with determining the batch sizes and production sequences, respectively. We develop a dynamic programming procedure to solve the batching problem, and suggest using an existing method from the current literature to solve the sequencing problem. We conduct a computational study and show that our solution approach is effective in meeting the JIT goals and efficient in its computational requirements.

This paper is motivated by a leading electronic contract manufacturer’s production facility in St. Petersburg, Florida. A multinational corporation in the business of contract manufacturing for electronic components operates the facility under consideration. Recent trends in the market indicate that the contract manufacturing industry is transforming from the traditional high volume low mix production, to low volume high mix production. The equipment used in the processes are worth millions of dollars, thus dedicating separate production lines to different products is not profitable. Therefore, the lines are operated as mixed-model production lines. Also, the volumes are so low that no distinct product can be manufactured on a line for a long period, such as a week. On the contrary, the production runs are short enough to require several changeovers in a day. St. Petersburg facility has two main flow lines, where the final products are assembled. The flow lines are identical and each consist of the following units: board loader, board printer, glue dots, HSP #1, HSP #2, GSM #1, GSM #2 and re-flow. Although there exists a line structure and the line performs the assembly of the final products, these lines are not assembly-lines in the traditional sense. Different machines have different setup and processing times for different products. Furthermore, setup times are significant. The production line is illustrated in Fig. 1. The arrows in the figure demonstrate the flow of products. The machines process products in the same order. That is, the environment is a permutation flow shop. We will call the environment a flow shop in the remainder of the paper. Full-size image (3 K) Fig. 1. Illustration of the production line under consideration. Figure options Above figure illustrates the final level of operations, i.e., it is the final link of the chain which converts the semi-products manufactured by the preceding operation levels (machines, shops or lines) into end-products. The production facility is operated under the just-in-time (JIT) manufacturing philosophy. Running such a mixed-model manufacturing system under the JIT philosophy is an important challenge which has been subject to research for the last two decades. JIT philosophy requires employing a pull system on the shop floor and a multi-level pull type production system is controlled by scheduling the final level only. The production schedule of the final level determines the demand for its immediate upstream operations and eventually the entire production system. In order to successfully operate the system, demand for the upstream operations should be stabilized. This implies that the end products should be dispersed over the schedule, as uniformly as possible. In the ideal case, appearance of a given product in the schedule is constant over time, or synonymously, cumulative production amount of a product is proportional to time. The problem of finding such schedules is known as the production smoothing problem (PSP). The PSP has been studied mainly on synchronized assembly lines where each product takes exactly one unit of processing time and setup times are ignored. In such an environment, any possible permutation of products gives a feasible sequence and the problem reduces to uniformly dispersing the products over the sequence. However, as illustrated by our motivating example, there exist many different manufacturing systems in real life which are far from being synchronized assembly lines. In this paper, we focus on flow shops and propose a methodology to achieve smooth production in flow shops. In order to make use of the literature established for the PSP in synchronized assembly lines and constructing a flow shop system which can be operated easily, we define a takt time. Each product, no matter if it is processed as a single unit or in a batch of multiple units, should be processed within this takt time, on every machine. In other words, with every beat of the clock (the takt time), each job moves to its downstream operation. In this structure, the takt time can be treated as the time unit and the problem of finding smooth production sequences reduces to the same problem arising in synchronized assembly lines. We mathematically formulate the sequencing problem (SP), refer to the existing literature for its solution and suggest a reduction to the well-known assignment problem which then can be solved in polynomial time, in terms of the number of positions in the sequence. However, due to the presence of setup times, every possible permutation of single units of the products may not yield a feasible sequence. Therefore, the products might need to be processed in batches, where a batch is defined as a collection of one or more units of the same product. This brings another problem into the picture: the batch sizes and number of batches for each product and the takt time should be determined before the sequencing phase. We call this primary problem as the batching problem (BP). We build an optimization model, whose objective function is a lower bound for the SP, which helps in finding the batch sizes that lead to a good solution in the sequencing phase. Being an integer nonlinear programming problem with nonsmooth nonlinear functions in both the objective function and the constraints, the BP is a hard problem. With reduction from the subset sum problem (SSP), we show that the BP is NP-hard. Note that our approach to solve the PSP consists of two subproblems, which are subsequently solved. In this regard, we name our approach a two-phase approach. We develop an iterative dynamic programming (DP) procedure which sequentially solves a number of DPs and reports the best solution obtained from these DPs as the optimal solution to the BP. We conduct computational experiments and show that the suggested DP procedure can have extensive time requirement for even relatively small problems. We further investigate the structural properties of the problem and the underlying network structure of the DP formulation, and develop some bounding strategies to speed up the procedure. The remainder of this paper is organized as follows. Section 2 presents a review of existing literature in the area. In Section 3, we formulate both the SP and BP and reveal important properties for their solution. In Section 4, we propose a DP procedure to solve the BP and develop bounding policies to improve the running time of the proposed DP procedure. In Section 5, we present the design and the results of the computational study. Finally, in Section 6, we give the conclusions from the study and point future research directions

This paper has developed a new methodology to solve the production smoothing problem arising in mixed-model JIT flow-shops. The methodology is found effective with respect to JIT goals, as well as computationally efficient. The computational results show that, for the exact solution of the batching problem, our DP procedure with the bounding policies can be used to solve medium sized problems, within several minutes. Considering that, the batching problem is a design problem which has to be solved once per planning period (e.g., a month), a longer time (e.g., an hour) can be devoted to the procedure for optimally solving larger problems. Testing the proposed algorithm on larger problems is a possible future research direction. Also, heuristic methods can be developed to reduce the number of DPs solved. In such a case, large problems can be solved to get near-optimal solutions within practical times.