Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem

Flexible job-shop problem has been widely addressed in literature. Due to its complexity, it is still under consideration for research. This paper addresses flexible job-shop scheduling problem (FJSP) with three objectives to be minimized simultaneously: makespan, maximal machine workload, and total workload. Due to the discrete nature of the FJSP problem, conventional particle swarm optimization (PSO) fails to address this problem and therefore, a variant of PSO for discrete problems is presented. A hybrid discrete particle swarm optimization (DPSO) and simulated annealing (SA) algorithm is proposed to identify an approximation of the Pareto front for FJSP. In the proposed hybrid algorithm, DPSO is significant for global search and SA is used for local search. Furthermore, Pareto ranking and crowding distance method are incorporated to identify the fitness of particles in the proposed algorithm. The displacement of particles is redefined and a new strategy is presented to retain all non-dominated solutions during iterations. In the presented algorithm, pbest of particles are used to store the fixed number of non-dominated solutions instead of using an external archive. Experiments are performed to identify the performance of the proposed algorithm compared to some famous algorithms in literature. Two benchmark sets are presented to study the efficiency of the proposed algorithm. Computational results indicate that the proposed algorithm is significant in terms of the number and quality of non-dominated solutions compared to other algorithms in the literature.     

可重构装配线多目标优化调度研究

针对可重构装配线调度存在的问题,综合考虑影响可重构装配线调度的三个主要因素,即最小化空闲和未完工作业量、均衡零部件的使用速率、最小化装配线重构成本,建立了可重构装配线多目标优化调度的数学模型。提出了一种基于Pareto多目标遗传算法的可重构装配线优化调度方法,该算法综合运用了群体排序技术、小生境技术、Pareto解集过滤及精英保留策略,并采用了交叉概率和变异概率的自适应重构策略。实例仿真表明该算法具有比其他遗传算法更高的求解质量。

     

基于混合离散蝙蝠算法的跨工序协同调度问题

针对跨工序的生产与配送协同调度问题,构建了前工序单机批加工、后工序多产线逐订单加工,且工序之间采用自动引导车循环配送的协同调度模型。以最小化最大完工时间和后工序前的在制品等待时间为调度目标,设计了融合模拟退火算法与解串算法的混合离散蝙蝠算法,与改进的离散粒子群算法和Ullrich遗传算法相比,该算法能很好地减少后工序产线前的队列等待时间,缩短产品的生产周期。     

解决U形装配线平衡调度问题的免疫协同进化算法

研究了混流U形装配线平衡与调度的多目标集成优化问题,提出了一种基于Pareto最优的多目标克隆免疫协同进化算法。该算法以两个单克隆抗体群对应平衡与调度两个子问题,分别编码并协同进化,以一个多克隆抗体群保存最优完整解并采取精英策略,使得子种群间既存在协作也存在竞争。提出从抗体的基因型和表现型同时评价抗体亲和度,并改进了共生伙伴选择机制以提高算法的收敛性能。仿真实例证明算法有着更快的收敛速度且比单种群进化算法更适于U形装配线平衡调度问题的求解。     

基于粒子群优化和模拟退火的混合调度算法

提出了一种离散粒子群调度算法，采用基于工序的编码方式及相应的位置和速度更新方法，使具有连续本质的粒子群算法直接适用于调度问题。针对粒子群算法容易陷入局部最优的缺陷，将其与模拟退火算法结合，得到了粒子群-模拟退火算法、改进的粒子群算法、粒子群-模拟退火交替算法以及粒子群-模拟退火协同算法等4种混合调度算法。仿真结果表明，混合算法均具有较高的求解质量。     

结合混合进化算法和知识的多目标车间调度

提出了一种结合混合进化算法和知识的新型多目标车间调度方法,在有限的时间或迭代次数下可以得到更好的非支配Pareto解以服务于生产调度。由优化目标和属性归纳演绎法确定了知识挖掘的工件属性,通过优先级权重得到了规则初始种群。所提出的增减排序方法通过重新局部排序初始种群中工序的位置来克服优先级下工序不足或过饱和的问题。最后由一标准案例和非支配排序遗传算法-Ⅱ(NSGA-Ⅱ)混合模拟退火算法对所提调度方法进行了验证,得到的结果无论是优化目标值还是解集的分布在不同迭代次数和初始种群尺寸下都要优于传统随机进化方法。     

A hybrid two-phase encoding particle swarm optimization for total weighted completion time minimization in proportionate flexible flow shop scheduling

A proportionate flow shop (PFS) is a special case of the m machine flow shop problem. In a PFS, a fixed sequence of machines is arranged in s stages (s?>?1) with only a single machine at each stage, and the processing time for each job is the same on all machines. Notably, PFS problems have garnered considerable attention recently. A proportionate flexible flow shop (PFFS) scheduling problem combines the properties of PFS problems and parallel-identical-machine scheduling problems. However, few studies have investigated the PFFS problem. This study presents a hybrid two-phase encoding particle swarm optimization (TPEPSO) algorithm to the PFFS problem with a total weighted completion time objective. In the first phase, a sequence position value representation is designed based on the smallest position value rule to convert continuous position values into job sequences in the discrete PFFS problem. During the second phase, an absolute position value representation combined with a tabu search (TS) is applied starting from the current position of particles that can markedly improve swarm diversity and avoid premature convergence. The hybrid TPEPSO algorithm combines the cooperative and competitive characteristics of TPEPSO and TS. Furthermore, a candidate list strategy is designed for the TS to examine the neighborhood and concentrate on promising moves during each iteration. Experimental results demonstrate the robustness of the proposed hybrid TPEPSO algorithm in terms of solution quality. Moreover, the proposed hybrid TPEPSO algorithm is considerably faster than existing approaches for the same benchmark problems in literature.     

Pareto archived simulated annealing for job shop scheduling with multiple objectives

In this paper, the job shop scheduling problem is studied with the objectives of minimizing the makespan and the mean flow time of jobs. The simultaneous consideration of these objectives is the multi-objective optimization problem under study. A metaheuristic procedure based on the simulated annealing algorithm called Pareto archived simulated annealing (PASA) is proposed to discover non-dominated solution sets for the job shop scheduling problems. The seed solution is generated randomly. A new perturbation mechanism called segment-random insertion (SRI) scheme is used to generate a set of neighbourhood solutions to the current solution. The PASA searches for the non-dominated set of solutions based on the Pareto dominance or through the implementation of a simple probability function. The performance of the proposed algorithm is evaluated by solving benchmark job shop scheduling problem instances provided by the OR-library. The results obtained are evaluated in terms of the number of non-dominated schedules generated by the algorithm and the proximity of the obtained non-dominated front to the Pareto front.     

面向大规模定制的装配线优化调度研究

针对大规模定制生产模式下汽车装配线调度存在的问题,提出一种多目标优化调度的方法,设计了相应的目标函数。提出一种多目标遗传算法,设计了相应的编码、选择和交换方案,在算法实现中对精英策略和选择机制进行了改进。仿真实验说明该算法可行有效,优于VEGA、PGA和NPGA等其他遗传算法。     

基于粒子群优化和变邻域搜索的混合调度算法

提出了用于解决作业车间调度问题的离散版粒子群算法.该算法采用基于工序的编码和新的位置更新策略,使具有连续本质的粒子群算法直接适用于调度问题.同时,针对粒子群算法容易陷入局部最优的缺陷,利用粒子群算法和变邻域搜索算法的互补性能,设计了粒子群-变邻域搜索算法、改进的粒子群算法、粒子群-变邻域搜索交替算法和粒子群-变邻域搜索协同算法4种混合调度算法.仿真结果表明,混合算法能够有效地、高质量地解决作业车间调度问题.     

多目标混合流水车间作业调度的演化算法

针对多目标条件下混合流水车间作业调度的优化问题,提出了一种在优化进程中能够动态调整适应度分配的演化算法。该算法采用矩阵编码描述多阶段并行机调度方案,结合问题的优化模型,对每一代Pareto解在各目标方向上的改善程度进行度量,进而通过多目标的选择性权重系数计算种群个体的适应度,以获得在改善指示方向上的选择压力。通过BENCHMARK问题测试和实际算例分析,表明新算法的性能优于现有的求解算法,特别是对于高维多目标优化问题,能够获得较高的演化收敛速度。     

混合离散蝙蝠算法求解多目标柔性作业车间调度

针对以最大完工时间、生产成本和生产质量为目标的柔性作业车间调度问题,在研究和分析蝙蝠算法的基础上,提出一种混合离散蝙蝠算法。为了提高求解多目标柔性作业车间调度问题的混合离散蝙蝠算法的初始种群质量,在通过分析初始选择的机器与每道工序调度完工时间两者关系的基础上,提出一种优先指派规则策略产生初始种群,提高了算法的全局搜索能力。同时采用位置变异策略来使得算法在较短的时间内尽可能多地搜索到最优位置,有效地避免了算法早熟收敛。在计算问题的目标值上面,首次提出时钟算法。针对具体实例进行测试,试验数据表明,该算法在求解柔性作业车间调度问题上有很好的性能,是一种有效的调度算法,从而为解决这类问题提供了新的途径和方法。     

基于模糊偏好的多目标粒子群算法的应用研究

研究了基于模糊偏好的多目标粒子群算法,算法将种群的最优解集进行Pareto排序,并动态更新Pareto解集,使其更快速的靠近Pareto前沿,对非劣解进行模糊评价,根据目标偏好的模糊信息,来确定折衷解的满意解。经典算例验证,该算法在计算时间及非劣解质量上,要优于多目标遗传算法。     

基于DNA遗传算法求解机床加工调度问题

研究了机床加工的多目标调度问题,提出一种基于DNA计算的混合遗传算法,结合Pareto非支配排序法来求解。为保证最优解集的多样性,采用四进制编码方式,将DNA序列分成中性和有害两部分,交叉操作只在中性部分进行;由动态变化的变异概率决定是否执行变异操作,并比较设计的算法与常规遗传算法获得的结果。试验结果表明,可以有效地解决机床加工中的多目标调度问题。     

A hybrid discrete firefly algorithm for multi-objective flexible job shop scheduling problem with limited resource constraints

In this paper, a hybrid discrete firefly algorithm is presented to solve the multi-objective flexible job shop scheduling problem with limited resource constraints. The main constraint of this scheduling problem is that each operation of a job must follow a process sequence and each operation must be processed on an assigned machine. These constraints are used to balance between the resource limitation and machine flexibility. Three minimisation objectives—the maximum completion time, the workload of the critical machine and the total workload of all machines—are considered simultaneously. In this study, discrete firefly algorithm is adopted to solve the problem, in which the machine assignment and operation sequence are processed by constructing a suitable conversion of the continuous functions as attractiveness, distance and movement, into new discrete functions. Meanwhile, local search method with neighbourhood structures is hybridised to enhance the exploitation capability. Benchmark problems are used to evaluate and study the performance of the proposed algorithm. The computational result shows that the proposed algorithm produced better results than other authors’ algorithms.     

[工艺规划与装配线平衡]两阶段混合算法求解集成工艺规划与调度问题

提出了求解集成式工艺规划与车间调度问题的两阶段混合算法。在工艺规划阶段,使用遗传算法为每个工件生成可选的近优工艺路线集,动态地为车间调度阶段输入已确定的工艺路线;在车间调度阶段,使用蜜蜂交配优化算法快速寻优,设计了蜂王婚飞的流程以保证算法的全局搜索能力,构建了基于不同邻域结构的工蜂培育幼蜂局部搜索策略。使用基准测试集对提出的方法进行验证,并与现有算法进行对比,计算结果证明了提出方法的有效性。     

面向绿色制造模式调度的Petri网模型及优化算法

针对绿色制造模式的作业车间调度中,不但要缩短生产周期和降低生产成本,而且要减少资源消耗和对环境的负面影响这一问题,建立包含加工时间、生产成本、资源消耗和环境影响等信息的Petri网模型。通过为机器分配工序来消解因机器库所共享引起的冲突,得到表示调度方案的标识图。提出生成可行调度标识图的三种方 法,并采用多目标遗传算法和多目标模拟退火算法相结合的混合算法对其优化。仿真结果表明算法的可行性和有效性。     

Product configuration optimization using a multiobjective genetic algorithm

Product configuration is one of the key technologies in the environment of mass customization. Traditional product configuration technology focuses on constraints-based or knowledge-based application, which makes it very difficult to optimize design of product configuration. In this paper, an approach based on multiobjective genetic algorithm is proposed to solve the problem. Firstly, a configuration-oriented product model is discussed. A multiobjective optimization problem of product configuration according to the model is described and its mathematical formulation is designed. Secondly, a multiobjective genetic algorithm is designed for finding near Pareto or Pareto optimal set for the problem. A matrix method used to check constraint is proposed, and the coding and decoding representation of the solution are designed, then a new genetic evaluation and select mechanism is proposed. Finally, performance comparison of the proposed genetic algorithm with three other genetic algorithms is made. The result shows that the proposed genetic algorithm outperforms the other genetic algorithms in this problem.     

多目标柔性作业车间调度决策精选机制研究

针对多目标柔性作业车间调度优化无法找到唯一最优解的问题，提出多目标遗传算法和层次分析法模糊综合评判的分阶段优化策略。提出优化阶段和精选阶段的优化任务，优化阶段选出一组Pareto解集，精选阶段从Pareto解集中选出最优解；在精选阶段运用层次分析法和模糊评判集成的策略精选调度决策。决策算例证明提出的方法是可行的，可很好地帮助决策者选择出一个最满意的解。     

Effective hybrid discrete artificial bee colony algorithms for the total flowtime minimization in the blocking flowshop problem

In this paper, three effective hybrid discrete artificial bee colony (hDABC1, hDABC2, hDABC3) algorithms are presented to solve the blocking flowshop scheduling problem with the objective of minimizing the total flowtime. The three hybrid DABC algorithms utilize discrete job permutations to represent food sources and apply discrete operators to generate new food sources for the employed bees, onlookers, and scouts, respectively. First, two heuristic rules called the MME-A and MME-B (variant of combination of minmax and NEH) are presented to construct an initial population with a certain level of quality and diversity. Second, a self-adaptive strategy is applied to employed bees. Third, the estimation of distribution algorithm implements explicit learning from selected individuals and then generates good solutions for onlooker bees. Last but not least, to improve the algorithms' local exploitation ability, a very efficient local search-based insertion neighborhood is carried out in three stages respectively, that is, hDABC1 algorithm is generated by applying a local search to the solution obtained in the employed bee stage. hDABC2 is designed by carrying out a local search in the onlooker bee stage, and hDABC3 is developed by applying a local search in the scout bee stage. Computational experiments on standard benchmark problems are conducted. The results and comparisons show that the proposed algorithms are very effective and efficient for the blocking flowshop scheduling problems with total flowtime criterion than the other algorithms.