A Pareto archive particle swarm optimization for multi-objective job shop scheduling

doi:10.1016/j.cie.2007.11.007

Computers & Industrial Engineering

Volume 54, Issue 4, May 2008, Pages 960-971

https://doi.org/10.1016/j.cie.2007.11.007 Get rights and content

Abstract

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.

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 form $\begin{matrix} \max y = f (\vec{X}) = [f_{1} (\vec{X}), f_{2} (\vec{X}), \dots f_{M} (\vec{X})] \\ Subject to g_{i} (\vec{X}) ⩽ 0 i = 1, 2, \dots D \end{matrix}$ where $\vec{X} = (x_{1}, x_{2} \dots x_{n})^{T}$ is called decision vector, $\vec{X} \in Θ \in R^{n}$ , Θ is search space. y ∈ Y is objective vector and Y is objective space. g_i is a constraint. For simplicity, we suppose that all f_k(k = 1, 2, ⋯ , M) is greater than zero in this paper. If f_k ⩽ 0, we replace f_k with f_k + τ. 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 ${\vec{G}}_{t}$ 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 $MOPSO$ 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 $MOPSO$ 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)

J.E.C. Arroyo et al.
Genetic local search for multi-objective flow shop scheduling problems
European Journal of Operational Research
(2005)
S. Esquivel et al.
Enhanced evolutionary algorithm for single and multi-objective optimization in job shop scheduling problem
Knowledge-Based System
(2002)
M. Sakawa 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)
W. Xia et al.
An effective hybridization approach for multi-objective flexible job-shop scheduling
Computers and Industrial Engineering
(2005)
C.A.C. Coello et al.
Handling multiple objectives with particle swarm optimization
IEEE Transactions on Evolutionary Computation
(2004)
K. Deb et al.
Simulated binary crossover for continuous search space
Complex Systems
(1995)
K. Deb et al.
A fast and elitist multi-objective genetic algorithms: NSGA-II
IEEE Transactions on Evolutionary Computation
(2002)

There are more references available in the full text version of this article.

Cited by (108)

Design of buoy network in port water area for monitoring air pollution: A robust optimization approach
2023, Ocean and Coastal Management
Buoy network is a promising technique to monitor air pollution in port water area, which is not limited by terrain and can provide continuous measurements at a low cost. Determining the number and location of buoys is a key issue in the design of the buoy network, however, it is affected by stochasticity of wind direction, wind speed, and emission intensity of ship exhaust. Therefore, a robust optimization approach is proposed to solve the problem of how to design buoy network in port water area for monitoring air pollution, i.e., to determine the number and location of buoys, with consideration of stochastic ship exhaust emissions and wind conditions. First, a bi-objective robust optimization model is developed based on the concept of p-robust to maximize monitoring capacity and minimize costs of buoy network. A method for constructing stochastic scenarios is subsequently proposed by combining Latin Hypercube Sampling, ship emission inventory, and atmospheric diffusion simulation. Then, a solution algorithm integrating Epsilon-constraint and Nash bargaining solution methods is presented to solve the model. Finally, a container port in eastern China is selected as a study case. Finally, the relative regret of the obtained robust layout is less than 13.04%. Results show that improving monitoring capacity and cross-scenario robustness is premised on increasing costs, decision-makers need to balance these aspects and design a buoy network with actual budgets. This study provides insights into how to design a buoy network to monitor air pollution in port water areas, and presents methods to determine the decision solution of a bi-objective robust optimization model, which helps maritime and environmental authorities manage ship emissions in port and coastal regions.
An improved NSGA-II with local search for multi-objective integrated production and inventory scheduling problem
2023, Journal of Manufacturing Systems
In the context of collaborative manufacturing, integrated optimization of spare parts production and inventory management is practically important. This paper investigates an integrated production and inventory scheduling (IPIS) problem based on condition-based maintenance. In respect to this problem, whereby inventory and direct supply decisions are made simultaneously to achieve a better reduction in total inventory holding costs, total tardiness and total makespan, a multi-objective IPIS model is developed. An improved non-dominated sorting genetic algorithm-II with local search (INSGA-II_LS) is proposed for the multi-objective IPIS model. In INSGA-II_LS, the encoding and population initialization suited for IPIS are designed. The detailed presentation of operators of crossover, mutation, and local search that designed for the proposed IPIS problem then follows. The mathematical programming solver CPLEX and three multi-objective evolutionary algorithms called SPEA2, PESA-II, MOEA/D are designed for comparisons against INSGA-II_LS. Experimental results show the superiority of the proposed INSGA-II_LS for the IPIS problem with respect to various multi-objective performance metrics, especially for large-scale instances.
Bound-guided hybrid estimation of distribution algorithm for energy-efficient robotic assembly line balancing
2020, Computers and Industrial Engineering
Under the pressure of climate change, energy-efficient manufacturing has attracted much attention. Robotic assembly lines are widely-used in automotive and electronic manufacturing. It is necessary to consider the energy saving and economic criteria simultaneously when robots are utilized to operate assembly tasks replacing human labor. This paper addresses an energy-efficient robotic assembly line balancing (EERALB) problem with the criteria to minimize both the cycle time and total energy consumption. We present a multi-objective mathematical model and propose a bound-guided hybrid estimation of distribution algorithm to solve the problem. When designing the optimization algorithm, we adopt estimation of distribution algorithm (EDA) to tackle the task assignment, and design a non-dominated robot allocation (NGRA) heuristic which is embedded into the EDA to allocate suitable robot to each workstation. Moreover, we propose a bound-guided sampling (BGS) method, which is able to reduce the search space of EDA and focus the search on the promising area. The computational complexity of the proposed algorithm is analyzed and the effectiveness of the proposed NGRA and BGS is tested. In addition, we compare the performances of the proposed mathematical model and the proposed algorithm with those of the existing model and algorithms on a set of widely-used benchmark instances. Comparative results demonstrate the effectiveness of the proposed model and algorithm.
Infinitely repeated game based real-time scheduling for low-carbon flexible job shop considering multi-time periods
2020, Journal of Cleaner Production
Citation 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.
Production scheduling has great significance for optimizing tasks distribution, reducing energy consumption and mitigating environmental degradation. Currently, the research of production scheduling considering energy consumption mainly focuses on the traditional manufacturing workshop. With the wide application of the Internet of Things (IoT) technology, the real-time data of manufacturing resources and production processes can be retrieved easily. These manufacturing data can provide opportunities for manufacturing enterprises to reduce energy consumption and enhance production efficiency. To achieve these targets, a multi-period production planning based real-time scheduling (MPPRS) approach for the IoT-enabled low-carbon flexible job shop (LFJS) is presented in this study to carry out real-time scheduling based on the real-time manufacturing data. Then, the mathematical models of real-time scheduling are established to achieve production efficiency improvement and energy consumption reduction. To obtain a feasible solution, an infinitely repeated game optimization approach is used. Finally, a case study is implemented to analyse and discuss the effectiveness of the proposed method. The results show that in general, the proposed method can achieve better results than the existing dynamic scheduling methods.
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 Engineering
Industries are looking for ways to expand their competitive advantages, a way is optimizing their production, and in this context, they found solutions in activities of production scheduling. The production job-shop scheduling can be a complex problem of combination. The Flexible Job-shop Scheduling Problem (FJSP) is an extension of the job-shop problem and has been widely reported in the literature. Thus, new optimization algorithms continues to be developed and evaluated, in special, artificial intelligence algorithms of the swarm type presented favorable results. In the FJSP context, this research presents the resolution of the FJSP multi-objective, using a hierarchical approach that divides the problem into two sub-problems, being the Particle Swarm Optimization (PSO), responsible for resolving the routing sub-problem, and Random Restart Hill Climbing (RRHC) for the resolution of scheduling sub-problem. The implementation of the proposed hybrid algorithm has new strategies in the population initialization, displacement of particles, stochastic allocation of operations, and management of scenarios partially and totally flexible. Experimental results using technical benchmarks problems are conducted, and proved the effectiveness of the hybridization, and the advantage of PSO + RRHC algorithm compared to others local search algorithms in the resolution of the scheduling problem.
Multi-objective hybrid job-shop scheduling with multiprocessor task (HJSMT) problem with cooperative effect
2024, Journal of Intelligent and Fuzzy Systems

View all citing articles on Scopus

View full text

A Pareto archive particle swarm optimization for multi-objective job shop scheduling

Abstract

Introduction

Section snippets

Basic concepts

Problem formulation

Particle swarm optimization

A Pareto archive particle swarm optimization

Simulation results

Conclusions

Acknowledgements

European Journal of Operational Research

Knowledge-Based System

European Journal of Operational Research

Computers and Industrial Engineering

Handling multiple objectives with particle swarm optimization

IEEE Transactions on Evolutionary Computation

Simulated binary crossover for continuous search space

Complex Systems

A fast and elitist multi-objective genetic algorithms: NSGA-II

IEEE Transactions on Evolutionary Computation