جستجوی محلی راه اندازی مجدد هدایت شده برای برنامه ریزی تولید

Planning problems can be solved with a large variety of different approaches, and a significant amount of work has been devoted to the automation of planning processes using different kinds of methods. This paper focuses on the use of specific local search algorithms for real-world production planning based on experiments with real-world data, and presents an adapted local search guided by evolutionary metaheuristics. To make algorithms efficient, many specifics need to be considered and included in the problem solving. We demonstrate that the use of specialized local searches can significantly improve the convergence and efficiency of the algorithm. The paper also includes an experimental study of the efficiency of two memetic algorithms, and presents a real-world software implementation for the production planning.

Planning problems exist in many real-world-industrial production settings and can be solved with a large variety of different approaches. Due to the growing complexity of these real-world planning problems, significant work has been devoted to the automation of planning processes using different kinds of methods. Furthermore, as a result of the increasing deployment of planning and scheduling systems, we often have to deal with very large search spaces, real-time performance demands, and dynamic environments (Nareyek, 2000). A review of the research on integrated process planning and scheduling, along with a discussion on the extent of the applicability of various approaches is presented in Li et al. (2010) and Shaotan et al. (2010). This paper focuses on the use of specific local search algorithms for real-world production planning based on experiments with real-world data and presents the adapted, local search, evolutionary-based metaheuristics for the real-world industrial problem. It also includes an experimental study of the efficiency of two memetic algorithms, and presents a real-world software implementation for the production planning. The motivation of this research is to solve an industrial problem. The goal of our real-world production-planning problem is to find a production plan that satisfies the production time constraints and minimizes the production costs. This involves many specific constraints that need to be considered. The main problem is the exchange delay, caused by adapting the production lines to different types of products and supplying the appropriate parts. Namely, the manufacturing processes of multiple types of products require many different steps and different product parts for the completion of each product type. Such a kind of problem can be represented as a job shop scheduling problem (Brucker, 1998). For solving scheduling problems, many scheduling methods are reported in the literature (Xing et al., 2010, Wang and Tang, 2009, Guo et al., 2009, Chiong and Dhakal, 2009 and Jarboui et al., 2009). One of the nature-inspired approaches (Chiong, 2009) is the genetic algorithm (GA). A heuristic for the open job shop scheduling problem using the GA to minimize makespan was developed by Senthilkumar and Shahabudeen (2006). On the other hand, a scheduling method based on the GA was developed by considering multiple criteria in Chryssolouris and Subramaniam (2001). Other implementations of the GA for scheduling can be found in Vazquez and Whitley (2000). The advanced local search approaches are usually guided by evolutionary algorithms, simulated annealing, tabu search, min-conflicts, and others (Voß, 2001). The basics of local search are in the successive changing of solutions with moves that alter solutions locally. These moves are defined by the neighborhood, which contains all the solutions that can be reached with one move/change. As the solution quality of the local optima may be unsatisfactory, we need some mechanisms that guide the search to overcome the local optimality. A simple strategy is to iterate/restart the local search process after a local optimum has been obtained, while more structured ways, e.g., the use of an evolutionary search, to overcome the local optimality might be advantageous. In Hamiez and Hao (2001), the problem of sports-league scheduling is addressed, presenting the results achieved by a tabu search method based on a neighborhood of value swaps. Furthermore, some works deal with planning systems that are able to incorporate resource reasoning. In Chien et al. (2001) the replanning capabilities of local search methods in a continuous planning process clearly outperform a restart strategy. In Engelhardt and Chien (2001), learning is used to speed up the search for a plan, where the goal is to find a set of search heuristics that guide the search, while Knight et al. (2001) proposes a technique for aggregating single search moves, so that distant states can be reached more easily. GAs in combination with local search procedures are known as memetic algorithms (MAs) (Ong and Keane, 2004). They represent a synergy of the evolutionary approach with separate individual learning or local improvement procedures (local searches) for the problem search. Various MAs were developed (Hasan et al., 2009, Caumond et al., 2008, García-Martínez and Lozano, 2008, Siarry and Michalewicz, 2008 and Ombuki and Ventresca, 2004) to obtain even better results than the GA for various scheduling applications. With the use of local search techniques the results were further improved. MAs do not only improve the quality of the solutions, but they also reduce the overall computational time (Hasan et al., 2009). Special attention should also be given to the dynamic nature of the production. Local search is well suited for anytime requirements because the optimization goal is improved iteratively (Nareyek, 2000). Here, a variety of algorithms have been proposed to solve dynamic optimization problems (Moser and Chiong, 2010, Tfaili and Siarry, 2008 and Engelhardt and Chien, 2001). The rest of the paper is organized as follows: in Section 2, we describe the problem and give its mathematical formulation; in Section 3, we present preliminary evaluations for the algorithm selection; in Section 4, we describe the evolutionary algorithms; in Section 5, we introduce the used local search procedures; in Section 6, we show the integration of guiding evolutionary algorithms with local search procedures; in Section 7, we present the experimental environment and the results of the evaluation with the real-world data; in Section 8, we present the implemented application for automatic production planning; and in Section 9, we conclude and propose possible future work.

In this paper we have tested a guided local search algorithm on some real-world test cases of a production planning problem. Such a problem is a member of the family of job shop scheduling problems, which are known to be NP-hard. Due to the problem's complexity with many constraints, we have used some specialized local searches and guided them with the GA, PLES and random selection. We have shown that the use of all the stochastic approaches greatly improved the quality of the production plans in respect to the expert's manual solution. There was also a noticeable difference between the evolutionary and the random guided approach in favor of the evolutionary. Although the random selection approach was able to come competitively close to the results of the evolutionary approaches, it was obvious that its success was caused by the quality of the LS. Namely, to get good results in a relatively short time we had to implement a very powerful LS. This led to good performances for all the guided approaches; however, the GA was the most stable among all. Furthermore, we are planning to analyze the performance of the PLES to find out possible reasons for its behavior. Its drawback might be in an automatic creation of the population size, which seems to be too large for these kinds of problems. For future work, we are planning to include some more constraints, which are already mentioned in the mathematical formulation of the problem, into the plan construction, i.e., fixed-order production days (the exact day when the order has to be carried out). Another aspect of improvement of the application is to put the results into a database, in order to allow the analysis of the plans and the evaluation of their realization in the production.