A Pareto archive particle swarm optimization for multi-objective job shop scheduling
Introduction
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.
Section snippets
Basic concepts
The general multi-objective optimization problem is of the formwhere is called decision vector, , Θ is search space. y ∈ Y is objective vector and Y is objective space. gi is a constraint. For simplicity, we suppose that all fk(k = 1, 2, ⋯ , M) is greater than zero in this paper. If fk ⩽ 0, we replace fk with fk + τ. Where τ is a big enough positive number.
The following basic concepts are often used in multi-objective
Problem formulation
Determining an efficient scheduling for the general shop problem has become the subject of research for more than 50 years. The elements of JSSP are the set of machines and a collection of jobs to be scheduled. The processing of a job on a certain machine is referred to as an operation. The processing time of each operation are fixed and known in advance. Each job passes each machine exactly once in a prescribed sequence and should be delivered before due date.
The minimization of cost and the
Particle swarm optimization
PSO is a population-based stochastic optimization technique inspired by the choreography of a bird flock. This technique has good performance, low computational cost and easy implementation. Due to these advantages, PSO has attracted significant attentions from researchers around the world since its introduction in 1995.
A Pareto archive particle swarm optimization
Archive maintenance and selection are two main steps in MOPSO. These two steps are independently implemented in most cases. This paper combines these two steps and constructs a new MOPSO.
Simulation results
In this section, we first describe SPEA2 and a MOPSO (Coello et al., 2004) called for simplicity and test problems. Then we perform sensitivity analyses and finally compare the computational results of three algorithms.
Conclusions
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 and obtains better computational results than SPEA2 for most of the problems.
In previous
Acknowledgements
This research is supported by China Hubei Provincial Science and Technology Department under grant science foundation project (2007ABA332). The authors also want to express their deepest gratitude to the anonymous reviewers for their incisive and seasoned suggestions.
References (15)
- et al.
Genetic local search for multi-objective flow shop scheduling problems
European Journal of Operational Research
(2005) - et al.
Enhanced evolutionary algorithm for single and multi-objective optimization in job shop scheduling problem
Knowledge-Based System
(2002) - et al.
Fuzzy programming for multi-objective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithm
European Journal of Operational Research
(2000) - et al.
An effective hybridization approach for multi-objective flexible job-shop scheduling
Computers and Industrial Engineering
(2005) - et al.
Handling multiple objectives with particle swarm optimization
IEEE Transactions on Evolutionary Computation
(2004) - et al.
Simulated binary crossover for continuous search space
Complex Systems
(1995) - et al.
A fast and elitist multi-objective genetic algorithms: NSGA-II
IEEE Transactions on Evolutionary Computation
(2002)
Cited by (108)
Design of buoy network in port water area for monitoring air pollution: A robust optimization approach
2023, Ocean and Coastal ManagementAn improved NSGA-II with local search for multi-objective integrated production and inventory scheduling problem
2023, Journal of Manufacturing SystemsBound-guided hybrid estimation of distribution algorithm for energy-efficient robotic assembly line balancing
2020, Computers and Industrial EngineeringInfinitely repeated game based real-time scheduling for low-carbon flexible job shop considering multi-time periods
2020, Journal of Cleaner ProductionCitation Excerpt :In particular, researchers have realized that appropriate scheduling mechanisms and methods could play a crucial role in energy-saving during the production execution stage (Dai et al., 2015; Yan et al., 2016; Raileanu et al., 2017). Moreover, production scheduling has attracted much attention (Lei, 2008; Renna, 2010), especially for flexible job shop scheduling (FJSS) problem (Jula and Kones, 2013; Nouiri et al., 2015). However, most research on this topic assumed that the production environment is static, thereby no unexpected disruption occurred during the production processes.
A new approach to solve the flexible job shop problem based on a hybrid particle swarm optimization and Random-Restart Hill Climbing
2018, Computers and Industrial EngineeringMulti-objective hybrid job-shop scheduling with multiprocessor task (HJSMT) problem with cooperative effect
2024, Journal of Intelligent and Fuzzy Systems