زمان بندی تولید کارگاهی انعطاف پذیر همراه با الگوریتم جستجوی محله متغیر موازی

Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. FJSP is NP-hard and mainly presents two difficulties. The first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on the machines. This paper proposes a parallel variable neighborhood search (PVNS) algorithm that solves the FJSP to minimize makespan time. Parallelization in this algorithm is based on the application of multiple independent searches increasing the exploration in the search space. The proposed PVNS uses various neighborhood structures which carry the responsibility of making changes in assignment and sequencing of operations for generating neighboring solutions. The results obtained from the computational study have shown that the proposed algorithm is a viable and effective approach for the FJSP.

Scheduling is the allocation of resources to perform a set of tasks over a period of time. Many real scheduling problems in the manufacturing industries are quite complex and very difficult to be solved by conventional optimization techniques (Watanabe, Ida, & Gen, 2005). The complexity of these problems has a direct dependence on constraints and shop environments upon which these problems are defined. The job-shop scheduling problem (JSP) is one of the hardest combinatorial optimization problems in the field of scheduling. JSP consists in performing a set of n jobs on a set of m machines, where the processing of each job i is composed of nini operations performed on these machines. This problem aims to find the appropriate sequencing of operations on the machines to optimize the performance indicator. Herein, a typical performance indicator for JSP is the makespan, which is defined as the time needed to complete all the jobs. It is well known that this problem is NP-hard ( Garey, Johnson, & Sethi, 1976). In order to match nowadays market requirements, manufacturing systems have to become more flexible and efficient. To achieve these objectives, the systems need not only the automated and flexible machines, but also the flexible scheduling systems. The flexible job-shop scheduling problem (FJSP) is a generalization of the classical JSP, where operations are allowed to be processed on any among a set of available machines. In fact, the FJSP mainly presents two difficulties. The first one is to assign each operation to a machine out of a set of capable machines, and the second one is to sequence the assigned operations on all machines. The FJSP is a much more complex version of the JSP, so the FJSP is strongly NP-hard and combinatorial. Although the complexity of FJSP is well-known, there are far more literatures focusing on JSP rather than on FJSP. Brucker and Schlie (1990) are the pioneers in addressing FJSP. They developed a polynomial algorithm for solving this problem with two jobs. Also various heuristic methods such as dispatching rules and local search and meta-heuristic methods such as tabu search (TS), simulated annealing (SA), and genetic algorithm (GA) have been applied for solving FJSP in recent years. These heuristic and meta-heuristic algorithms can be classified into two main categories: hierarchical approaches and integrated approaches. In hierarchical approaches, the assignment of operations to machines and the sequencing of operations on the machines are treated separately, whereas in integrated approaches, the assignment and sequencing problems are not separated. The hierarchical approaches are based on the idea of decomposing the original problem in order to reduce its complexity. Despite the fact that the integrated approaches are much more difficult to solve, they generally achieve better results. Brandimarte (1993) applied a hierarchical approach for FJSP based on decomposition. He solved the routing sub-problem using some existing dispatching rules and then concentrated on sequencing sub-problem which is solved by using a TS algorithm. Hurink, Jurisch, and Thole (1994) based on the integrated approach and Barnes and Chambers (1996) based on the hierarchical approach developed TS algorithms to solve FJSP. Dauzére-Pérés and Paulli (1997) defined a new neighborhood structure for the problem where there is no distinction between reassigning and resequencing an operation, and proposed a TS algorithm based on the integrated approach. Mastrolilli and Gambardella (2000) improved Dauzére-Pérés TS techniques and presented two neighborhood functions. Chen, Ihlow, and Lehmann (1999) developed a GA for FJSP. They split the chromosome representation into two parts, the first one defined the routing policy, and the second one delineated the sequence of operations on each machine. Kacem et al., 2002a and Kacem et al., 2002b proposed a GA controlled by the assigned model which was generated by the approach of localization and they used it to solve mono-objective and multi-objective FJSP. Zhang and Gen (2005) proposed a multistage operation-based GA to deal with the problem from the point view of dynamic programming. Xia and Wu (2005) worked on a hierarchical approach for solving multi-objective FJSP. The approach made use of particle swarm optimization (PSO) to assign operations to machines and SA algorithm to schedule operations on each machine. Fattahi, Saidi Mehrabad, and Jolai (2007) proposed a mathematical model and two meta-heuristics algorithms (SA and TS) for solving FJSP. Moreover, considering two developed meta-heuristics and concerning the integrated and hierarchical approaches, they presented six different algorithms. Pezzella, Morganti, and Ciaschetti (2008) propounded a GA for FJSP based on the integrated approach, in which a mix of different strategies for generating the initial population, selecting individuals for reproduction, and reproducing new individuals is presented. Gao, Sun, and Gen (2008) studied the FJSP with three objectives: min makespan, min maximal machine workload and min total workload. They developed a hybrid genetic algorithm (hGA) based on the integrated approach for this problem. Given the literature of FJSP, the heuristics and meta-heuristics have corroborated their merits to solve the FJSP. Variable neighborhood search (VNS) (Amiri et al., 2009; Hansen and Mladenovic, 2001 and Mladenovic and Hansen, 1997) is a modern meta-heuristic based on systematic changes of the neighborhood structure within a search to solve combinatorial optimization problems. In this paper, we develop a parallel variable neighborhood search (PVNS) algorithm for solving FJSP. Parallelization in the presented optimization method increases the diversification and the exploration in the search space. In this method, neighborhood structures related to sequencing and assignment problems are employed to generate a neighboring solution. Considering the aforementioned neighborhood structures, the proposed algorithm executes parallel search process in the solution space. The rest of the paper is organized as follows. In Section 2, we present the formulation and constraints of the problem. Section 3 which is subdivided into five subdivisions explains proposed PVNS algorithm for solving FJSP. In Section 4, the computational study performed with the proposed algorithm and its results are reported. The conclusion and some further research suggestions are presented in Section 5.

In this paper, we developed parallel variable neighborhood search algorithm for the flexible job-shop scheduling problem. In the presented optimization method, the external loop controlled the stop condition of algorithm and the internal loop executed search process. To search solution space, internal loop used two main search engines of VNS, i.e., shake and local search procedures. In addition, two neighborhood structures related to sequencing problem and three neighborhood structures related to assignment problem were employed to generate neighboring solutions in shake and local search procedures of the presented algorithm. Another effectively useful operator in the searching solution space was a combined neighborhood structure that generated a neighboring solution by implementing changes in both assigning and sequencing of the candidate solution. Parallelism in the proposed algorithm caused the improvement in search process ability. 181 benchmark problems of FJSP were used to evaluate the performance of the presented algorithm. The computational results revealed the competent performance of the proposed algorithm to optimize the FJSP. The implementation of various states of parallelization for VNS algorithm in solving FJSP and considering other performance indicators and process constraints are suggested for further studies.