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

Over the past few years, a continually increasing number of research efforts have investigated the application of evolutionary computation techniques for the solution of scheduling problems. Scheduling can pose extremely complex combinatorial optimization problems, which belong to the NP-hard family. Last enhancements on evolutionary algorithms include new multirecombinative approaches. Multiple Crossovers Per Couple (MCPC) allows multiple crossovers on the couple selected for mating and Multiple Crossovers on Multiple Parents (MCMP) do this but on a set of more than two parents. Techniques for preventing incest also help to avoid premature convergence. Issues on representation and operators influence efficiency and efficacy of the algorithm. The present paper shows how enhanced evolutionary approaches, can solve the Job Shop Scheduling Problem (JSSP) in single and multiobjective optimization.

Due to its complexity [1] and reflecting the industrial relevance of this application domain, a variety of evolutionary schedulers based on genetic algorithms have been reported in the literature in the past [2], [3], [4], [5], [6], [7], [8], [9], [10] and [11]. In general, the task of scheduling is the allocation of jobs over time when limited resources are available, where a number of objectives should be optimized, and several constraints must be satisfied. A job is determined by a predefined set of operations, and the result of a scheduling algorithm is a schedule that contains the start times and allocation of resources to each operation [12]. Improvements in evolutionary algorithms (EAs) have been recently found by using a multiplicity feature, which allows multiple recombination on a couple of parents or on multiple parents [13], [14], [15] and [16]. The method was successfully applied to multimodal optimization problems. As a consequence of this approach, it was detected that all individuals of the final population are much more centered on the optimum. This is an important issue when the application requires provision of multiple alternative near-optimal solutions confronting system dynamics as in production planning. The idea of incest prevention, was initially proposed by Eshelman and Shaffer [17] and it showed its benefits to avoid premature convergence. The method avoided mating of pairs showing similarities based on the parents' Hamming distance. Incest prevention was extended in an earlier work by maintaining information about ancestors within the chromosome and modifying the selection for reproduction in order to prevent mating of individuals belonging to the same ‘family’, for a predefined number of generations. This novel approach was also tested on a set of multimodal functions. Description of experiments and analyses of improved results can be seen in Ref. [18]. Current trends in chromosome representation are problem-dependent and genetic operators are closely related to representation. In scheduling the quality of a schedule is measured by means of an objective function, which assigns a numerical value to a schedule. In our case, for single objective optimization the completion time of the last job abandoning the system (makespan) is optimized. For multiobjective optimization, an aggregative approach with three objectives (makespan, global earliness and weighted completion time) was first considered, then a Pareto optimality problem with two objectives (makespan, mean absolute deviation from a common due date) was studied. Section 2 discusses multirecombination and incest prevention as means to enhance EAs. Section 3 is related to single objective JSSP optimization. Section 4 discusses aggregative and Pareto multiobjective JSSP optimizations. Section 5 discusses the conclusions.

Evolutionary algorithms have been proved as efficient tools to face scheduling problems. The effectiveness of evolutionary computation depends on the representation used for the problem solutions, the operators used and the configuration of the evolutionary algorithm. These ideas are not new and have been recognized for some time. This contribution shows the application of enhanced evolutionary algorithms to the Job Shop Scheduling Problem in single and multiobjective optimization. Enhancements are primarily related to multirecombination (MCPC and MCMP). Also, the extended incest prevention to avoid premature convergence was implemented and the modified ordered crossover (MOX) was introduced to generate feasible offspring when operation-based representation (OBR) is used. In single objective optimization a first approach with multirecombination combined with incest prevention was undertook for different scanning crossover methods under a decoder representation. Results indicated that USX performs similarly to other more complex methods (FBSX and OBSX) and that incest prevention is too expensive in processing time without providing noticeable extra benefits in the quality of results. Consequently, further work concentrated on a hybrid approach including multiplicity of crossovers and parents (MCMP) coupled with a more problem specific representation (PRB) that triggers a priority dispatching rule when conflicts are to be resolved. The same testing set was used and after a series of trials the analysis of results suggests that: MCMP-PBR reaches the optimum for any (n1, n2) combination for la06, la01, la12 and la15 instances. When instance complexity increases it became harder for both algorithms to find the optimum and this problem is stronger under MCMP-Dec where a tendency to stagnate the search is detected. Both algorithms find near optimal solutions in less than 3 minutes running time in standard workstations. In general, MCMP-PBR performs better than MCMP-Dec. In multiobjective optimization aggregative and Pareto optimality approaches were undertaken. For the aggregative approach, a multistage evolutionary algorithm (MSE) was implemented. Independent and unified evolution, were introduced to obtain partial optimization of three distinct criteria, f1, f2 and f3, and the aggregation criterion f at the same time. Results of these preliminary experiments with MSE show some enhancements when compared with the conventional evolutionary approach (SGA). In general, the overall performance is slightly better in big instances and the near optimal solutions, under each individual criterion, are also provided. This later additional feature can be of utmost importance in the decision making process for multiobjective optimization. To build a Pareto front a multi-recombinated cooperative population search method (CPS-MCPC), was implemented and contrasted against a single-recombinated cooperative population search method (CPS-SCPC). Both methods were run under, three well-known representations (PLR, JBR, and OBR). A novel MOX operator for crossover was designed to generate valid offspring for a problem specific representation (OBR). As results of these experiments we can conclude that, independently of the coding technique adopted, in most cases CPS-MCPC gives an indication of building better Pareto fronts. This was shown by the achievement of improved, and more densely and evenly distributed fronts. Moreover, the final population obtained under the novel approach is grouped around compromise solutions. The latter fact shows that the alternative solutions provided by multirecombination, attempt to balance the damage caused on the conflicting objectives when one of them is arbitrarily chosen for improvement. These preliminary results are promising and encourage us to deep forward investigation in single and multiobjective scheduling problems by using multirecombination with better representations for the JSSP. An open remaining question is the optimal setting of the numbers n1and n2 of crossovers and parents, which could be self-adapted. Other variants of multiplicity of parents and crossovers are under study to establish the abilities and possible limitations of this approach.