求解拆卸线平衡问题的一种变邻域搜索算法

针对拆卸线平衡问题特点,建立以最小化工作站数、平滑指数、危害指数和需求指数为优化目标的多目标数学模型,进而提出一种改进的变邻域搜索算法求解该问题。所提算法采用了一种启发式方法产生初始解,并构造了3种邻域结构,扩大算法搜索范围。采用初始解集进行局部搜索,搜索过程使用一步改进策略,并引入禁忌表方法,提高算法全局寻优能力。通过对大量不同规模测试问题进行算法实验,并与现有方法对比,结果表明,所提变邻域搜索算法在求解效率与求解质量上具有优越性。     

解决无等待流水线调度问题的变邻域搜索算法

提出了解决无等待流水线调度问题的变邻域搜索调度算法。采用基于自然数编码的工件序列表达问题的解，采用多重Insert移动邻域和多重Swap移动邻域作为变邻域搜索的两种邻域结构。多重移动有利于算法向包含较优解的区域搜索，因而有较高的求解质量和效率。仿真实验证明了变邻域搜索算法的有效性。     

同时配集货定位—路线问题的变邻域分散搜索算法

针对同时配集货的定位—路线问题,建立了三维指数混合整数规划模型,并设计了变邻域分散搜索求解算法,即在基本分散搜索算法的基础上保留参考集更新和组合策略的全局搜索能力。针对组合后的解可能是不可行解的问题,利用插入法将其改进为可行解,再运用变邻域搜索进行局部开发以提高可行解质量。为保证算法的多样性以进一步扩大搜索空间,初始种群采用两阶段混合多随机法构造。通过采用Lingo求解简单算例验证了模型的正确性,采用设计的变邻域分散搜索算法仿真已有算例并与其他算法比较,证明了该算法的有效性。     

一类解决Job Shop问题的禁忌搜索算法

针对Job shop问题，设计了一种改进的禁忌搜索算法（MTS算法）。MTS算法从多个初始解开始，将传统禁忌搜索算法由串行搜索结构变为并行搜索结构；采用互换和交叉两种邻域搜索函数，既有利于新邻域的探索又有利于交换信息；基于目标值的禁忌表保证了群体的多样性。实验表明，MTS算法克服了传统禁忌搜索算法的缺陷，具有较高的求解质量和鲁棒性。     

求解单向环型布局问题的一种禁忌搜索算法

单向环型布局在柔性制造系统中得到广泛应用,在分析该布局特点的基础上,提出了一种改进的禁忌搜索算法来求解该布局优化问题。基于总零件重新载入次数最小的原则,建立数学模型。设计禁忌搜索算法时,采用插入法产生初始解,以两台设备的交换作为禁忌对象构建禁忌表,采用2-opt方式产生邻域结构,在此基础上编写相关程序实现模型计算。通过对算例和实际问题进行求解验证,说明了该算法的有效性。     

求解作业车间调度的变邻域细菌觅食优化算法

针对最小化最大完工时间的作业车间调度问题,提出一种基于变邻域趋化操作的细菌觅食优化算法。邻域搜索是一类改进型局部搜索算法,在每一步迭代过程中通过搜索当前解的邻域得到一个改进的解,利用邻域搜索可大大提高局部最优解的精确度。本算法采用基于操作的编码,使得细菌觅食优化算法适用于作业车间调度求解;将3种不同的邻域结构引入趋化操作中,以便扩大可行解的搜索空间,细菌个体按照自适应学习策略根据邻域的各自贡献率选择搜索方式,减少陷入局部极小的机会;同时使用自适应步长更新各邻域内趋化操作的位置,根据适应度值动态调整搜索精度,避免早熟收敛。典型算例试验表明,该算法具有一定的鲁棒性,并有效地提高了搜索精度和收敛性。     

基于遗传变邻域混合算法的带交货期的单机车间逆调度方法

针对带交货期的单机逆调度问题,建立以最小化系统调整为目标函数的单机逆调度数学优化模型;利用互补性能,采用串行、并行和嵌入等结构,将遗传算法与变邻域搜索算法相结合,设计出遗传-变邻域搜索算法、遗传-变邻域搜索交替算法和遗传-变邻域搜索协同算法3种混合算法。为产生逆调度激发机制,采用非最优调度法,将随机初始化与局部初始化进行结合,创造逆调度环境;此外,为提高算法的局部搜索能力,基于交叉变异操作等思想来构建四种搜索邻域,通过邻域结构的切换,加强局部搜索能力;最后,将提出的混合算法用于求解不同规模的问题实例,与其他算法的求解结果进行比较,证明提出的混合算法是可行的和有效的。     

基于改进禁忌搜索的多目标自动化仓库调度

针对产品质量和路径的多目标自动化立体仓库调度优化问题,为平衡解的收敛性和多样性,提出一种改进的多目标禁忌搜索算法.该算法的改进在于,一方面为Pareto解空间构造可行的初始解,改造了禁忌搜索的邻域结构;另一方面采用惩罚策略,使搜索能够跳出局部最优.面向出入自动化立体仓库的产品在时间上有特定要求的工业生产过程,建立了兼顾质量和路径的多目标优化模型,并运用改进的多目标禁忌搜索算法对其实现了调度优化求解.实例仿真表明,所提算法对仓库调度优化问题在解的质量及求解效率上都取得了较好的效果.     

应用混合蚁群算法求解模糊作业车间调度问题

为解决蚁群算法求解时间过长和易陷入局部最优的问题,提出了一种求解模糊作业车间调度问题的混合算法,该算法将蚁群算法用于全局搜索.为了提高搜索效率,根据作业车间调度问题解的特征,提出一种基于关键工序的邻域搜索方法,并使用此邻域搜索方法的禁忌搜索算法嵌入蚁群算法.利用禁忌搜索算法较强的局部搜索能力,提高了蚁群算法的优化能力,改善了作业车间调度问题解的质量.实验结果验证了该混合搜索算法的有效性,其优化效果优于并行遗传算法和禁忌搜索算法.     

改进遗传变邻域算法求解飞机装配线调度问题

针对飞机装配调度过程中受到空间限制的问题,建立了以最小化装配作业总工期为目标并考虑空间约束的飞机装配线分部段作业调度数学模型,提出了一种求解此模型的改进遗传变邻域算法。该算法采用优先级规则进行种群初始化以缩减解空间,并设计了一种结合接受阈值的变邻域局部搜索方式,采用考虑紧前紧后关系三种邻域结构来确保搜索过程中产生合法解,以提高搜索能力,避免传统遗传算法陷入局部最优,最后通过标准算例库PSPLIB中的算例验证了算法的有效性和优越性。     

柔性车间的多工艺路线与布局联合优化

为解决柔性车间布局过程中常忽略工艺与布局相互影响的问题,并提高柔性车间布局的鲁棒性,提出多工艺路线和车间布局联合优化模型.该模型以总体物流成本最低为优化目标,同时考虑车间布局与多工艺路线规划以提高整体的优化效果,其中根据产量决定各产品加工工序序列在总体规划中的影响程度,并将出入库物流与换模物流纳入总体物流成本中,以进一...     

Scheduling jobs under constant period-by-period resource availability to maximize project profit at a due date

In this paper, we propose a lump-sum payment model for the resource-constrained project scheduling problem, which is a generalization of the job shop scheduling problem. The model assumes that the contractor will receive the profit of each job at a predetermined project due date, while taking into account the time value of money. The contractor will then schedule the jobs with the objective of maximizing his total future net profit value at the due date. This proposed problem is nondeterministic polynomial-time (NP)-hard and mathematically formulated in this paper. Several variable neighborhood search (VNS) algorithms are developed by using insertion move and two-swap to generate various neighborhood structures, and making use of the well-known backward–forward scheduling, a proposed future profit priority rule, or a short-term VNS as the local refinement scheme (D-VNS). Forty-eight 20-job instances were generated using ProGen and optimally solved with ILOG CPLEX. The performances of these algorithms are evaluated based on the optimal schedules of the 48 test instances. Our experimental results indicate that the proposed VNS algorithms frequently obtain optimal solutions in a short computational time. For larger size problems, our experimental results also indicate that the D-VNS with forward direction movement outperforms the other VNS algorithms, as well as a genetic algorithm and a tabu search algorithm.     

基于群智能算法的设备布局离散优化研究

针对单向环形设备布局设计问题,建立了新的数学模型.利用多维实数编码及映射方法,将连续粒子群优化算法应用于求解设备单向环形布局问题,提供了求解离散优化问题的新思路.利用遗传算法中的杂交策略扩展了粒子群优化算法,提高了粒子群优化算法性能.建立了问题的图结构描述,以引入蚁群系统算法搜索优化解.给出了两种方法的求解步骤.通过实例计算和结果比较,说明该算法能有效地解决此类离散优化问题,降低成本,提高效率,所得解质量较高,有很好的实用价值.     

一种鱼骨仓储布局下的拣选路径优化方法

根据一种非传统鱼骨(fishbone)布局的特点，基于仓储运作约束条件建立了拣选路径优化模型，构造了非传统货位距离矩阵；在标准遗传算法基础上，通过进化逆转算子克服标准遗传算法存在早熟收敛和局部搜索能力较差等问题，给出了一种多种群遗传算法；为验证算法的有效性，在不同订单规模下，将多种群遗传算法与标准遗传算法和S-Shape算法进行比较，应用MATLAB软件仿真分析，一系列实验结果表明多种群遗传算法计算结果最优，并且寻优速度更快于标准遗传算法，能够很好地解决鱼骨仓储布局下的拣选路径优化问题，提高仓储智能化水平。     

A clustering-based modified variable neighborhood search algorithm for a dynamic job shop scheduling problem

The dynamic job shop scheduling (DJSS) problem occurs when some real-time events are taken into account in the ordinary job shop scheduling problem. Most researches about the DJSS problem have focused on methods in which the problem’s input data structure and their probable relationship are not considered in the optimization process while some useful information can be extracted from such data. In this paper, the variable neighborhood search (VNS) combined with the k-means algorithm as a modified VNS (MVNS) algorithm is proposed to address the DJSS problem. The k-means algorithm as a cluster analysis algorithm is used to place similar jobs according to their processing time into the same clusters. Jobs from different clusters are considered to have greater probability to be selected when an adjacent for a solution is made in an optimization process using the MVNS algorithm. To deal with the dynamic nature of the problem, an event-driven policy is also selected. Computational results obtained using the proposed method in comparison with VNS and other common algorithms illustrate better performance in a variety of shop floor conditions.     

基于随机秘钥蝙蝠算法的多行设施布局设计

针对行内纵向通道数量和位置具有不确定性的多行设施布局问题,建立了以最小化物流强度、最小化搬运设备空载运行强度及最大化相互关系为设计目标的布局优化模型,并针对所建立的模型提出了一种基于映射规则的随机秘钥蝙蝠算法。在蝙蝠算法中引入随机秘钥编码思想,定义了基于随机秘钥编码的蝙蝠位置向多行设施布局组合解的映射规则与映射步骤,使算法在不进行离散化处理的前提下,可以在连续空间上执行,并在组合空间上映射出码长不同的布局方案。最后,以一个多行设施布局问题为实例,采用所提出的随机秘钥蝙蝠算法进行求解,证明了算法的优越性。     

Hybrid algorithms for the uncapacitated continuous location-allocation problem

In this paper, hybrid algorithms are developed for the multisource location-allocation problem in continuous space. Three hybrid algorithms are proposed to solve this problem that combine elements of several traditional metaheuristics (genetic algorithm and variable neighborhood search) and local searches to find near-optimal solutions. Many problems from the literature have been solved with these algorithms and the obtained results confirm the robustness of the proposed hybrid algorithms. Moreover, the results show that in comparison to the best methods in literature (GA and VNS), these algorithms provide some better solutions.     

INTEGRATED LAYOUT DESIGN OF CELLS AND FLOW PATHS

The integrated layout problem in manufacturing systems is investigated. An integrated model for concurrent layout design of cells and flow paths is formulated. A hybrid approach combined an enhanced branch-and-bound algorithm with a simulated annealing scheme is proposed to solve this problem. The integrated layout method is applied to re-layout the gear pump shop of a medium-size manufacturer of hydraulic pieces. Results show that the proposed layout method can concurrently provide good solutions of the cell layouts and the flow path layouts.     

适应性禁忌搜索算法求解带回程的时变速度车辆路径问题

为求解带回程的时变速度车辆路径问题，建立了问题的数学模型并提出适应性禁忌搜索算法求解。适应性禁忌搜索算法为两阶段的启发式方法，改进固定速度下的启发式方法用于生成时变速度下的初始解，然后运用适应性禁忌搜索算法进一步优化，包括邻域生成规则定义，采用Hash表存储搜索过程中的解，检测解的重复状态，定义逃离局部搜索区域规则。对改进的标准问题进行测试，同时与最近邻域搜索算法的结果作比较，结果表明算法是有效的。与固定速度情形相比较，时变速度模型得到的调度方案更加合理。     

用差异进化和变邻域搜索解决无等待流水线调度问题

提出了解决无等待流水线调度问题的离散差异进化(DDE)算法和变邻域搜索(VNS)算法。与标准差异进化(DE)算法不同,DDE算法采用了基于工序的编码和新的个体生成方法,因而能直接用于求解生产调度这类复杂问题;VNS算法采用多重移动邻域以提高性能。为了进一步提高求解质量,将DDE和VNS结合,得到三种混合算法:DDE—VNS、DDE_(VNS)和DDE&VNS。仿真试验表明:上述算法都是有效的,混合算法优于单一算法,VNS、DDE—VNS、DDE_(VNS)和DDE&VNS等4种算法优于国际上同类研究的最新成果。