تعیین اندازه دسته تولید بر روی یک ماشین ناقص منفرد : مدل های ILP و توسعه FPTAS

A single-machine multi-product lot-sizing and sequencing problem is studied. In this problem, items of n different products are manufactured in lots. Demands for products as well as per item processing times are known. There are losses of productivity because of non perfect production. There is also a sequence dependent set-up time between lots of different products. Machine yields and product lead times are assumed to be known deterministic functions. The objective is to minimize the cost of the demand dissatisfaction provided that the total processing time does not exceed a given time limit. We propose two integer linear programming (ILP) models for the NP-hard “fraction defective” case of this problem and compare effectiveness of their ILOG CPLEX realizations with a dynamic programming algorithm in a computer experiment. We also show how an earlier developed fully polynomial time approximation scheme (FPTAS) and one of the ILP models can be extended for a more complex case.

We study a problem of lot-sizing and sequencing for n different products on a single machine. The finished product can be defective, and thus rejected. Demands for non-rejected (adequate quality) items of all products are known in advance. A sequence-dependent set-up time is required between items of different products to reconfigure the machine. The machine can break down, in which case a repair time is needed. The objective is to find a sequence of lots and their sizes such that the total demand dissatisfaction cost is minimized under the condition that the total processing time does not exceed a given time limit T0. Demand dissatisfaction cost is a linear function of the quantities of unsatisfied demands of all products. We denote this problem as P-Cost. Motivation for this problem comes from our experience in planning of an automated manufacturing line (Dolgui, Kovalyov, & Shchamialiova, 2011) of several types of Printed Circuit (PC) in electronic industry. This PC production line normally works with no human operators other than the maintenance team. There is no buffers between machines, so this line can be considered as a single machine. A production schedule is made for 24 h to satisfy given 1-day demands, and it is repeated every day. It specifies lot sizes for all PC types and a sequence of lots. The main difficulties are the high defectiveness rate – from 20% to 40% depending on the type of the PC, and the line breakdowns – mean time to failure for different pieces of equipment varies between 100 and 1000 h and mean time to repair is about half an hour. A similar situation is described in Sikora, Chhajed, and Shaw (1996). A time diagram for the flow of items at the machine output is given in Fig. 1. There is set-up times between lots of products including a set-up time before a first lot. Normal processing is interrupted by a single breakdown for each of two lots represented (the first lot is in green and the last lot is in blue), there is one defective item in the first lot and two defective items in the last lot. As the planning horizon is limited by T0 (24 h in the industrial case), the time is not enough to finish the last lot, so two items will not be processed (items with lateness). The quantities of good items for all lots are compared with demands, the dissatisfaction cost will be incurred for the lots were demand is greater than the quantity of good items. Full-size image (29 K) Fig. 1. An item flow time diagram for line output. Figure options Problem P-Cost belongs to the general field of lot-sizing and scheduling. A survey of deterministic lot-sizing and scheduling problems can be found in Drexl and Kimms (1997). In Potts and Kovalyov (2000) a review of scheduling with batching was given. Papers of Zhu and Wilhelm (2006) as well as Allahverdi, Ng, Cheng, and Kovalyov (2008) contain literature on scheduling with set-up times and costs. An earliness-tardiness lot-sizing and scheduling problem to minimize the sum of setup, holding and tardy costs was studied in Supithak, Liman, and Montes (2010). Additional results for the deterministic lot-sizing and scheduling problems can be found in Drexl and Haase, 1995, Sikora, 1996, Meyr, 2002, Toso et al., 2009, Dolgui and Proth, 2010 and Dolgui et al., 2010. Our model assumes that the machine can produce defective items and can break down. Lot-sizing and scheduling problems with uncertain product lead time and machine yield are also considered in a number of papers. The most cited survey of lot-sizing problems with random yields was given by Yano and Lee (1995). A number of lot-sizing problems with random yield were reviewed by Grosfeld-Nir and Gerchak (2004). Lead time uncertainty for assembly systems were investigated by Dolgui and Ould-Louly, 2002 and Ould-Louly and Dolgui, 2004. A state of the art for the supply planning under uncertainties in the case of random demand and lead time in a Manufacturing Resource Planning environment is given by Dolgui and Prodhon (2007). A method to model machine breakdowns using a renewal process can be found in (Dolgui, 2002). A problem most similar to ours is studied by Dolgui, Levin, and Louly (2005), where the authors suppose that random yield can be characterized by Bernoulli’s law and machine breakdowns can be modeled using renewal process. Authors decompose their NP-hard problem into three sub-problems and propose a dynamic programming algorithm to solve the lot-sizing part of the original problem. In this paper, in contrast, we mainly consider the “fraction defective” case, in which fi approximates an average proportion between defective and adequate quality items of product i, and R(x) approximates an average proportion between total machine repair time and total manufacturing time. In this case, functions fi and R can be easily deduced from classic process indicators such as defectiveness rates, mean time to failure and mean time to repair. The user can also integrate in these functions some additional safety values. The “fraction defective” assumption is widely used in the literature, see Inderfurth et al., 2005, Teunter and Flapper, 2003, Inderfurth et al., 2006, Inderfurth et al., 2007, Chiu et al., 2007 and Buscher and Lindner, 2007. Flapper, Fransoo, Broekmeulen, and Inderfurth (2002) underline that uncertainty about the distribution of the defective items is common for many process industries. Nevertheless, if there is an adequate statistical data, it is possible to accurately determine that the rate of defective items is relatively stable and fixed. The following parameters are assumed to be given: di – demand for the good items of product i, i = 1, … , n; ti – per item processing time of product i, i = 1, … , n; ci – per item cost of demand dissatisfaction for product i, i = 1, … , n; si,j – set-up time for a pair of products i, j, if a lot of product i immediately precedes a lot of product j, si,j ⩾ 0; s0,i – initial set-up time, if the manufacturing process begins with a lot of product i, i = 1, … , n, s0,i ⩾ 0; fi(xi) – an integer non-decreasing function whose value is equal to the estimated quantity of defective items in a lot of size xi of product i. We require fi(0) = 0, and fi(xi) ⩽ xi; R(x) – non-negative non-decreasing real valued function which represents the forecasted cumulative repair time for the lot size vector x = (x1, … , xn). All di, ti and ci are integer positive numbers. We assume that the set-up times satisfy the triangle inequality: si,j + sj,k ⩾ si,k for any triple of products (i, j, k), where i = 0, … , n, j,k = 1, … , n and i ≠ j ≠ k. Note that the set-up time matrix may not be symmetric, i.e., si,j ≠ sj,i may happen for i, j ∈ {1, … , n}. Sequence-dependent set-ups are widely studied for lot-sizing and scheduling problems, see, for example, Shim, Kim, Doh, and Lee (2011). There are some additional assumptions: • the machine can process at most one item at a time; • item processing is not possible during set-up or repair time; • set-up and repair times cannot overlap; • breakdown can only happen during item processing; • items of the same product pass through the machine with no time delay between them (the transfer time is included in the processing time). The deterministic problem P-Cost considered in this paper was originally proposed in Dolgui et al. (2011), where the authors prove that its lot-sizing part, called P-Cost-Sizes, is NP-hard even in the “fraction defective” (FD) case and propose a dynamic programming algorithm and a fully polynomial time approximation scheme (FPTAS). In the present paper, we show that the problem P-Cost-Sizes-FD admits two integer linear programming formulations (ILP). Further we compare the performances of the dynamic programming algorithm and two ILP formulations solved by ILOG CPLEX. Finally, we demonstrate that the FPTAS and one of the ILP models can be transformed to solve a more general than “fraction defective” case, denoted as P-Cost-Sizes-αβ. The remainder of this paper is organized as follows. In Section 2, we provide a mathematical model and some observations about the problem P-Cost. Section 3 describes two ILP models for the “fraction defective” case of this problem. Section 4 contains a comparison of the ILOG CPLEX realizations of the proposed models with the earlier developed dynamic programming algorithm. In Section 5, we introduce the problem P-Cost-Sizes-αβ and demonstrate the transformations required for the FPTAS and one of the ILP models to solve this new problem. Some conclusions are reported in Section 6.

A problem of optimal lot-sizing and sequencing multiple products on an imperfect single machine has been studied. The machine can breakdown and produce defective items. Thus, there are two types of losses of productivity: defective items and machine stoppages after break downs. We introduced deterministic function representing the rates of defective items and cumulative repair time. For the studied model, lot-sizing and sequencing decisions can be taken independently. The sequencing sub-problem is equivalent to the well known asymmetric traveling salesman problem. Therefore, we have concentrated on the lot-sizing sub-problem. From the theoretical standpoint, we have shown that the FPTAS proposed by Dolgui et al. (2011) for the “fraction defective” case can also be generalized to handle a more general case of concave and convex functions fi(xi) representing the number of defective items. Two integer linear models have been developed. One of them is designed for the “fraction defective” case, and the other can be used for a concave case. These models are implemented in ILOG CPLEX. The worst-case complexity of algorithms in this commercial solver is exponential, and thus, it is theoretically less efficient than the FPTAS. However, ILOG CPLEX implementation is very efficient in the provided experiments. We remark that the Bound Improvement Procedure of the FPTAS is used to speed up this implementation. Another interesting result is that DP and BLP are not sensitive to the type of the functions fi(xi). The search for other important special cases where the linear programming models are efficient, as well as for the extensions of the FPTAS approach, is perspective. An interesting topic is to consider the problem with lots for which xi = 0. In this case, the selection of products for processing and their sequence cannot be separated. It would also be interesting to develop a strongly polynomial FPTAS for the problem P-Cost-Sizes.