متااکتشافی ترکیبی موازی برای مشکل تولید کارگاهی انعطاف پذیر

A parallel approach to flexible job shop scheduling problem is presented in this paper. We propose two double-level parallel metaheuristic algorithms based on the new method of the neighborhood determination. Algorithms proposed here include two major modules: the machine selection module refer to executed sequentially, and the operation scheduling module executed in parallel. On each level a metaheuristic algorithm is used, therefore we call this method meta2heuristics. We carry out a computational experiment using Graphics Processing Units (GPU). It was possible to obtain the new best known solutions for the benchmark instances from the literature.

The flexible job shop problem constitutes a generalization of the classic job shop problem where operations have to be executed on one machine from a set of dedicated machines. Then, as a job shop problem it also belongs to the strongly NP-hard class. Although exact algorithms based on a disjunctive graph representation of the solution have been developed (see Pinedo (2002)), they are not effective for instances with more than 20 jobs and 10 machines. Many approximate algorithms, mainly metaheuristics, have been proposed. Hurink, Jurisch, and Thole (1994) developed the tabu search method for this problem. Also Dauzère-Pérès and Pauli (1997) used the tabu search approach extending the disjunctive graph representation for the classic job shop problem taking into consideration the assignment of operations to machines. Mastrolilli and Gambardella (2000) proposed a tabu search procedure with effective neighborhood functions for the flexible job shop problem. Many authors have proposed a method of assigning operations to machines and then determining sequence of operations on each machines. Such an approach is followed by Brandimarte, 1993 and Pauli, 1995. These authors solved the assignment problem (i.e. using dispatching rules) and next used metaheuristics to solve the job shop problem. Also genetic approaches have been adopted to solve the flexible job shop problem. Recent works are these of Jia et al., 2003, Ho and Tay, 2004, Kacem et al., 2002 and Pezzella et al., 2008. Gao, Sun, and Gen (2008) proposed the hybrid genetic and variable neighborhood descent algorithm for this problem. There are only a few papers considering parallel algorithms for the FJSP. Yazdani, Amiri, and Zandieh (2010) propose a parallel variable neighborhood search (VNS) algorithm for the FJSP based on independent VNS runs. Defersha and Chen (2009) describe a coarse-grain version of the parallel genetic algorithm for the considered FJSP basing on island-model of parallelization focusing on genetic operators used and scalability of the parallel algorithm. Both papers are focused on parallelization side of the programming methodology and they do not use any special properties of the FJSP. In this paper we propose a parallel double-level metaheuristic approach for the flexible job shop problem based on two methods implemented on the higher level: tabu search and population-based approach. Additionally we have implemented the new method of the neighborhood determination (so-called t-moves) for the considered problem. We apply INSertion Algorithm INSA, ( Nowicki & Smutnicki, 1996) and Tabu Search Algorithm with Backtracking TSAB, ( Nowicki & Smutnicki, 1996) on the second level of parallelism. Using this method we have obtained the new best known solutions for the benchmark instances of Barnes and Chambers (1996) from the literature.

We have discussed a new approach to the scheduling problems with parallel machines, where the assignment of operations to machines defines a classical problem without parallel machines. We propose double-level parallel metaheuristics, where each solution of the higher level, i.e. jobs assignment to machines, defines an NP-hard job shop problem, which we solve by the second metaheuristics – we call such an approach meta2heuristics. On the Machine Selection Module (higher level), we apply two metaheuristics: the tabu search and the population-based approach to determine an assignment of operations to machines. The distribute tabu search threads are used as Operations Scheduling Module (lower level). Using the exact algorithms on both levels (i.e. branch and bound) makes possible to obtain an optimal solution of the problem.