روش اکتشافی ترکیبی برای حل دستگاه های موازی مشکل زمان بندی تولید کارگاهی

This paper presents an advanced software system for solving the flexible manufacturing systems (FMS) scheduling in a job-shop environment with routing flexibility, where the assignment of operations to identical parallel machines has to be managed, in addition to the traditional sequencing problem. Two of the most promising heuristics from nature for a wide class of combinatorial optimization problems, genetic algorithms (GA) and ant colony optimization (ACO), share data structures and co-evolve in parallel in order to improve the performance of the constituent algorithms. A modular approach is also adopted in order to obtain an easy scalable parallel evolutionary-ant colony framework. The performance of the proposed framework on properly designed benchmark problems is compared with effective GA and ACO approaches taken as algorithm components.

The job-shop scheduling problem with parallel machines (JSP-PM) represents an important problem encountered in current practice of manufacturing scheduling systems [1] and [2]. It consists of assigning any operation for each job to a resource of a candidate set of identical parallel machines (assigning subproblem), in addition to the classic JSP where the operations must be arranged on each (assigned) resource in order to minimize the makespan (sequencing subproblem). A candidate set of identical parallel machines is termed a machine type [1], a workcenter [2] or also a flexible manufacturing cell [3]. In opposition to classic job-shops where there is a single resource for each machine type, in flexible manufacturing systems (FMS) a number of parallel machines are available in order to both increase the throughput rate and avoid production stop when machines fail or maintenance occurs [4]. According to the α∣β∣γ notation of Graham et al. [5], the problem under consideration can be denoted by FJm∣prec∣Cmax, where the field α denotes a flexible job-shop [6], the field β indicate linear routings, i.e. the occurrence of simple precedence constraints in the job routing and the field γ denotes the makespan which is the adopted measure of performance. The problem is an extension of the classical Jm∥Cmax which is strongly NP-hard [7] and, therefore, unlikely to reach an optimal solution in an acceptable amount of time by a computing strategy. An extensive and rapidly growing series of approaches have been reported in literature, but only approximate or heuristic methods make a tradeoff between solution quality and effective computing times (see [8] and [9] for a review). Recently, genetic algorithms (GA) became the state-of-the-art algorithms when computation time it not a concern [10]. More recently, this approach used in combination with taboo search or ant colony optimization (ACO) achieved good results and drastically reduced the CPU time [11] and [12]. In opposition to JSP, the literature on job-shop scheduling with parallel machines is scarce. As optimization techniques result in exponential computational complexity, until last decade manufacturing systems widely implemented dispatching rules systems [13] and [14]. In the last few years, effective heuristics have become available and some systems are proposed for the literature subject by means of a genetic algorithm [15], a Lagrangian relaxation [16] and an extension of the shifting bottleneck heuristic [17] and [18]. The SB procedure decomposes the overall problem into multiple instances of the scheduling problems for single group of parallel machines. More tractable scheduling subproblems solved by dispatching rules are a result of the decomposition approach. Upasani et al. [19] approach the problem by means of a temporal decomposition method. A rolling horizon (RH) framework, which divides the scheduling problem in subproblems which cover decisions for a limited time period into the future, are more effective to implement dynamic scheduling systems [20] and [21]. More recently an ant colony optimization for FJm∣sjk, prec∣Cmax, is developed where sjk denotes the presence of sequence-dependent setup time [22]. This ACO is quite robust, because it uses a problem representation where assigning and sequencing constraints are deeply integrated. Even though those approaches succeeded in find the best solution in a number of simulated cases, the search efficiency seemed to offer a considerable improvement when evaluated by benchmark problems. ACO and GA, known as population-based algorithms, perform a multiple directed-parallel probabilistic searching technique by maintaining a population of solutions, also referred to as agents, each of these provides the capability of finding near-optimal solutions in a complex multi-dimensional searching space. A GA is modelled on an evolutionary approach, where recombination and selection operators are inspired by the natural evolution process. ACO is an emerging class of research, dealing with swarm intelligence, a set of artificial life methods which exploits the experience of an ant colony as a model of self-organisation in co-operative food retrieval by means of a proper pheromone trail model. Agents are capable of exploring and exploiting pheromone information which has been left on the pheromone trail when they traversed it. A GA provides the advantage of performing a global search, but may cause stagnation or degeneration of search performance [23]. In particular, if GA mimics natural evolution, it should not operate on a single population in which a given individual has the potential to mate with any other partner in the entire population (panmixia). Instead, species are structured and tend to reproduce within subgroups or within neighbourhoods. Among the existing types of structured genetic algorithms, distributed GAs are especially popular [24]. Their premise lies in partitioning the population into several subpopulations, each one being processed by a GA, independently of the others. Furthermore, a sparse migration of individuals produces an exchange of genetic material between the subpopulations that enhances diversity and usually improves the accuracy and efficiency of the algorithm. By making different decisions on the sub-algorithms of a distributed GA through the application of different search strategies, the search occurs at multiple exploration and exploitation levels [10]. Moreover, in recent years it has become evident that concentration on a sole heuristic is rather restrictive. A skilled combination of concepts derived from different heuristics can provide a more efficient behaviour and a higher flexibility when dealing with large-scale and real-world problems. A truly cunning hybrid strategies, combining GA and other systems as dispatching rules, TS or Simulated Annealing (SA). Mönch et al. apply a more sophisticated subproblem solution procedure which hybridizes dispatching rules and GA [25]. A simple priority index allows to select the more profitable batch of jobs from the overall set of batch and a genetic algorithm allows to select the more profitable assignment of the batches to the parallel machines. Wang and Zheng propose a SA procedure which controls the search process by means of an adaptive probability of mutation and an efficient strategy of selection [26]. This method is able to improve the search mechanism of GA. The most general level of distributed search arises when each subpopulation can potentially run a different algorithm; this level is termed the algorithm level [27]. Another orthogonal level of distributed search can be defined by the relationship maintained among the subpopulations. Basically, if the amount of individuals of each subpopulation is fixed during evolution, i.e. the size of a subpopulation is made independent of the current success of its strategy, then it can be considered that the subpopulations are collaborating to find the optimum [28]. Otherwise, the kind of distributed search is competing [29] and [30]. In this context, the paper proposes an easy scalable distributed-collaborative search at the algorithm level between GA and ACO for the job-shop scheduling problem with parallel machines in order to improve the performance of the individual algorithms.

The paper focuses on a challenge distributed-collaborative search algorithm which hybridizes GA and ACO for the job-shop scheduling problem with parallel machines. A number of innovative skills are present in the paper. The first is the use of genetic algorithms and ant colony optimization as a mechanism of collaborative search at the algorithm level. The second aspect concerns the methods of selecting the GA subpopulations and to updating pheromone trails. Finally, the GA counterpart is reinforced in order to tackle stagnation with a method which reinitializes the subpopulations by means of the two-tournament selection. At this stage the system parameter values inherit those of the constituent algorithms. The system is able to find six new optimal solutions and to improve the performance of the constituent algorithms in 77% of proposed benchmarks. Statistical analysis is also employed to better ensure the performance when compared with that of the constituent algorithms. The proposed system performs significantly better than its GA counterpart, while it is very close to the confidence interval of 0.05% of the test statistic which ensures its superiority with respect to the ACO counterpart. As general consideration, the proposed system is a powerful mechanism and an important tool to enhance the searching capability of both genetic algorithms and ant colony systems in the optimization search. As the parameter values which give a good performance for the constituent algorithms are not necessarily good in the hybrid system, it is expected that the proposed system will offer a sharp increase in performance when a similar tool is integrated. Therefore, future work will be directed in two main directions: (i) allowing the system to automatically detect the most performing system parameters as a function of the data entry; (ii) increasing computing speed for real-time response behaviour in dynamic scheduling applications.