بهینه سازی ازدحام ذرات آرشیو « پاره تو» برای برنامه ریزی تولید کارگاهی چند هدفه

In this paper, we present a particle swarm optimization for multi-objective job shop scheduling problem. The objective is to simultaneously minimize makespan and total tardiness of jobs. By constructing the corresponding relation between real vector and the chromosome obtained by using priority rule-based representation method, job shop scheduling is converted into a continuous optimization problem. We then design a Pareto archive particle swarm optimization, in which the global best position selection is combined with the crowding measure-based archive maintenance. The proposed algorithm is evaluated on a set of benchmark problems and the computational results show that the proposed particle swarm optimization is capable of producing a number of high-quality Pareto optimal scheduling plans.

Multi-objective job shop scheduling problem (MOJSSP) is the one with multiple conflicting objectives, which mainly presents some difficulties related to the objectives. If the objectives are combined into a scalar function by using weights, the difficulty is to assign weights for each objective; if all objectives are optimized concurrently, the problem is to design the effective search algorithm for some extra steps and the considerable increment of time complexity. In the past decades, the literature of MOJSSP is notably sparser than the literature of single-objective job shop scheduling problem (JSSP). Sakawa and Kubota (2000) presented a genetic algorithm incorporating the concept of similarity among individuals by using Gantt charts for JSSP with fuzzy processing time and fuzzy due date. The objective is to maximize the minimum agreement index, to maximize the average agreement index and to minimize the maximum fuzzy completion time. Ponnambalam, Ramkumar, and Jawahar (2001) proposed a multi-objective genetic algorithm to derive the optimal machine-wise priority dispatching rules to resolve the conflict among the contending jobs in the Giffler and Thompson procedure (Giffler & Thompson, 1960) applied in job shop scheduling. The objective is to minimize the weighted sum of makespan, the total idle time of machines and the total tardiness. The weights assigned for combining the objectives into a scalar fitness are not constant. Esquivel et al. (2002) proposed an enhanced evolutionary algorithm with new multi-re-combinative operators and incest prevention strategy for single and multi-objective job shop scheduling problem. Kacem, Hammadi, and Borne (2002) presented a combination approach based on the fusion of fuzzy logic and multi-objective evolutionary algorithm to the problems of flexible job shop scheduling. Xia and Wu (2005) proposed a hybrid algorithm of particle swarm optimization (PSO) and simulated annealing to multi-objective flexible job shop scheduling problems. The hybrid algorithm makes use of PSO to assign operations on machines and simulated annealing algorithm to arrange operations on each machine. The above-mentioned approaches optimize the weighted sum of objective functions and can produce one or several optimal solutions. Some studies have attempted to simultaneously optimize all objectives and obtain a group of Pareto optimal solutions. Arroyo and Armentano (2005) presented a genetic local search algorithm with features such as preservation of dispersion in the population, elitism et al. for flow shop scheduling problems in such a way as to provide the decision maker with the approximate Pareto optimal solutions. Lei and Wu (2006) developed a crowding measure-based multi-objective evolutionary algorithm to the problems of job shop scheduling. The proposed algorithm makes use of crowding measure to adjust the external population and assign different fitness for individuals and is applied to MOJSSP to minimize makespan and the total tardiness of jobs. PSO is seldom applied to JSSP since 1995 and the optimization capacity and advantage of PSO on JSSP are not intensively considered. Compared with evolutionary algorithm, PSO has its own superiorities on scheduling. For instance, it is unnecessary for PSO to design the special crossover and mutation operators to avoid the occurrence of the illegal individuals. The main obstacle of directly applying PSO to the combinatorial optimization problems such as JSSP is its continuous nature. To remedy the above drawback, this paper presents an effective approach to convert JSSP to a continuous optimization problem. Once JSSP is converted into the continuous problem, the direct application of PSO becomes possible. In addition, an effective multi-objective particle swarm optimization (MOPSO) is proposed for solving MOJSSP. The proposed algorithm combines the global best position selection with the external archive maintenance, whereas these two steps in most of MOPSO are separately considered. The remainder of the paper is organized as follows. The basic concepts of multi-objective optimization are introduced in Section 2. Section 3 formulates JSSP with multiple objectives. In Section 4, we introduce standard PSO and describe the method which converts scheduling problems into the continuous optimization ones. In Section 5, we describe a Pareto archive particle swarm optimization (PAPSO) for MOJSSP. The proposed algorithm is applied to a set of benchmark problems and the performances of three algorithms are compared in Section 6. Conclusions and remarks for the future work are given in Section 7.

We have proposed an effective method to convert JSSP to a continuous one. This is a new path to apply PSO to the scheduling problem. We also presented a PAPSO for MOJSSP. Unlike previous works, PAPSO combines the global best position selection with archive maintenance. The effectiveness of PAPSO was tested on 18 benchmark problems. The computational results show that PAPSO perform better than MOPSOMOPSO and obtains better computational results than SPEA2 for most of the problems. In previous research, the application of PSO on combinatorial optimization problems such as JSSP is seldom investigated. The main contribution of this study is to provide an effective path to apply PSO to JSSP. Unlike the discrete PSO, the proposed path is simple and easily implemented. Moreover, the existing improvement strategies of PSO can be directly applied for the high-quality solutions. We will take a further discussion on the new path to handle multi-objective scheduling by using PSO algorithm and carry out research into the application of MOPSO to other scheduling problems such as flexible job shop scheduling in the near future.