گداختن ترکیبی شبیه سازی شده و ابتکارات مبتنی بر MIP-برای مشکل تعیین اندازه دسته تولید و برنامه ریزی تصادفی در سیستم تولید چند مرحله ای توانا شده
کد مقاله | سال انتشار | تعداد صفحات مقاله انگلیسی |
---|---|---|
22826 | 2013 | 14 صفحه PDF |
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Applied Mathematical Modelling, Volume 37, Issue 7, 1 April 2013, Pages 5134–5147
چکیده انگلیسی
This paper addresses lot sizing and scheduling problem of a flow shop system with capacity constraints, sequence-dependent setups, uncertain processing times and uncertain multi-product and multi-period demand. The evolution of the uncertain parameters is modeled by means of probability distributions and chance-constrained programming (CCP) theory. A new mixed-integer programming (MIP) model with big bucket time approach is proposed to formulate the problem. Due to the complexity of problem, two MIP-based heuristics with rolling horizon framework named non-permutation heuristic (NPH) and permutation heuristic (PH) have been performed to solve this model. Also, a hybrid meta-heuristic based on a combination of simulated annealing, firefly algorithm and proposed heuristic for scheduling is developed to solve the problem. Additionally, Taguchi method is conducted to calibrate the parameters of the meta-heuristic and select the optimal levels of the algorithm’s performance influential factors. Computational results on a set of randomly generated instances show the efficiency of the hybrid meta-heuristic against exact solution algorithm and heuristics.
مقدمه انگلیسی
One of the very important issues in the area of production planning is the integrated production planning and scheduling problem. Production planning and scheduling belong to two different decision making levels, such that the production planning belongs in the medium-term level and the scheduling is placed in the short-term level. Due to the interrelationship between these two levels, to obtain globally optimal solutions, the interdependence between different functions of planning should be taken into consideration, and the planning decisions should be taken simultaneously. The solution strategies for obtaining thorough production planning and scheduling can be classified into three categories: the hierarchical method, the iterative method and the comprehensive (full-space) method [1]. In the hierarchical method, the high-level problem determines the set of high-level decision variables such as the amount of production, inventory and shortage. This information is used as the input for the low-level scheduling sub-problem. The obtained production quantities are most probably infeasible or sub-optimal. The iterative approach tries to flow the information cycle from the scheduling sub-problems toward the higher-level problem and to get a feedback from the low-level sub-problem for the high-level problem. In order to overcome the weakness of the hierarchical production planning, Lasserre [2] considered a shop planning and scheduling model in the job shop environment and used a decomposition approach that alternated between solving a planning problem with a fixed sequence of products on machines and a shop scheduling problem for a fixed chosen production plan. Anwar and Nagi [3] proposed a two-phase method for lot sizing and scheduling in the job shop environment for a single-period planning horizon. Kim et al. [4] considered a production planning and scheduling problem for combining the products with hierarchical structure, similar to the material requirement planning (MRP), and solved this problem. The comprehensive approach considers the problem as an integrated issue, so that the conditions and constraints of the detailed scheduling problem are used in the modeling of production planning. One of the methods that consider the production planning and scheduling as an integrated problem is the simultaneous lot-sizing and scheduling planning. Ever since Wagner and Whithin [5] published their seminal paper on the dynamic lot-sizing problem in 1958, researchers have developed different models for solving the problems in this area. There are two basic modeling approaches in the literature for the dynamic lot-sizing problems, including models with big bucket time and those with small bucket time. In the small bucket time problems, first the larger time period is divided into small time periods and then the modeling is carried out. This procedure drastically increases the complexity of the problem. In the models with small bucket time, it is usually assumed that one or maximum two products may be manufactured in every period. Thus these models enable simultaneous lot-sizing and scheduling. On the other hand, models with big bucket time allow the manufacturing of several products in a given macro-period without determining the sequence of products. Karimi et al. [6] conducted a comprehensive review of the lot-sizing and scheduling problems in the single-level case and appropriately classified the problems in this area. Buschkühl et al. [7] presented a review of the research works in the last four decades on the capacitated dynamic lot-sizing problem. In their paper, they focused on the multi-level capacitated lot-sizing problem (MLCLSP), which is a model with big bucket time. The lot-sizing problems in multi-level production environments with small bucket time include the multi-level discrete lot-sizing and scheduling problem (MLDLSP) [8], multi-level proportional lot-sizing and scheduling problem (MLPLSP) [9] and the multi-level general lot-sizing and scheduling problem (MLGLSP) [10]. The MLDLSP and MLPLSP models can simultaneously perform lot sizing and scheduling, however, the number of products that can be manufactured in each period is limited. MLGLSP integrates lot sizing and scheduling of several products in each period. Therefore, the MLGLSP, which was proposed by Fundel and Stammen-Hegene [10] tries to model the problem by using the integration advantages of the MLPLSP and MLCLSP based on the dividing of larger periods into a fixed number of smaller periods. Due to the high computational complexity of this model, only problems with very small sizes can be optimally solved by this model. Mohammadi et al. [11] considered the multi-level lot-sizing and scheduling problem with sequence-dependent startups. Artificial setup concept which assumes that during every planning period, N (number of products) setups occur is used to formulate this problem. Their modeling is a generalization of the model proposed by Clark and Clark [12] for the case of parallel machines. Since in their modeling, a number of fixed and given setup has been assumed in every period, the computational complexity increases. Recently, Ramezanian et al. [13] studied a multi-product multi-period lot-sizing and scheduling problem in capacitated permutation flow shop with sequence-dependent setups. They proposed a more efficient mathematical model for the problem and used two MIP-based heuristics for solving related problem. In the lot-sizing and scheduling literature, most of the past researches have focused on deterministic conditions. However, considering the different sources of uncertainty in the real world (e.g. processing times, product demand, etc.), this assumption not only becomes limited but it could also affect the decisions regarding to the lot-sizing and scheduling. Thus, the solutions obtained by deterministic models may be having little value when uncertain parameters are replaced by the average or worst case. To the best knowledge of the authors, all the studies under uncertain conditions are associated with the single-level case and this paper is the first attempt at modeling the problem in an uncertain multi-level environment. Sox et al. [14] reviewed the problems of static and dynamic lot-sizing with random demand. Gnoni et al. [15] studied the problem of production planning and scheduling of a multi-site manufacturing system with uncertain demand. The lot-sizing and scheduling problem is defined separately at each location. They solved the considered problem using a hybrid model consisting of the mixed integer programming model and a simulation model. Beraldi et al. [16] considered the problem of lot-sizing and scheduling with identical parallel machines with uncertain processing times and they evaluated the uncertain parameters using the scenario tree. They also applied the fix-and-relax method to solve the problem. A new approach is used to formulate the proposed integrated multi-level lot-sizing and scheduling problem as a stochastic mixed integer programming model based on the big bucket time. After transforming the stochastic problem into a deterministic form by using the chance-constrained programming (CCP) theory, it was solve by means of heuristics and hybrid simulated annealing algorithms. Two heuristic algorithms based on MIP model with the rolling horizon framework, which iteratively create and solve smaller size models, have been developed for solving the integrated model. The proposed meta-heuristic method combines the simulated annealing algorithm with the firefly algorithm. To obtain better and more robust solutions, the Taguchi method is used to calibrate the parameters of the hybrid algorithm. The considered solution algorithms search the solution space for both problems and find a combination of production planning and scheduling which is feasible and close to the optimal solution. The chance-constrained programming (CCP) was introduced by Charnes et al. [17] and have been extensively studied as means of dealing with uncertainty by specifying a confidence level at which the uncertain constraints hold. For both the theoretical and application background, the readers may refer to Prékopa [18] where an extensive list of the research works is presented. The rest of the paper is organized as follows. In Section 2, the considered problem is described and a stochastic mixed integer programming model is proposed to formulate this problem. The heuristic methods, the hybrid algorithm and Taguchi method for tuning the parameters of the hybrid algorithm are presented in Sections 3 and 4 presents computational experiments and discussion. The conclusions and suggestions for future studies are included in Section 5.
نتیجه گیری انگلیسی
In this paper, we deal with lot sizing and scheduling problem of a multi-stage manufacturing system subject to capacity constraints and uncertainty in processing times and products demand. Chance-constrained programming theory is used to model the stochastic parameters. An efficient MIP model is proposed to formulate this problem. Due to the complexity of the problem, two MIP-based heuristics based on iterative procedures and a hybrid meta-heuristic is developed to solve problem instances. The first heuristic is based on the original model and the second heuristic is based on permutation flow shop problem which considers the similar sequence vector of products on all machines. Also, the hybrid meta-heuristic is based on a combination of simulated annealing, firefly algorithm and proposed heuristic for scheduling. Additionally, an extensive parameter setting with performing the Taguchi method is conducted for selecting the optimal levels of the factors that effect on algorithm’s performance. Also, computational experiments clearly confirmed the superiority of our proposed hybrid meta-heuristic with respect to the heuristic methods. One straightforward opportunity for future research is extending the assumption of the proposed model for including real conditions of production systems such as limited intermediate buffer space, lot transportation constraints, etc. Also, using the multi objective optimization approach can be suggested for further research.