ترتیب‌گذاری چند محصولی و تعیین‌ اندازه-لات تحت عدم‌حتمیت: الگوریتم ممتیک

The paper deals with a stochastic multi-product sequencing and lot-sizing problem for a line that produces items in lots. Two types of uncertainties are considered: random lead time induced by machine breakdowns and random yield to take into account part rejects. In addition, sequence dependent setup times are also included. This study focuses on maximizing the probability of producing a required quantity of items of each type for a given finite planning horizon. A decomposition approach is used to separate sequencing and lot-sizing algorithms. Previous works have shown that the sequencing sub-problem can be solved efficiently, but the lot-sizing sub-problem remains difficult. In this paper, a memetic algorithm is proposed for this second sub-problem. Computational results show that the algorithms developed can be efficiently used for large scale industrial instances.

In this paper, a multi-product lot-sizing and sequencing problem under uncertainties is studied. The source of the problem is derived from an automated semiconductor manufacturing plant where there are non-negligible percentages of rejects and breakdowns. However, this situation can concern any automatic production line working under uncertainties and the proposed approach could be easily extended to different types of production lines. The example given here is from our experience of designing a paced line to produce several types of conductor patterns. These parts are used to obtain electronic modules (printed circuits). Since the considered semi-conductor factory is greatly automated, there is no staff other than maintenance for almost the whole day. The facility functions with three shifts. Specifically, the main task for the day shift is to define the production plan for the next 24 h and start the manufacturing process. The evening and night shifts, which consist of maintenance personnel only, insure the production line continue to function, but cannot change the production plan. As a consequence, the production plan is set for 24 h and will not be adjusted to take into account rejects or breakdowns that may occur in the later shifts. After processing, parts (conductor patterns) are placed in an automatic storage system, and they are used for the assembly of electronic modules. The automatic storage system is expensive and restricted in volume. Consequently, it should work with one day stock limit, if possible. So, this line and storage system should be able supply the next assembly line just-in-time. In other words, the following policy is applied: all the items used for assembly in period r+1 must be in the storage system by the end of planning period r. At the beginning of the period r, the demand for all items types for assembly in the planning period r+1 is known (taking into account the current stocks in the automatic storage system, if they exist, and the production plans of the assembly line for period r and r+1). Thus, for each period r, the following question has to be answered: how many items of each type must be released to production in the beginning of the period r to obtain the necessary quantity for all components in the next production run r+1 of the assembly line? With this sort of production, there is a non-negligible percentage of rejects, because some finished components are produced with unacceptable quality. Quality control is made at the end of the line with no intermediate quality control. In addition, the machines of the line are often stopped briefly because of breakdowns. This leads to a new and very interesting production control problem dealing with optimal lot-sizing and scheduling under uncertainties. There are two types of possible policies which are in conflict. To diminish the influence of random breakdowns, the safety time (the difference between the duration of the planning horizon and the time necessary to produce all lots) can be increased, but in this case, it is necessary to reduce the sizes of lots, so the production plan can be more easily perturbed by rejects. On the other hand, the size of lots can be increased to diminish the impact of random rejects, but the line will be more sensitive to random breakdowns, because of insufficient safety time. There would be not enough time to repair of all these breakdowns and the line cannot produce the necessary quantity of items. Moreover, a set-up time is necessary between processing of two different products for reconfiguration of manufacturing facility. The set-up time depends on type of already manufactured product and new items to process. Thus, for the both policies mentioned above, there is an additional level of action affecting the safety time. In this paper, we will reexamine the probabilistic formulation of this lot-sizing and scheduling problem, initially evoked in Dolgui (2002). For this problem, a first approach was suggested in Dolgui et al. (2005): authors have shown that this problem can be reduced to a single machine problem with sequence-dependent set-up times and that its optimal solution can be obtained using a decomposition into several optimization sub-problems: enumerating, sequencing and lot-sizing. Note that the latter two problems are NP-hard but the sequencing sub-problem can be transformed in a well-known Traveling Salesman Problem, for which there exist a large number of effective algorithms. For lot-sizing sub-problem, in Dolgui et al. (2005), the authors presented an idea how dynamic programming (DP) approach could be used to solve it. Nevertheless, only the decomposition framework and a recursive DP expression for lot-sizing were provided. No evaluating tests were performed. Thus, the question on the effectiveness of this approach for small, medium and large size cases is still open. This needed to be explored further which is the motivation of the current paper. We present a global approach intended to treat actual problems of industrial sizes. This study will employ the earlier proposed overall decomposition approach. DP will be tested on several numerical examples and a memetic algorithm (MA) based on a local search (LS) and a genetic algorithm (GA) will be suggested for large scale cases. The rest of the paper is organized as follows. Overall assumptions and problem statement are presented in Section 2. A review of related literature is given in Section 3. Section 4 introduces the solution framework: how the uncertainties are modeled and decomposition is accomplished. In Section 5, a Memetic Algorithm (MA) with its elements is presented. In Section 6, several experimental results comparing the algorithms (DP, LS, MA) are reported. Section 7 contains some concluding remarks and further perspectives.

A real-life problem of optimal lot-sizing and sequencing for a production line with random breakdowns and rejects was studied. The line considered manufactures intermediate components of different types for subsequent assembly into modules. The problem is to choose sequences and lot sizes. The objective is to maximize the probability to have a sufficient number of components by the end of a given planning horizon, i.e. maximize the overall service level. The benefit of this optimization is evident, because without any additional resources, production cost can be reduced by limiting the stoppages for the assembly line that follows. With an optimal decomposition procedure which uses a complete enumeration to search for the optimal last lot, sequencing and lot-sizing decisions can be considered separately. The sequencing sub-problem can be reduced to the well studied Asymmetric Traveling Salesman Problem and thus be solved with known methods. For lot-sizing, a local search and a memetic algorithm were proposed. Some experimental results were shown and discussed. The algorithms developed were compared with a dynamic programming procedure for small size instances and between them for large size problems. The MA and LS developed can find good solutions for large problems and thus this approach can be applied to large scale industrial problems. Future work may entail using simulation methods to replace the evaluation function (fitness) in order to consider problems with various probability distributions or integrating other uncertainty phenomena (e.g. uncertain manufacturing time). For example, by using simulation we could study problems in which the quantity and/or seriousness of breakdowns increases with the age of machines, etc. It will be interesting also to develop a metaheuristics approach to resolve the entire problem without decomposition and compare the results with and without decomposition.