An effective PSO-based memetic algorithm for flow shop scheduling.

This paper proposes an effective particle swarm optimization (PSO)-based memetic algorithm (MA) for the permutation flow shop scheduling problem (PFSSP) with the objective to minimize the maximum completion time, which is a typical non-deterministic polynomial-time (NP) hard combinatorial optimization problem. In the proposed PSO-based MA (PSOMA), both PSO-based searching operators and some special local searching operators are designed to balance the exploration and exploitation abilities. In particular, the PSOMA applies the evolutionary searching mechanism of PSO, which is characterized by individual improvement, population cooperation, and competition to effectively perform exploration. On the other hand, the PSOMA utilizes several adaptive local searches to perform exploitation. First, to make PSO suitable for solving PFSSP, a ranked-order value rule based on random key representation is presented to convert the continuous position values of particles to job permutations. Second, to generate an initial swarm with certain quality and diversity, the famous Nawaz-Enscore-Ham (NEH) heuristic is incorporated into the initialization of population. Third, to balance the exploration and exploitation abilities, after the standard PSO-based searching operation, a new local search technique named NEH_1 insertion is probabilistically applied to some good particles selected by using a roulette wheel mechanism with a specified probability. Fourth, to enrich the searching behaviors and to avoid premature convergence, a simulated annealing (SA)-based local search with multiple different neighborhoods is designed and incorporated into the PSOMA. Meanwhile, an effective adaptive meta-Lamarckian learning strategy is employed to decide which neighborhood to be used in SA-based local search. Finally, to further enhance the exploitation ability, a pairwise-based local search is applied after the SA-based search. Simulation results based on benchmarks demonstrate the effectiveness of the PSOMA. Additionally, the effects of some parameters on optimization performances are also discussed.     

Metaheuristic methods in hybrid flow shop scheduling problem

Memetic algorithms are hybrid evolutionary algorithms that combine global and local search by using an evolutionary algorithm to perform exploration while the local search method performs exploitation. This paper presents two hybrid heuristic algorithms that combine particle swarm optimization (PSO) with simulated annealing (SA) and tabu search (TS), respectively. The hybrid algorithms were applied on the hybrid flow shop scheduling problem. Experimental results reveal that these memetic techniques can effectively produce improved solutions over conventional methods with faster convergence.     

A hybrid evolutionary multiobjective optimization strategy for the dynamic power supply problem in magnesia grain manufacturing

The supply trajectory of electric power for submerged arc magnesia furnace determines the yields and grade of magnesia grain during the manufacture process. As the two production targets (i.e., the yields and the grade of magnesia grain) are conflicting and the process is subject to changing conditions, the supply of electric power needs to be dynamically optimized to track the moving Pareto optimal set with time. A hybrid evolutionary multiobjective optimization strategy is proposed to address the dynamic multiobjective optimization problem. The hybrid strategy is based on two techniques. The first one uses case-based reasoning to immediately generate good solutions to adjust the power supply once the environment changes, and then apply a multiobjective evolutionary algorithm to accurately solve the problem. The second one is to learn the case solutions to guide and promote the search of the evolutionary algorithm, and the best solutions found by the evolutionary algorithm can be used to update the case library to improve the accuracy of case-based reasoning in the following process. Due to the effectiveness of mutual promotion, the hybrid strategy can continuously adapt and search in dynamic environments. Two prominent multiobjective evolutionary algorithms are integrated into the hybrid strategy to solve the dynamic multiobjective power supply optimization problem. The results from a series of experiments show that the proposed hybrid algorithms perform better than their component multiobjective evolutionary algorithms for the tested problems.     

一种用于多目标优化的混合粒子群优化算法

将粒子群算法与局部优化方法相结合,提出了一种混合粒子群多目标优化算法（HMOPSO）。该算法针对粒子群局部优化性能较差的缺点,引入多目标线搜索与粒子群算法相结合的策略,以增强粒子群算法的局部搜索能力。HMOPSO首先运行PSO算法,得到近似的Pareto最优解;然后启动多目标线搜索,发挥传统数值优化算法的优势,对其进行进一步的优化。数值实验表明,HMOPSO具有良好的全局优化性能和较强的局部搜索能力,同时HMOPSO所得的非劣解集在分散性、错误率和逼近程度等量化指标上优于MOPSO。     

基数约束投资组合问题的一种混合元启发式算法求解

针对资产数目和投资资金比例受约束的投资组合选择这一NP难问题,基于混沌搜索、粒子群优化和引力搜索算法提出了一种新的混合元启发式搜索算法。该算法能很好地平衡开发能力和勘探能力,有效抑制了算法早熟收敛现象。标准测试函数的测试结果表明混合算法与标准的粒子群优化和引力搜索算法相比具有更好的寻优效率;实证分析进一步对混合算法与遗传算法及粒子群优化算法在求解这类投资组合选择问题的性能进行了比较。数值结果表明,混合算法在搜索具有高预期回报的非支配投资组合方面表现更好,取得了更为满意的结果。     

求解区间数分布式流水线调度的混合离散果蝇优化算法

分布式调度是制造系统领域的前沿研究,而不确定调度问题的研究更具现实意义.针对不确定分布式置换流水线调度问题,采用区间数表示工序加工时间,以最小化区间最大完工时间为目标,利用问题特性在果蝇优化框架内提出一种混合离散果蝇优化算法.首先,通过改进启发式方法和随机方法混合初始化种群;然后,基于概率协同多搜索操作执行嗅觉搜索.为了平衡算法的全局探索与局部开发能力,设计基于学习机制的双种群协同搜索环节.为了进一步提升种群性能,针对优良解设计基于切换机制的双模式局部搜索.基于大量算例的仿真结果与统计对比,表明所提出算法能更有效求解区间数分布式流水线调度问题.     

一种自适应混合粒子群优化算法及其应用*

为提高粒子群算法的寻优精度,提出一种将单纯形法(SM)和粒子群(PSO)算法相结合的自适应混合粒子群优化(AHPSO)算法,该算法根据进化需要动态调整粒子的惯性权重,并在进化停滞时使用SM优化。通过仿真实验证明了AHPSO的寻优性能优于SPSO和SMPSO。将AHPSO用于某航空发动机的PID参数优化,其整定性能优于现有的工业方法和其他PSO算法。     

A hybrid particle swarm optimization for a university course scheduling problem with flexible preferences

The timetabling problem at universities is an NP-hard problem concerned with instructor assignments and class scheduling under multiple constraints and limited resources. A novel meta-heuristic algorithm that is based on the principles of particle swarm optimization (PSO) is proposed for course scheduling problem. The algorithm includes some features: designing an ‘absolute position value’ representation for the particle; allowing instructors that they are willing to lecture based on flexible preferences, such as their preferred days and time periods, the maximum number of teaching-free time periods and the lecturing format (consecutive time periods or separated into different time periods); and employing a repair process for all infeasible timetables. Furthermore, in the original PSO algorithm, particles search solutions in a continuous solution space. Since the solution space of the course scheduling problem is discrete, a local search mechanism is incorporated into the proposed PSO in order to explore a better solution improvement. The algorithms were tested using the timetabling data from a typical university in Taiwan. The experimental results demonstrate that the proposed hybrid algorithm yields an efficient solution with an optimal satisfaction of course scheduling for instructors and class scheduling arrangements. This hybrid algorithm also outperforms the genetic algorithm proposed in the literature.     

PSO-Based Multiobjective Optimization With Dynamic Population Size and Adaptive Local Archives

Recently, various multiobjective particle swarm optimization (MOPSO) algorithms have been developed to efficiently and effectively solve multiobjective optimization problems. However, the existing MOPSO designs generally adopt a notion to “estimate” a fixed population size sufficiently to explore the search space without incurring excessive computational complexity. To address the issue, this paper proposes the integration of a dynamic population strategy within the multiple-swarm MOPSO. The proposed algorithm is named dynamic population multiple-swarm MOPSO. An additional feature, adaptive local archives, is designed to improve the diversity within each swarm. Performance metrics and benchmark test functions are used to examine the performance of the proposed algorithm compared with that of five selected MOPSOs and two selected multiobjective evolutionary algorithms. In addition, the computational cost of the proposed algorithm is quantified and compared with that of the selected MOPSOs. The proposed algorithm shows competitive results with improved diversity and convergence and demands less computational cost.      

An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers

In this paper, an effective hybrid algorithm based on particle swarm optimization (HPSO) is proposed for permutation flow shop scheduling problem (PFSSP) with the limited buffers between consecutive machines to minimize the maximum completion time (i.e., makespan). First, a novel encoding scheme based on random key representation is developed, which converts the continuous position values of particles in PSO to job permutations. Second, an efficient population initialization based on the famous Nawaz–Enscore–Ham (NEH) heuristic is proposed to generate an initial population with certain quality and diversity. Third, a local search strategy based on the generalization of the block elimination properties, named block-based local search, is probabilistically applied to some good particles. Moreover, simulated annealing (SA) with multi-neighborhood guided by an adaptive meta-Lamarckian learning strategy is designed to prevent the premature convergence and concentrate computing effort on promising solutions. Simulation results and comparisons demonstrate the effectiveness of the proposed HPSO. Furthermore, the effects of some parameters are discussed.     

批量无等待调度问题的微粒群蛙跳混合优化算法*

将离散微粒群与蛙跳算法相结合解决以最大完工时间为指标的批量无等待流水线调度问题.结合微粒群算法较强的全局收敛能力和蛙跳算法较强的深度搜索能力,设计了三种混合算法,平衡了算法的全局开发能力和局部探索能力.对随机生成不同规模的实例进行了广泛的实验,仿真实验结果的比较表明了所得混合算法的有效性和高效性.     

基于多目标粒子群算法的混合流水车间调度方法研究

混合流水车间调度问题HFSP是一种具有很强应用背景的生产调度问题。本文给出了一种HFSP多目标调度模型,提出了一种针对该类问题的多目标粒子群算法。该算法采用基于Pareto支配关系的极值更新策略;采取对自适应惯性权重递减和对种群变异的方法以保持种群多样性;设置Pareto解池保存计算中出现的Pareto最优解,并提出了一种基于适应度拥挤度的聚类算法优化解的分布特性。实验结果表明,本文算法是求解HFSP问题的一种有效方法。     

求解混合流水车间调度问题的改进型PSO算法

针对粒子群优化算法易陷入局部最优以及求解生产调度问题时容易重复搜索的情况,结合混合车间调度问题的优化模型,提出一种改进的粒子群优化算法。在算法设计中,引入基于位置相似度的禁忌策略,避免对刚刚搜索过的区域重复搜索和过早陷入局部最优;同时采用线性微分递减方式更新惯性权重,既保证了算法前期有较高的全局搜索能力,又能保证后期有较高的开发能力。最后通过仿真实验,验证算法的有效性。     

自适应混合粒子群算法求解置换流水车间调度问题

为更有效地解决以最大完工时间最小化为目标的置换流水车间调度问题,提出了一种自适应混合粒子群算法（SHPSO）。该算法结合Q学习设计了参数自适应更新策略,以平衡算法的探索和开发;同时引入粒子停滞判断方法,使用平局决胜机制和Taillard加速算法改进基于迭代贪婪的局部搜索策略,对全局极值进行局部搜索,帮助粒子跳出局部最优。实验结果表明,SHPSO算法取得的平均相对百分偏差（RPDavg）对比其他四种改进PSO算法至少下降了83.2%,在求解质量上具有明显优势。     

A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling.

This paper proposes a hybrid quantum-inspired genetic algorithm (HQGA) for the multiobjective flow shop scheduling problem (FSSP), which is a typical NP-hard combinatorial optimization problem with strong engineering backgrounds. On the one hand, a quantum-inspired GA (QGA) based on Q-bit representation is applied for exploration in the discrete 0-1 hyperspace by using the updating operator of quantum gate and genetic operators of Q-bit. Moreover, random-key representation is used to convert the Q-bit representation to job permutation for evaluating the objective values of the schedule solution. On the other hand, permutation-based GA (PGA) is applied for both performing exploration in permutation-based scheduling space and stressing exploitation for good schedule solutions. To evaluate solutions in multiobjective sense, a randomly weighted linear-sum function is used in QGA, and a nondominated sorting technique including classification of Pareto fronts and fitness assignment is applied in PGA with regard to both proximity and diversity of solutions. To maintain the diversity of the population, two trimming techniques for population are proposed. The proposed HQGA is tested based on some multiobjective FSSPs. Simulation results and comparisons based on several performance metrics demonstrate the effectiveness of the proposed HQGA.     

An improved PSO algorithm with genetic and neighborhood-based diversity operators for the job shop scheduling problem

The job shop scheduling problem (JSSP) is an important NP-hard practical scheduling problem that has various applications in the fields of optimization and production engineering. In this paper an effective scheduling method based on particle swarm optimization (PSO) for the minimum makespan problem of the JSSP is proposed. New variants of the standard PSO operators are introduced to adapt the velocity and position update rules to the discrete solution space of the JSSP. The proposed algorithm is improved by incorporating two neighborhood-based operators to improve population diversity and to avoid early convergence to local optima. First, the diversity enhancement operator tends to improve the population diversity by relocating neighboring particles to avoid premature clustering and to achieve broader exploration of the solution space. This is achieved by enforcing a circular neighboring area around each particle if the population diversity falls beneath the adaptable diversity threshold. The adaptive threshold is utilized to regulate the population diversity throughout the different stages of the search process. Second, the local search operator based on critical path analysis is used to perform local exploitation in the neighboring area of the best particles. Variants of the genetic well-known operators “selection” and “crossover” are incorporated to evolve stagnated particles in the swarm. The proposed method is evaluated using a collection of 123 well-studied benchmarks. Experimental results validate the effectiveness of the proposed method in producing excellent solutions that are robust and competitive to recent state-of-the-art heuristic-based algorithms reported in literature for nearly all of the tested instances.     

Cost optimized Hybrid Genetic-Gravitational Search Algorithm for load scheduling in Cloud Computing

In cloud computing, cost optimization is a prime concern for load scheduling. The swarm based meta-heuristics are prominently used for load scheduling in distributed computing environment. The conventional load scheduling approaches require a lot of resources and strategies which are non-adaptive and static in the computation, thereby increasing the response time, waiting time and the total cost of computation. The swarm intelligence-based load scheduling is adaptive, intelligent, collective, random, decentralized, self-collective, stochastic and is based on biologically inspired mechanisms than the other conventional mechanisms. The genetic algorithm schedules the particles based on mutation and crossover techniques. The force and acceleration acting on the particle helps in the finding the velocity and position of the next particle. The best position of the particles is assigned to cloudlets to be executed on the virtual machines in the cloud. The paper proposes a new load scheduling technique, Hybrid Genetic-Gravitational Search Algorithm (HG-GSA) for reducing the total cost of computation. The total computational cost includes cost of execution and transfer. It works on hybrid crossover technique based gravitational search algorithm for searching the best position of the particle in the search space. The best position of the particle is used calculating the force. The HG-GSA is compared to the existing approaches in the CloudSim simulator. By the convergence and statistical analysis of the results, the proposed HG-GSA approach reduces the total cost of computation considerably as compared to existing PSO, Cloudy-GSA and LIGSA-C approaches.     

Binary optimization using hybrid particle swarm optimization and gravitational search algorithm

The PSOGSA is a novel hybrid optimization algorithm, combining strengths of both particle swarm optimization (PSO) and gravitational search algorithm (GSA). It has been proven that this algorithm outperforms both PSO and GSA in terms of improved exploration and exploitation. The original version of this algorithm is well suited for problems with continuous search space. Some problems, however, have binary parameters. This paper proposes a binary version of hybrid PSOGSA called BPSOGSA to solve these kinds of optimization problems. The paper also considers integration of adaptive values to further balance exploration and exploitation of BPSOGSA. In order to evaluate the efficiencies of the proposed binary algorithm, 22 benchmark functions are employed and divided into three groups: unimodal, multimodal, and composite. The experimental results confirm better performance of BPSOGSA compared with binary gravitational search algorithm (BGSA), binary particle swarm optimization (BPSO), and genetic algorithm in terms of avoiding local minima and convergence rate.     

A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems

This paper presents a novel discrete differential evolution (DDE) algorithm for solving the no-wait flow shop scheduling problems with makespan and maximum tardiness criteria. First, the individuals in the DDE algorithm are represented as discrete job permutations, and new mutation and crossover operators are developed based on this representation. Second, an elaborate one-to-one selection operator is designed by taking into account the domination status of a trial individual with its counterpart target individual as well as an archive set of the non-dominated solutions found so far. Third, a simple but effective local search algorithm is developed to incorporate into the DDE algorithm to stress the balance between global exploration and local exploitation. In addition, to improve the efficiency of the scheduling algorithm, several speed-up methods are devised to evaluate a job permutation and its whole insert neighborhood as well as to decide the domination status of a solution with the archive set. Computational simulation results based on the well-known benchmarks and statistical performance comparisons are provided. It is shown that the proposed DDE algorithm is superior to a recently published hybrid differential evolution (HDE) algorithm [Qian B, Wang L, Huang DX, Wang WL, Wang X. An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers. Computers & Operations Research 2009;36(1):209–33] and the well-known multi-objective genetic local search algorithm (IMMOGLS2) [Ishibuchi H, Yoshida I, Murata T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation 2003;7(2):204–23] in terms of searching quality, diversity level, robustness and efficiency. Moreover, the effectiveness of incorporating the local search into the DDE algorithm is also investigated.     

An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers

This paper proposes an effective hybrid algorithm based on differential evolution (DE), namely HDE, to solve multi-objective permutation flow shop scheduling problem (MPFSSP) with limited buffers between consecutive machines, which is a typical NP-hard combinatorial optimization problem with strong engineering background. Firstly, to make DE suitable for solving scheduling problems, a largest-order-value (LOV) rule is presented to convert the continuous values of individuals in DE to job permutations. Secondly, after the DE-based exploration, an efficient local search, which is designed based on the landscape of MPFSSP with limited buffers, is applied to emphasize exploitation. Thus, not only does the HDE apply the parallel evolution mechanism of DE to perform effective exploration (global search) in the whole solution space, but it also adopts problem-dependent local search to perform thorough exploitation (local search) in the promising sub-regions. In addition, the concept of Pareto dominance is used to handle the updating of solutions in sense of multi-objective optimization. Moreover, the convergence property of HDE is analyzed by using the theory of finite Markov chain. Finally, simulations and comparisons based on benchmarks demonstrate the effectiveness and efficiency of the proposed HDE.