求解置换流水线调度问题的混合离散果蝇算法

针对置换流水线调度问题,提出了一种新颖的混合离散果蝇算法.算法每一代进化包括4个搜索阶段:嗅觉搜索、视觉搜索、协作进化和退火过程.在嗅觉搜索阶段,采用插入方式生成邻域解;在视觉搜索阶段,选择最优邻域解更新个体;在协作进化阶段,基于果蝇个体间的差分信息产生引导个体;在退火操作阶段,以一定概率接受最优引导个体从而更新种群.同时,通过试验设计方法对算法参数设置进行了分析,并确定了合适的参数组合.最后,通过基于标准测试集的仿真结果和算法比较验证了所提算法的有效性和鲁棒性.     

变邻域保优遗传算法求解柔性车间调度问题

针对单目标柔性作业车间调度问题,以最大完工时间为优化目标,将遗传算法、变邻域搜索算法与精英保护策略相结合,提出一种运算效率和求解性能均较好的混合算法。首先建立数学模型,阐述算法的整体流程。对遗传算子进行改进,并添加改良的保优记忆库对精英个体进行保护。基于关键工序调整,设计了“同机器工序调整”“变机器工序调整”“双工序调整”三种邻域结构,增强了局部搜索能力,并给出一种高效的关键工序寻找法则。通过对基准算例及数值实验的测试,验证了该算法的有效性和可行性。     

求解不相关并行机混合流水线调度问题的人工蜂群算法

针对不相关并行机混合流水线调度问题的特点,设计了一种基于排列的编码和解码方法,提出了一种有效的人工蜂群算法.在引领蜂和跟随蜂搜索阶段采用3种有效的邻域搜索方法,以丰富搜索行为;在侦察蜂搜索阶段通过随机搜索对种群进行更新,以增强种群多样性.同时,通过试验设计方法对算法的参数设置进行了分析,给出指导性参数组合.通过基于典型实例的数值仿真以及与已有代表性算法的比较,验证了所提算法的有效性和鲁棒性.     

不确定工时下多目标柔性作业车间调度问题的进化求解方法

在实际工业生产中,调度环境的复杂性与不确定性使得调度问题求解难度大大提高.针对加工时间不确定的柔性作业车间调度问题,采用不确定参数描述随机工时波动程度和约束条件允许违背程度,构建工时波动服从指数分布的多目标柔性车间调度模型.基于机会约束规划理论,将不确定调度问题转化为加工时间确定的柔性作业车间调度问题,求解得到一定程度上具有鲁棒性能的调度方案.在执行过程中,采用工序移动调整和重调度方法对作业排产方案进行动态调整.基于双链式编码以及贪婪插入法解码规则,提出了基于变邻域搜索的混合NSGA-Ⅱ算法.针对车间调度问题的多约束性和计算复杂度高等特点,设计了基于机器选择的复合启发式规则,包括依据概率的最小累计机器负载和最短工序加工时间规则,以获取更加接近Pareto前沿的均匀分布初始种群.采用改进工序和设备交叉策略以提高算法的全局搜索能力.此外,基于关键工序和机器选择的多种邻域结构,设计了变邻域搜索策略,以进一步提高算法的局部搜索能力.通过Kacem和Brandimarte标准算例的数值仿真以及与多种代表算法的统计比较,验证了所提算法的有效性.本文所提算法为不确定柔性作业车间调度问题提供了更优的调...     

混合离散教与学算法求解复杂并行机调度问题

针对制造行业中广泛存在的一类复杂并行机调度问题, 即带到达时间、多工序、加工约束和序相关设置时间的并行机调度问题(Parallel machine scheduling problem with arrival time, multiple operations, process restraints and sequence-dependent setup times, PMSP_AMPS), 建立问题的排序模型并提出一种混合离散教与学优化算法进行求解, 优化目标为最小化最大完工时间.首先, 根据标准教与学算法(Teaching-learning-based optimization, TLBO)中两阶段个体更新公式的特点, 在保留每一阶段个体更新公式框架不变的前提下, 对公式中具体改变实数个体或向量的每个核心操作均用所设计的排列操作进行替换, 使其可直接在离散问题解空间中执行基于标准教与学算法机理的全局搜索, 从而明显提高了原算法的全局搜索效率.其次, 采用交换操作和插入操作构造了一种简洁有效地变邻域局部搜索, 对全局搜索发现的优质解区域进行细致搜索, 从而进一步增强了算法的性能.通过对不同测试问题的仿真实验和算法比较, 验证了所提算法可有效求解PMSP_AMPS.     

面向柔性作业车间调度问题的改进变邻域搜索算法

针对柔性作业车间调度问题的特点,提出一种求解该问题的改进变邻域搜索算法。结合问题特点设计合理的编码方式,采用遗传算法进行最优解搜索,将搜索的结果作为变邻域搜索算法的初始解,以提高初始解的质量。为提高局部搜索能力,设计3种不同的邻域结构,构建邻域结构集以产生邻域解,保证邻域解的搜索过程中解的可行性以提高求解效率。针对一系列典型的柔性作业车间调度问题的实例,运用所设计的改进变邻域搜索算法进行测试求解,并将计算结果与文献中其他算法的测试结果进行比较,验证了所提出方法求解柔性作业车间调度问题的可行性和有效性。     

求解并行机拖期与能耗成本优化调度的混合教一学算法

针对加工时间可控的并行机调度,提出了一类考虑拖期与能耗成本优化的调度问题。首先对调度问题进行了问题描述,并建立了整数线性规划模型以便于CPLEX求解。为了快速获得问题的满意解,提出了一种混合教-学算法。结合问题的性质,设计了编码与解码方法以克服标准教-学算法无法直接适用于离散问题的缺点。同时,构建了基于变邻域搜索的局部搜索算子以强化混合算法的搜索性能。最后,对加工时间可控的并行机调度问题进行了仿真实验,测试结果验证了本文构建的整数线性规划模型和混合算法的可行性和有效性。     

求解带容量约束车辆路径问题的混合变邻域生物共栖搜索算法

针对带容量约束的车辆路径问题,提出一种混合变邻域生物共栖搜索算法.设计基于客户点优先序列及车辆参考点模拟信息的有序编码,该编码方案使生物共栖搜索算法可以参与CVRP的离散优化;为了提高算法的全局搜索能力,根据有序编码特点构造3种共栖搜索算子,扩大搜索空间;同时,结合变邻域搜索算法设计客户点重置、交换和2-OPT三种局部搜索策略,以提高解方案质量.算例验证分析表明,所提算法能够有效地解决容量约束车辆路径问题,求解质量优于所对比算法,具有可靠的全局稳定性.     

变邻域遗传算法在车间物流调度中的应用

针对含有自动引导小车(Automated Guided Vehicle,AGV)的离散化车间物流调度问题,以最小化物流任务时间惩罚成本和最小化运载小车的总行驶距离为优化目标,构建离散化车间多目标物流调度优化模型,设计一种基于Pareto寻优的多目标混合变邻域搜索遗传算法(VNSGA-II).以遗传算法为基础,通过使用NSGA-II的Pareto分层和拥挤度计算方法评估种群优劣实现多目标优化,为了提高算法的寻优能力,避免算法陷入局部最优,通过添加保优记忆库对精英个体进行保护,并利用变邻域搜索算法在搜索过程中的局部寻优能力,针对本文模型特点,设计6个随机邻域结构,来达到算法求解最优值的目标.并提出了基于关键AGV小车的插入邻域和基于关键物流任务的交换邻域调整策略以进一步降低成本.最后,以某离散车间物流调度为实例,分别使用VNSGA-II、带精英策略的快速非支配排序遗传算法Ⅱ(Nondominated Sorting Genetic AlgorithmⅡ,NSGA-II)和强Pareto进化算法(Strong Pareto Evolutionary Algorithm 2,SPEA2)对问题进行求解,计算结果表明,VNSGA-II能得到更好的Pareto解集,验证了算法的有效性和可行性.     

基于遗传算法的混合流水线车间调度多目标求解*

为了解决传统的多目标优化算法难以很好实现企业的实际决策需要问题,针对混合流水线车间调度（HFSP）的多目标优化调度问题,提出了一种新的多目标遗传算法。根据企业实际需求,采用分模块两层建模的思想,将多目标分为约束性目标和优化性目标。算法根据目标性质的不同分别进行不同的搜索。最后将新算法应用于HFSP多目标优化问题进行实例验证。结果表明,所提出的算法具有很好的可行性,与其他多目标优化方法相比,该算法具有明显的优越性、实用性和可操作性。     

A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem

Job shop scheduling problem (JSP) which is widespread in the real-world production system is one of the most general and important problems in various scheduling problems. Nowadays, the effective method for JSP is a hot topic in research area of manufacturing system. JSP is a typical NP-hard combinatorial optimization problem and has a broad engineering application background. Due to the large and complicated solution space and process constraints, JSP is very difficult to find an optimal solution within a reasonable time even for small instances. In this paper, a hybrid particle swarm optimization algorithm (PSO) based on variable neighborhood search (VNS) has been proposed to solve this problem. In order to overcome the blind selection of neighborhood structures during the hybrid algorithm design, a new neighborhood structure evaluation method based on logistic model has been developed to guide the neighborhood structures selection. This method is utilized to evaluate the performance of different neighborhood structures. Then the neighborhood structures which have good performance are selected as the main neighborhood structures in VNS. Finally, a set of benchmark instances have been conducted to evaluate the performance of proposed hybrid algorithm and the comparisons among some other state-of-art reported algorithms are also presented. The experimental results show that the proposed hybrid algorithm has achieved good improvement on the optimization of JSP, which also verifies the effectiveness and efficiency of the proposed neighborhood structure evaluation method.     

A multi-objective cellular grey wolf optimizer for hybrid flowshop scheduling problem considering noise pollution

The hybrid flowshop scheduling problem (HFSP) has been widely studied in the past decades. The most commonly used criterion is production efficiency. Green criteria, such as energy consumption and carbon emission, have attracted growing attention with the improvement of the environment protection awareness. Limited attention has been paid to noise pollution. However, noise pollution can lead to health and emotion disorder. Thus, this paper studies a multi-objective HFSP considering noise pollution in addition to production efficiency and energy consumption. First, we formulate a new mixed-integer programming model for this multi-objective HFSP. To realize the green scheduling, one energy conservation/noise reduction strategy is embedded into this model. Then, a novel multi-objective cellular grey wolf optimizer (MOCGWO) is proposed to address this problem. The proposed MOCGWO integrates the merits of cellular automata (CA) for diversification and variable neighborhood search (VNS) for intensification, which balances exploration and exploitation. Finally, to validate the efficiency and effectiveness of the proposed MOCGWO, we compare our proposal with other well-known multi-objective evolutionary algorithms by conducting comparison experiments. The experimental results show that the proposed MOCGWO is significantly better than its competitors on this problem.     

Variable neighbourhood decomposition search for 0–1 mixed integer programs

In this paper we propose a new hybrid heuristic for solving 0–1 mixed integer programs based on the principle of variable neighbourhood decomposition search. It combines variable neighbourhood search with a general-purpose CPLEX MIP solver. We perform systematic hard variable fixing (or diving) following the variable neighbourhood search rules. The variables to be fixed are chosen according to their distance from the corresponding linear relaxation solution values. If there is an improvement, variable neighbourhood descent branching is performed as the local search in the whole solution space. Numerical experiments have proven that exploiting boundary effects in this way considerably improves solution quality. With our approach, we have managed to improve the best known published results for 8 out of 29 instances from a well-known class of very difficult MIP problems. Moreover, computational results show that our method outperforms the CPLEX MIP solver, as well as three other recent most successful MIP solution methods.     

Hybrid flow shop scheduling with assembly operations and key objectives: A novel neighborhood search

This paper addresses hybrid flow shop scheduling problem (HFSP) with assembly operations, in which parts of each product are produced in a hybrid flow shop and then assembled at an assembly stage. The goal is to minimize total tardiness, maximum tardiness and makespan simultaneously. Tardiness objectives are regarded as key ones because of their relative importance and this situation is seldom considered. A simple strategy is applied to handle the optimization with key objectives. A novel neighborhood search with global exchange (NSG) is proposed, in which a part-based coding method is adopted and global exchange is cooperated with neighborhood search to produce high quality solution. Extensive experiments are conducted and the results show that the strategy on key objectives is reasonable and effective and NSG is a very competitive method for the considered HFSP.     

基于新型蛙跳算法的低碳混合流水车间调度

针对低碳混合流水车间调度问题(HFSP),提出一种新型蛙跳算法(SFLA)以同时最小化总能耗和总延迟时间.该算法将种群内最差的部分解排斥在模因组之外, 运用模因组构建和模因组搜索新策略产生新解,同时利用搜索过程产生的优化数据替换种群中未进入模因组的差解并更新外部档案以提高求解质量.通过算例验证新型蛙跳算法解决该问题的有效性,实验结果分析表明,新型SFLA对于所研究的低碳HFSP具有较强的搜索能力和优势.     

A hybridisation of adaptive variable neighbourhood search and large neighbourhood search: Application to the vehicle routing problem

In this paper, an adaptive variable neighbourhood search (AVNS) algorithm that incorporates large neighbourhood search (LNS) as a diversification strategy is proposed and applied to the capacitated vehicle routing problem. The AVNS consists of two stages: a learning phase and a multi-level VNS with guided local search. The adaptive aspect is integrated in the local search where a set of highly successful local searches is selected based on the intelligent selection mechanism. In addition, the hybridisation of LNS with the AVNS enables the solution to escape from the local minimum effectively. To make the algorithm more competitive in terms of the computing time, a simple and flexible data structure and a neighbourhood reduction scheme are embedded. Finally, we adapt a new local search move and an effective removal strategy for the LNS. The proposed AVNS was tested on the benchmark data sets from the literature and produced very competitive results.     

Genetic tabu search for the fuzzy flexible job shop problem

This paper tackles the flexible job-shop scheduling problem with uncertain processing times. The uncertainty in processing times is represented by means of fuzzy numbers, hence the name fuzzy flexible job-shop scheduling. We propose an effective genetic algorithm hybridised with tabu search and heuristic seeding to minimise the total time needed to complete all jobs, known as makespan. To build a high-quality and diverse set of initial solutions we introduce a heuristic method which benefits from the flexible nature of the problem. This initial population will be the starting point for the genetic algorithm, which then applies tabu search to every generated chromosome. The tabu search algorithm relies on a neighbourhood structure that is proposed and analysed in this paper; in particular, some interesting properties are proved, such as feasibility and connectivity. Additionally, we incorporate a filtering mechanism to reduce the neighbourhood size and a method that allows to speed-up the evaluation of new chromosomes. To assess the performance of the resulting method and compare it with the state-of-the-art, we present an extensive computational study on a benchmark with 205 instances, considering both deterministic and fuzzy instances to enhance the significance of the study. The results of these experiments clearly show that not only does the hybrid algorithm benefit from the synergy among its components but it is also quite competitive with the state-of-the-art when solving both crisp and fuzzy instances, providing new best-known solutions for a number of these test instances.     

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

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

A large neighbourhood metaheuristic for the risk-constrained cash-in-transit vehicle routing problem

In this paper, we propose a new metaheuristic to solve the Risk constrained Cash-in-Transit Vehicle Routing Problem (Rctvrp). The Rctvrp is a variant of the well-known capacitated vehicle routing problem and models the problem of routing vehicles in the cash-in-transit sector. In the Rctvrp, the risk associated with a robbery represents a critical aspect that is treated as a limiting factor subject to a maximum risk threshold.A new metaheuristic, called aco-lns is developed. It combines the ant colony heuristic for the travelling salesman problem and a variable neighbourhood descent within an large neighbourhood search framework.A new library of Rctvrp instances with known optimal solutions is proposed. The aco-lns is extensively tested on small, medium and large benchmark instances and compared with all existing solution approaches for the Rctvrp.     

基于免疫克隆选择算法的混合流水车间调度问题的研究

本文针对混合流水车间调度问题,以最大流程时间最小为目标函数,建立了混合整数数学规划模型;将具有解决复杂组合优化问题的免疫克隆选择算法（ICA）应用于求解混合流水车间调度问题,详细描述了ICA算法求解HFSP问题的步骤;为了验证算法的有效性,仿真对比了遗传算法和ICA算法的性能,与文献结果比较,结果表明ICA算法求解HFSP问题可行性和有效性。