An improved particle swarm optimization algorithm for flowshop scheduling problem

The flowshop scheduling problem has been widely studied and many techniques have been applied to it, but few algorithms based on particle swarm optimization (PSO) have been proposed to solve it. In this paper, an improved PSO algorithm (IPSO) based on the “alldifferent” constraint is proposed to solve the flow shop scheduling problem with the objective of minimizing makespan. It combines the particle swarm optimization algorithm with genetic operators together effectively. When a particle is going to stagnate, the mutation operator is used to search its neighborhood. The proposed algorithm is tested on different scale benchmarks and compared with the recently proposed efficient algorithms. The results show that the proposed IPSO algorithm is more effective and better than the other compared algorithms. It can be used to solve large scale flow shop scheduling problem effectively.     

A discrete particle swarm optimization algorithm with self-adaptive diversity control for the permutation flowshop problem with blocking

This paper proposes a discrete particle swarm optimization (DPSO) algorithm for the m-machine permutation flowshop scheduling problem with blocking to minimize the makespan, which has a strong industrial background, e.g., many production processes of chemicals and pharmaceuticals in chemical industry can be reduced to this problem. To prevent the DPSO from premature convergence, a self-adaptive diversity control strategy is adopted to diversify the population when necessary by adding a random perturbation to the velocity of each particle according to a probability controlled by the diversity of the current population. In addition, a stochastic variable neighborhood search is used as the local search to improve the search intensification. Computational results using benchmark problems show that the proposed DPSO algorithm outperforms previous algorithms proposed in the literature and that it can obtain 111 new best known upper bounds for the 120 benchmark problems.     

A hybrid meta-heuristic algorithm for optimization of crew scheduling

Crew scheduling problem is the problem of assigning crew members to the flights so that total cost is minimized while regulatory and legal restrictions are satisfied. The crew scheduling is an NP-hard constrained combinatorial optimization problem and hence, it cannot be exactly solved in a reasonable computational time. This paper presents a particle swarm optimization (PSO) algorithm synchronized with a local search heuristic for solving the crew scheduling problem. Recent studies use genetic algorithm (GA) or ant colony optimization (ACO) to solve large scale crew scheduling problems. Furthermore, two other hybrid algorithms based on GA and ACO algorithms have been developed to solve the problem. Computational results show the effectiveness and superiority of the proposed hybrid PSO algorithm over other algorithms.     

Genetic algorithms for flowshop scheduling problems

In this paper, we apply a genetic algorithm to flowshop scheduling problems and examine two hybridizations of the genetic algorithm with other search algorithms. First we examine various genetic operators to design a genetic algorithm for the flowshop scheduling problem with an objective of minimizing the makespan. By computer simulations, we show that the two-point crossover and the shift change mutation are effective for this problem. Next we compare the genetic algorithm with other search algorithms such as local search, taboo search and simulated annealing. Computer simulations show that the genetic algorithm is a bit inferior to the others. In order to improve the performance of the genetic algorithm, we examine the hybridization of the genetic algorithms. We show two hybrid genetic algorithms: genetic local search and genetic simulated annealing. Their high performance is demonstrated by computer simulations.     

An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem

Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. Although the traditional optimization algorithms could obtain preferable results in solving the mono-objective FJSP. However, they are very difficult to solve multi-objective FJSP very well. In this paper, a particle swarm optimization (PSO) algorithm and a tabu search (TS) algorithm are combined to solve the multi-objective FJSP with several conflicting and incommensurable objectives. PSO which integrates local search and global search scheme possesses high search efficiency. And, TS is a meta-heuristic which is designed for finding a near optimal solution of combinatorial optimization problems. Through reasonably hybridizing the two optimization algorithms, an effective hybrid approach for the multi-objective FJSP has been proposed. The computational results have proved that the proposed hybrid algorithm is an efficient and effective approach to solve the multi-objective FJSP, especially for the problems on a large scale.     

Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan

The multistage hybrid flow shop (HFS) scheduling problems are considered in this paper. Hybrid flowshop scheduling problems were proved to be NP-hard. A recently developed cuckoo search (CS) metaheuristic algorithm is presented in this paper to minimize the makespan for the HFS scheduling problems. A constructive heuristic called NEH heuristic is incorporated with the initial solutions to obtain the optimal or near optimal solutions rapidly in the improved cuckoo search (ICS) algorithm. The proposed algorithm is validated with the data from a leading furniture manufacturing company. Computational results show that the ICS algorithm outperforms many other metaheuristics.     

Particle swarm optimization with expanding neighborhood topology for the permutation flowshop scheduling problem

This paper introduces a new algorithmic nature-inspired approach that uses particle swarm optimization (PSO) with different neighborhood topologies, for successfully solving one of the most computationally complex problems, the permutation flowshop scheduling problem (PFSP). The PFSP belongs to the class of combinatorial optimization problems characterized as NP-hard and, thus, heuristic and metaheuristic techniques have been used in order to find high quality solutions in reasonable computational time. The proposed algorithm for the solution of the PFSP, the PSO with expanding neighborhood topology, combines a PSO algorithm, the variable neighborhood search strategy and a path relinking strategy. As, in general, the structure of the social network affects strongly a PSO algorithm, the proposed method using an expanding neighborhood topology manages to increase the performance of the algorithm. As the algorithm starts from a small size neighborhood and by increasing (expanding) in each iteration the size of the neighborhood, it ends to a neighborhood that includes all the swarm, and it manages to take advantage of the exploration abilities of a global neighborhood structure and of the exploitation abilities of a local neighborhood structure. In order to test the effectiveness and the efficiency of the proposed method, we use a set of benchmark instances of different sizes and compare the proposed method with a number of other PSO algorithms and other algorithms from the literature.     

An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem

Hybrid flow shops (HFS) are common manufacturing environments in many industries, such as the glass, steel, paper and textile industries. In this paper, we present a particle swarm optimization (PSO) algorithm for the HFS scheduling problem with minimum makespan objective. The main contribution of this paper is to develop a new approach hybridizing PSO with bottleneck heuristic to fully exploit the bottleneck stage, and with simulated annealing to help escape from local optima. The proposed PSO algorithm is tested on the benchmark problems provided by Carlier and Néron. Experimental results show that the proposed algorithm outperforms all the compared algorithms in solving the HFS problem.     

粒子置换的双种群综合学习PSO算法

针对粒子群算法(PSO)种群多样性低和易于陷入局部最优等问题,提出一种粒子置换的双种群综合学习PSO算法(PP-CLPSO)。根据PSO算法的收敛特性和Logistic映射的混沌思想,设计并行进化的PSO种群和混沌化种群,结合粒子编号机制,形成双种群系统中粒子的同号结构和同位结构,其中粒子的惯性权重根据适应度值自适应调节;当搜索过程陷入局部最优时,PSO种群同位结构下适应度值较差的粒子,根据与混沌化种群间的同号结构执行粒子置换操作,实现了双种群系统资源的合理调度,增加了种群的多样性;进而综合双向搜索的同位粒子学习策略和线性递减搜索步长的局部学习策略,进行全局探勘和局部搜索,提高了算法的求解精度。实验选取9个基准测试函数,同时与4个改进的粒子群算法和4个群智能算法进行对比验证,实验结果表明,PP-CLPSO算法在求解精度和收敛速度等方面具备较好的综合性能。     

量子萤火虫算法及在无等待流水调度上的应用

针对无等待流水车间调度问题,提出了一种新颖的量子萤火虫优化算法用于最小化总完工时间．首先,将量子进化机制嵌入萤火虫算法中,并设计一种快速的局部邻域搜索方法,在每次迭代时只搜索部分邻域,同时采用目标增量计算邻域解变化,这样极大地加快了算法迭代速度,加速了算法收敛．最后,应用Taillard基准测试实例仿真,与目前较优的启发式算法IHA（improved heuristic algorithm）和群智能算法DGSO（discrete glowworm swarm optimization）、 GA-VNS（genetic algorithm-variable neighborhood search）及DHS（discrete harmony search）相比较,产生最好解的平均百分比偏差均下降了40％以上．实验结果验证了所提算法在求解无等待流水调度中的优越性．     

A discrete differential evolution algorithm for the permutation flowshop scheduling problem

Very recently, Pan et al. [Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, GECCO07, pp. 126–33] presented a new and novel discrete differential evolution algorithm for the permutation flowshop scheduling problem with the makespan criterion. On the other hand, the iterated greedy algorithm is proposed by [Ruiz, R., & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2033–49] for the permutation flowshop scheduling problem with the makespan criterion. However, both algorithms are not applied to the permutation flowshop scheduling problem with the total flowtime criterion. Based on their excellent performance with the makespan criterion, we extend both algorithms in this paper to the total flowtime objective. Furthermore, we propose a new and novel referenced local search procedure hybridized with both algorithms to further improve the solution quality. The referenced local search exploits the space based on reference positions taken from a reference solution in the hope of finding better positions for jobs when performing insertion operation. Computational results show that both algorithms with the referenced local search are either better or highly competitive to all the existing approaches in the literature for both objectives of makespan and total flowtime. Especially for the total flowtime criterion, their performance is superior to the particle swarm optimization algorithms proposed by [Tasgetiren, M. F., Liang, Y. -C., Sevkli, M., Gencyilmaz, G. (2007). Particle swarm optimization algorithm for makespan and total flowtime minimization in permutation flowshop sequencing problem. European Journal of Operational Research, 177(3), 1930–47] and [Jarboui, B., Ibrahim, S., Siarry, P., Rebai, A. (2007). A combinatorial particle swarm optimisation for solving permutation flowshop problems. Computers & Industrial Engineering, doi:10.1016/j.cie.2007.09.006]. Ultimately, for Taillard’s benchmark suite, four best known solutions for the makespan criterion as well as 40 out of the 90 best known solutions for the total flowtime criterion are further improved by either one of the algorithms presented in this paper.     

Scatter search based particle swarm optimization algorithm for earliness/tardiness flowshop scheduling with uncertainty

Considering the imprecise nature of the data in real-world problems, the earliness/tardiness (E/T) flowshop scheduling problem with uncertain processing time and distinct due windows is concerned in this paper. A fuzzy scheduling model is established and then transformed into a deterministic one by employing the method of maximizing the membership function of middle value. Moreover, an effective scatter search based particle swarm optimization (SSPSO) algorithm is proposed to minimize the sum of total earliness and tardiness penalties. The proposed SSPSO algorithm incorporates the scatter search (SS) algorithm into the frame of particle swarm optimization (PSO) algorithm and gives full play to their characteristics of fast convergence and high diversity. Besides, a differential evolution (DE) scheme is used to generate solutions in the SS. In addition, the dynamic update strategy and critical conditions are adopted to improve the performance of SSPSO. The simulation results indicate the superiority of SSPSO in terms of effectiveness and efficiency.     

具有快速收敛和自适应逃逸功能的粒子群优化算法

为了克服标准粒子群优化算法(PSO)后期收敛速度慢、容易陷入局部最优等缺点,借鉴人工蜂群算法的思想,提出了一种提高收敛速度并且带有自适应逃逸功能的粒子群优化算法(FAPSO)。算法中每进化一次粒子搜索两次：一次全局搜索,一次局部搜索。当粒子陷入局部最优时,通过逃逸功能使粒子重新搜索。8个经典基准测试函数仿真结果表明,改进的粒子群优化算法在收敛速度和寻优精度上均有提高,相对于目前常用的改进粒子群优化算法如CLPSO等,t检验结果说明,新算法具有明显的优势。     

解决作业车间调度的微粒群退火算法*

针对微粒群优化算法在求解作业车间调度问题时存在的易早熟、搜索准确度差等缺点,在微粒群优化算法的基础上引入了模拟退火算法,从而使得算法同时具有全局搜索和跳出局部最优的能力,并且增加了对不可行解的优化,从而提高了算法的搜索效率;同时,在模拟退火算法中引入自适应温度衰变系数,使得SA算法能根据当前环境自动调整搜索条件,从而避免了微粒群优化算法易早熟的缺点。对经典JSP问题的仿真实验表明,与其他算法相比,该算法是一种切实可行、有效的方法。     

Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm

This paper deals with a scheduling problem for reentrant hybrid flowshop with serial stages where each stage consists of identical parallel machines. In a reentrant flowshop, a job may revisit any stage several times. Local-search based Pareto genetic algorithms with Minkowski distance-based crossover operator is proposed to approximate the Pareto optimal solutions for the minimization of makespan and total tardiness in a reentrant hybrid flowshop. The Pareto genetic algorithms are compared with existing multi-objective genetic algorithm, NSGA-II in terms of the convergence to optimal solution, the diversity of solution and the dominance of solution. Experimental results show that the proposed crossover operator and local search are effective and the proposed algorithm outperforms NSGA-II by statistical analysis.     

Multi-objective fuzzy multiprocessor flowshop scheduling

This paper considers a bi-objective hybrid flowshop scheduling problems with fuzzy tasks’ operation times, due dates and sequence-dependent setup times. To solve this problem, we propose a bi-level algorithm to minimize two criteria, namely makespan, and sum of the earliness and tardiness, simultaneously. In the first level, the population will be decomposed into several sub-populations in parallel and each sub-population is designed for a scalar bi-objective. In the second level, non-dominant solutions obtained from sub-population bi-objective random key genetic algorithm (SBG) in the first level will be unified as one big population. In the second level, for improving the Pareto-front obtained by SBG, based on the search in Pareto space concept, a particle swarm optimization (PSO) is proposed. We use a defuzzification function to rank the Bell-shaped fuzzy numbers. The non-dominated sets obtained from each of levels and an algorithm presented previously in literature are compared. The computational results showed that PSO performs better than others and obtained superior results.     

化工工业多品种成批轮番生产的集成分批与调度

针对化工工业流程式多品种成批轮番生产集成分批与调度问题,分析多阶段、共享设备、物料输入输出变动转化率、库存限制和品种切换调整时间的工艺特点,建立连续时间表示的混合整数线性规划模型,提出二维粒子群优化算法。设计粒子编码为生产设备的加工状态,通过有效的解码程序将粒子解释为分批和调度。算法采用收缩算子提高局部求精能力,并引入发散算子和速度扰动策略保持种群的多样性。实验结果表明了所提出的算法具有良好的性能。     

A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application

The assembly flowshop scheduling problem has been addressed recently in the literature. There are many problems that can be modeled as assembly flowshop scheduling problems including queries scheduling on distributed database systems and computer manufacturing. The problem has been addressed with respect to either makespan or total completion time criterion in the literature. In this paper, we address the problem with respect to a due date-based performance measure, i.e., maximum lateness. We formulate the problem and obtain a dominance relation. Moreover, we propose three heuristics for the problem: particle swarm optimization (PSO), Tabu search, and EDD. PSO has been used in the areas of function optimization, artificial neural network training, and fuzzy system control in the literature. In this paper, we show how it can be used for scheduling problems. We have conducted extensive computational experiments to compare the three heuristics along with a random solution. The computational analysis indicates that Tabu outperforms the others for the case when the due dates range is relatively wide. It also indicates that the PSO significantly outperforms the others for difficult problems, i.e., tight due dates. Moreover, for difficult problems, the developed dominance relation helps reduce error by 65%.     

A machine-learning based memetic algorithm for the multi-objective permutation flowshop scheduling problem

In recent years, the historical data during the search process of evolutionary algorithms has received increasing attention from many researchers, and some hybrid evolutionary algorithms with machine-learning have been proposed. However, the majority of the literature is centered on continuous problems with a single optimization objective. There are still a lot of problems to be handled for multi-objective combinatorial optimization problems. Therefore, this paper proposes a machine-learning based multi-objective memetic algorithm (ML-MOMA) for the discrete permutation flowshop scheduling problem. There are two main features in the proposed ML-MOMA. First, each solution is assigned with an individual archive to store the non-dominated solutions found by it and based on these individual archives a new population update method is presented. Second, an adaptive multi-objective local search is developed, in which the analysis of historical data accumulated during the search process is used to adaptively determine which non-dominated solutions should be selected for local search and how the local search should be applied. Computational results based on benchmark problems show that the cooperation of the above two features can help to achieve a balance between evolutionary global search and local search. In addition, many of the best known Pareto fronts for these benchmark problems in the literature can be improved by the proposed ML-MOMA.     

最佳维变异粒子群优化算法在传感器调度中应用

粒子群优化(PSO)算法的主要特点是能快速得到问题的解,缺点是容易陷入局部最优.提出了一种利用最佳维变异技术和量子理论方法改进的PSO算法,并应用于目标跟踪传感器调度问题.目标的动力学模型为线性高斯模型,传感器观测值被高斯噪声污染并与目标状态线性相关.对于多传感器单目标跟踪的数学问题,引入提出的最佳维变异PSO算法,在...