حل مشکل جریان قابل انعطاف فروشگاه اینترنتی با یک الگوریتم ترکیبی ژنتیک و داده کاوی: یک رویکرد فازی
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|22215||2011||7 صفحه PDF||سفارش دهید||2640 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Expert Systems with Applications, Volume 38, Issue 6, June 2011, Pages 7609–7615
In this paper, an efficient algorithm is presented to solve flexible flow-shop problems using fuzzy approach. The goal is to minimize the total job tardiness. We assume parallel machines with different operation times. In this algorithm, parameters like “due date” and “operation time” follow a triangular fuzzy number. We used data mining technique as a facilitator to help in finding a better solution in such combined optimization problems. Therefore, using a combination of genetic algorithm and an attribute-deductive tool such as data mining, a near optimal solution can be achieved. According to the structure of the presented algorithm, all of the feasible solutions for the flexible flow-shop problem are considered as a database. Via data mining and attribute-driven deduction algorithm, hidden relationships among reserved solutions in the database are extracted. Then, genetic algorithm can use them to seek an optimum solution. Since there are inherited properties in the solutions provided by genetic algorithm, future generation should have the same behavioral models more than preliminary ones. Data mining can significantly improve the performance of the genetic algorithm through analysis of near-optimal scheduling programs and exploration of hidden relationships among pre-reached solutions.
Flow-shop with parallel machines (FSPM) problem is well-known to flexible flow-shop problem (Hoogeveen et al., 1996, Janiak and Lichtenstein, 2001 and Tian et al., 1999). This problem includes a number of products with the same production steps. There are parallel machines in each production stage (work-station). All products have should pass step 1 to step “n” ( Artiba and Elmaghrabhy, 1997 and Shiau et al., 2008). Each job is processed just by one machine in each step. Also, each machine is working on one job each time and equally each job is under processing just using one machine each time. Machine center can be filled by uniform or unrelated machines. In this paper, we suppose that three types of machines in each center. These machines are equal in operation type and different in operation speed. In recent two decades, many researchers focus on flexible flow-shop problem which is a NP-Hard problem. Most researchers considered maximum finish time as a goal function. As well as mathematical modeling, deterministic, heuristic and even meta-heuristic methods are used (Chen, 1995, Gupta, 1988 and Haouari and Hallah, 1997). Others preferably applied deterministic and heuristic methods to solve small-size problems (Botta-Genoulaz, 2000, Braha and Loo, 1999 and Kyparisis and Koulamas, 2001). The main parameter used in these papers is to minimize tardiness time for all jobs. Customer’s orders represent input jobs to the system. For each job, the setup and process times are determined by process unit and due date is established by customers. Botta-Genoulaz (2000) presented six heuristic algorithms to minimize the maximum tardiness in a flexible flow-shop problem with different due dates. Lin and Liao (2003) developed a near-optimal heuristic algorithm to minimize maximum tardiness in a 2-stage flexible flow-shop problem. Bertel and Billaut (2004) proposed a heuristic algorithm for a scheduling problem in a flow-shop environment with regards to minimizing the numbers of operations with balanced tardiness. They have used a combination of integer-linear programming and genetic algorithm for the mentioned problem. Vob and Witt (2007) studied on a flexible flow-shop which is an actual scheduling problem including 16 processing steps to minimize balanced tardiness time. They have developed a mathematic model on the basis of scheduling problem with limitation of resources. Then they have solved the problem heuristically. Besides pointed out algorithm used to solve different types of problems, a number of other algorithms can be found. For example, there are lots of algorithms most of which use neighborhood search, tabu search and simulated annealing. Some of them also use branch and bound algorithm (Chen et al., 2008, Garey and Johnson, 1979 and Karimi et al.., in press). The above techniques have significantly success to solve combinational optimization problem. The flexibility of these techniques especially genetic algorithm has extended their application scope (Deborah et al., 2004 and Roshanaei et al., in press). In this paper, we have used a different analytical glass to the flexible series scheduling problem to improve the efficiency of the solution. We have also used data mining to study the properties of the solutions to find their hidden relationships. Data mining is an effective tool to manage huge databases. In the presented methodology, each feasible scheduling solution is considered as a database member. After clustering the data, their properties are recorded. Then, logical relationships among the operation’s properties and their sequence have been developed through data mining deduction algorithm. The extracted rules help genetic algorithm to boost its speed to the optimal point. In each stage of scheduling, there are three types of machines with low, medium and high operation speed. A triangular fuzzy number is assigned for the time of operations. The structure of the remaining part of the paper is as follows: In Section 2, we have studied the flexible series scheduling problem. In Section 3, the application of data mining in the flexible series scheduling is studied. The genetic algorithm is applied to the problem in Section 4. The proposed methodology is discussed in Section 5. In Section 6, we analyzed the efficiency of the methodology and finally, we illustrate the findings in Section 7.
نتیجه گیری انگلیسی
In this paper, a hybrid algorithm is developed which is a combination of multiple algorithm including genetic algorithm, data mining, fuzzy sets, similarity algorithm and attribute-driven deduction algorithm. We solved the flexible series scheduling problem to minimize the length of timing period. The obtained answers are very pleasant. In this algorithm, the chromosomes are defined on the machines. The genes are representatives for assignment rules. Applications of data mining and attribute-driven deduction algorithm together with the genetic algorithm and fuzzy sets have significantly improved the performance of the algorithm. Also the convergence rate to the optimal solution has improved. To show the efficacy of the algorithm, a numerical example is presented. The results are compared against to GA and ILP. We have solved 300 typical real problems and compared the results against GA and ILP. The findings show a 48% time reduction in solving the problems. The local optimal solution is equal to 5%. As the application of data mining and attribute-driven deduction algorithm in fuzzy sets needs sufficient knowledge and intuition to the problem, the use of obtained information from the presented algorithm in genetic algorithm has improved the solutions.