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

Most previous research into the job-shop scheduling problem has concentrated on finding a single optimal solution (e.g., makespan), even though the actual requirement of most production systems requires multi-objective optimization. The aim of this paper is to construct a particle swarm optimization (PSO) for an elaborate multi-objective job-shop scheduling problem. The original PSO was used to solve continuous optimization problems. Due to the discrete solution spaces of scheduling optimization problems, the authors modified the particle position representation, particle movement, and particle velocity in this study. The modified PSO was used to solve various benchmark problems. Test results demonstrated that the modified PSO performed better in search quality and efficiency than traditional evolutionary heuristics.

The job-shop scheduling problem (JSP) has been studied for more than 50 years in both academic and industrial environments. Jain and Meeran (1999) provided a concise overview of JSPs over the last few decades and highlighted the main techniques. The JSP is the most difficult class of combinational optimization. Garey, Johnson, and Sethi (1976) demonstrated that JSPs are non-deterministic polynomial-time hard (NP-hard); hence we cannot find an exact solution in a reasonable computation time. The single-objective JSP has attracted wide research attention. Most studies of single-objective JSPs result in a schedule to minimize the time required to complete all jobs, i.e., to minimize the makespan (Cmax)(Cmax). Many approximate methods have been developed to overcome the limitations of exact enumeration techniques. These approximate approaches include simulated annealing (SA) (Lourenço, 1995), tabu search (Nowicki and Smutnicki, 1996, Pezzella and Merelli, 2000 and Sun et al., 1995) and genetic algorithms (GA) (Bean, 1994, Gonçalves et al., 2005, Kobayashi et al., 1995 and Wang and Zheng, 2001). However, real-world production systems require simultaneous achievement of multiple objective requirements. This means that the academic concentration of objectives in the JSP must been extended from single to multiple. Recent related JSP research with multiple objectives is summarized as below. Ponnambalam, Ramkumar, and Jawahar (2001) has offered a multi-objective GA to derive optimal machine-wise priority dispatching rules for resolving job-shop problems with objective functions that consider minimization of makespan, total tardiness, and total machine idle time. Ponnambalam’s multi-objective genetic algorithm (MOGA) has been tested with various published benchmarks, and is capable of providing optimal or near-optimal solutions. A Pareto front provides a set of best solutions to determine the tradeoffs between the various objects, and good parameter settings and appropriate representations can enhance the behavior of an evolution algorithm. Esquivel, Ferrero, and Gallard (2002) studied the influence of distinct parameter combinations as well as different chromosome representations. Initial results showed that: (i) larger numbers of generations favor the building of a Pareto front because the search process does not stagnate, even though it may be rather slow, (ii) Multi-recombination helps to speed the search and to find a larger set size when seeking the Pareto optimal set, and (iii) operation-based representation is better than priority-list and job-based representation selected for contrast under recombination methods. The Pareto archived simulated annealing (PASA) method, a meta-heuristic procedure based on the SA algorithm, was developed by Suresh and Mohanasndaram (2006) to find non-dominated solution sets for the JSP with the objectives of minimizing the makespan and the mean flow time of jobs. The superior performance of the PASA can be attributed to the mechanism it uses to accept the candidate solution. Candido, Khator, and Barcia (1998) addressed JSPs with numbers of more realistic constraints, such as jobs with several subassembly levels, alternative processing plans for parts and alternative resources of operations, and the requirement for multiple resources to process an operation. The robust procedure worked well in all problem instances and proved to be a promising tool for solving more realistic JSPs. Lei and Wu (2006) first designed a crowding-measure-based multi-objective evolutionary algorithm (CMOEA) makes use of the crowding-measure to adjust the external population and assign different fitness for individuals. Compared to the strength Pareto evolutionary algorithm, CMOEA performs well in job-shop scheduling with two objectives including minimization of makespan and total tardiness. One of the latest evolutionary techniques for unconstrained continuous optimization is particle swarm optimization (PSO) proposed by Kennedy and Eberhart (1995). PSO has been successfully used in different fields due to its ease of implementation and computational efficiency. Even so, application of PSO to the combination optimization problem is rare. Coello, Plido, and Lechga (2004) provided an approach in which Pareto dominance is incorporated into PSO to allow the heuristic to handle problems with several object functions. The algorithm uses a secondary repository of particles to guide particle flight. That approach was validated using several test functions and metrics drawn from the standard literature on evolutionary multi-objective optimization. The results show that the approach is highly competitive. Liang, Ge, Zho, and Guo (2005) invented a novel PSO-based algorithm for JSPs. That algorithm effectively exploits the capability of distributed and parallel computing systems, with simulation results showing the possibility of high-quality solutions for typical benchmark problems. Lei (2008) presented a PSO for the multi-objective JSP to minimize makespan and total job tardiness simultaneously. Job-shop scheduling can be converted into a continuous optimization problem by constructing the corresponding relationship between a real vector and a chromosome obtained using the priority rule-based representation method. The global best position selection is combined with crowding-measure-based archive maintenance to design a Pareto archive PSO. That algorithm is capable of producing a number of high-quality Pareto optimal scheduling plans. Hybrid algorithms that combine different approaches to build on their strengths have led to another branch of research. Wang and Zheng (2001) combined GA with SA in a hybrid framework, in which the GA was introduced to present a parallel search architecture, and SA was used to increase the probability of escape from local optima at high temperatures. Computer simulation results showed that the hybrid strategy was very effective and robust, and could find optima for almost all benchmark instances. Xia and Wu (2005) developed an easily implemented approach for the multi-objective flexible JSP based on the combination of PSO and SA. They demonstrated that their proposed algorithm was a viable and effective approach to the multi-objective flexible JSP, especially for large-scale problems. Ripon (2007) extended the idea in the jumping genes genetic algorithm, a hybrid approach capable of searching for near-optimal and non-dominated solutions with better convergence by simultaneously optimizing criteria. Previous literature indicates that there has been little study of the JSP with multiple objectives. In this study, we use a new evolutionary PSO technique to solve the JSP with multiple objectives.

While there has been a large amount of research into the JSP, most of this has focused on minimizing the maximum completion time (i.e., makespan). There exist other objectives in the real-world, such as the minimization of machine idle time that might help improve efficiency and reduce production costs. PSO, inspired by the behavior of birds in flocks and fish in schools, has the advantages of simple structure, easy implementation, immediate accessibility, short search time, and robustness. However, few applications of PSO to multi-objective JSPs can be found in the literature. Therefore, we presented a MOPSO method for solving the JSP with multiple objectives, including minimization of makespan, total tardiness, and total machine idle time. The original PSO was proposed for continuous optimization problems. To make it suitable for job-shop scheduling (i.e., a combinational problem), we modified the representation of particle position, particle movement, and particle velocity. We also introduced a mutation operator and used a diversification strategy. The results demonstrated that the proposed MOPSO could obtain more optimal solutions than the MOGA. The relative error ratios of each problem scenario in our MOPSO algorithm were less than in the MOGA. The performance measure results also revealed that the proposed MOPSO algorithm outperformed MOGA in simultaneously minimizing makespan, total tardiness, and total machine idle time. We will attempt to apply MOPSO to other shop scheduling problems with multiple objectives in future research. Other possible topics for further study include the modification of the particle position representation, particle movement, and particle velocity. In addition, issues related to Pareto optimization, such as solution maintenance strategy and performance measurement, merit future investigation.