همکاری موازی متا هیوریستیک در شبکه های محاسباتی: مطالعه موردی: مسئله دو هدفه ی جریان فروشگاه

In this paper, we contribute with the first results on parallel cooperative multi-objective meta-heuristics on computational grids. We particularly focus on the island model and the multi-start model and their cooperation. We propose a checkpointing-based approach to deal with the fault tolerance issue of the island model. Nowadays, existing Dispatcher–Worker grid middlewares are inadequate for the deployment of parallel cooperative applications. Indeed, these need to be extended with a software layer to support the cooperation. Therefore, we propose a Linda-like cooperation model and its implementation on top of XtremWeb. This middleware is then used to develop a parallel meta-heuristic applied to a bi-objective Flow-Shop problem using the two models. The work has been experimented on a multi-domain education network of 321 heterogeneous Linux PCs. The preliminary results, obtained after more than 10 days, demonstrate that the use of grid computing allows to fully exploit effectively different parallel models and their combination for solving large-size problem instances. An improvement of the effectiveness by over 60% is realized compared to serial meta-heuristic.

In combinatorial optimization, meta-heuristics allow to iteratively solve in a reasonable time NP-hard complex problems. According to the number of solutions handled at each iteration, two main categories of meta-heuristics are often distinguished: evolutionary algorithms (EAs) and local searches (LSs). EAs are population-oriented as they manage a whole population of individuals, what confers them a good exploration power. Indeed, they allow to explore a large number of promising regions in the search space. On the contrary, LSs work with a single solution which is iteratively improved by exploring its neighborhood in the solution space. Therefore, they are characterized by better local intensification capabilities. On the other hand, theoretical and experimental studies have shown that the cooperation between meta-heuristics belonging either to the same category or to different categories improves the effectiveness (quality of provided solutions) and the robustness of the meta-heuristics [14]. Nevertheless, as it is generally CPU time-consuming it is not often fully exploited in practice. Indeed, experiments with cooperative meta-heuristics are often stopped without convergence being reached. Nowadays, grid computing [7] is recognized as a powerful way to achieve high performance on long-running scientific applications. Parallel cooperative meta-heuristics for solving real-world multi-objective problems (MOPs) are good challenges for grid computing. However, to the best of our knowledge very few research works have been published on that topic. In this paper, we contribute with the first results on parallel cooperative multi-objective meta-heuristics on computational grids. We particularly focus here on the island model and the multi-start model and their cooperation. These two models are presented in Section 2. The computational grid targeted in this paper is a scalable pool of heterogeneous and dynamic resources geographically distributed across multiple administrative domains and owned by different organizations. The scalability and volatile nature of the grid may particularly have a great impact on the design of grid-based meta-heuristics. The traditional parallel models and cooperation mechanisms have to be re-visited and adapted to be scaled up. Moreover, these require to be fault-tolerant to allow long-running problem resolutions. The design and deployment of the parallel cooperative models of meta-heuristics on computational grids require a grid middleware that allows cooperation between parallel tasks. In this paper, we focus on the Dispatcher–Worker grid middlewares such as XtremWeb [6]. One major limitation of such middlewares is that they do not allow communication between workers. One of our contributions is to propose a Linda-like [10] coordination model and its implementation on top of XtremWeb. This is a Dispatcher–Worker middleware, in which the dispatcher distributes application tasks submitted by clients to volunteer workers at their request. In addition, the middleware provides fault-tolerance mechanisms that are costly in a highly volatile computational grid. Indeed, a work unit is re-started from scratch each time it fails. Another contribution of this paper is to deal with the fault-tolerance issue at the application level. We propose a checkpointing approach for the island model. To be validated the work has been experimented on the Bi-criterion Permutation Flow-Shop Problem (BPFSP) [16]. The problem consists roughly to find a schedule of a set of jobs on a set of machines that minimizes the makespan and the total tardiness. Jobs must be scheduled in the same order on all machines, and each machine can not be simultaneously assigned to two jobs. In [1] and [2], a parallel cooperative multi-objective meta-heuristic has been proposed to solve this problem. The work has been experimented on a large problem instance of 200 jobs on 10 machines an IBM-SP2 of 16 processors. As the implementation is not fault tolerant, the experiments have been stopped by far before the convergence is reached. In this paper, we propose to use the computational grid to overcome such problem. Our proposed work is based on a gridification of the island and multi-start models and their cooperation. It allows to fully exploit the cooperation and provides clearly better results. The rest of the paper is organized as follows: Section 2 briefly presents the multi-objective meta-heuristics and their associated parallel and cooperative models. Section 3 describes the characteristics of the targeted computational grid and their impact on parallel cooperative meta-heuristics. Dispatcher–Worker grid middlewares are discussed and their limitations are highlighted. In Section 4, a coordination model for such family of middlewares is proposed with an implementation on top of XtremWeb [6]. Section 5 presents the experimentation of the model and its implementation through a parallel cooperative meta-heuristic applied to the Bi-objective Permutation Flow-Shop Scheduling Problem (BPFSP), and analyzes the preliminary experimental results. Finally, Section 6 concludes the paper.

The cooperation of meta-heuristics having complementary behaviors allows to enhance the effectiveness and robustness in combinatorial optimization [14]. However, its exploitation for solving real-world problems is possible only by using a great computing power. Large-scale parallelism based on the use of computational grids is recently revealed to be a good way to get at hand such computing power and fully exploit cooperation. At our best of knowledge, no research work has been published on parallel cooperative meta-heuristics on grids. Nowadays, existing Dispatcher–Worker grid computing middlewares are inadequate for the deployment of parallel cooperative applications. Indeed, these need to be extended with a software layer to support the cooperation. In this paper, we have proposed a Linda-like cooperation model that has been implemented on top of XtremWeb. In [1] and [2], a cooperative meta-heuristic (AGMA) has been proposed and experimented on BPFSP. The performed experiments on large-size instances such as 200 jobs on 10 machines are often stopped without convergence being reached. The full exploitation of the cooperation needs a large amount of computational resources and the management of the fault tolerance issue. We have proposed a fault-tolerant cooperative parallel design of the AGMA combining two parallel models: the multi-start model and the island model. The algorithm has been implemented on our extended version of XtremWeb. The first experiments have been performed on a multi-domain education network. The network is composed of 321 heterogeneous Linux PCs. The preliminary results, obtained after several execution days, demonstrate that the use of grid computing allows to fully exploit effectively different parallel models and their combination for solving large-size problem instances. In addition, the results show that the proposed checkpointing-based fault tolerance approach induces a very low overhead. Beyond the improvement of the effectiveness, the parallelism on grids allows to push far the limits in terms of computational resources. As a consequence, it permits to better evaluate the benefits and limitations of the cooperation. In the future, the focus will be on the cooperation of meta-heuristics with exact methods to provide exact Pareto fronts. The meta-heuristics will serve to provide better bounds to reduce the exploration cost of the exact methods.