双层束搜索算法优化机器人制造单元调度问题

针对混流生产阻塞机器人制造单元调度问题，给出了可行机器人运动插入法，构建可行解。依据可行机器人运动插入法，提出双层过滤变宽度束搜索算法进行求解。搜索过程利用局部评价函数和全局评价函数对节点进行两次择优选取。通过计算随机生成算例，仿真结果表明，相对于以分支定界算法产生的可行解进行变邻域搜索、分支定界算法、局部评价函数束搜索算法、全局评价函数束搜索算法和双层过滤定宽度束搜索算法，双层过滤变宽度束搜索算法不但能显著提高搜索效率，而且解的平均改进度分别为3.07%、6.07%、7.79%、12.62%、14.47%。     

差分进化算法求解带批处理机的机器人制造单元调度问题

机器人制造单元是智能制造系统的主要载体,研究机器人制造单元的生产调度问题对于提高智能制造系统的生产效率有着重要作用.对此,研究带批处理机的混合流水线机器人制造单元调度问题.首先,针对机器人制造单元与批处理机的生产特性,建立数学优化模型;其次,设计差分进化算法对其进行求解,提出染色体组编码的概念,求解该问题的染色体组由两个染色体构成,第1条染色体确定工件在每个工序选择的机器,第2条染色体确定加工顺序以及机器人的搬运顺序;然后,设计差分变异、交叉以及选择操作;最后,进行数值实验,结果证明,针对带批处理机的机器人制造单元调度问题,差分进化算法能缩短完工时间,得到更好的解.     

求解混流装配线调度问题的蚁群算法

以最小化总的传送中断时间为目标函数的混流装配线调度问题是丰田生产方式中自动化概念的一个重要问题,而新颖的蚁群算法具有通用性、鲁棒性、并行搜索以及易于与其他启发式算法结合的优点,可以解决多种组合优化问题,对其进行了改进,以便更适于求解混流装配线的调度问题。实验表明：改进的蚁群算法解决了混流装配线的调度问题,得到了优于分支定界法、模拟退火法和遗传算法的可行解。     

多工件类型的无等待机器人制造单元调度研究

首先将加工多工件类型的无等待机器人制造单元调度问题分解为两个相互联系的子问题：（1）多类型工件进入系统的排序问题;（2）机器人搬运作业的排序问题。从解决工件使用工作站和机器人可能发生的冲突入手,以工件进入系统的时间为决策变量,利用禁止区间法建立了问题的数学模型,并开发了一基于图论的动态分枝定界最优算法。最后,通过一自动化印刷电路板（PCB）生产线和随机算例验证了算法的有效性。     

最小费用充电站选址问题的分支定界算法

电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-hard问题。基于最小开设费用对充电站选址问题进行研究,首先对该问题进行了数学建模,进而研究了该问题的数学性质并给予相应的证明,利用这些性质减小问题的规模,从而降低问题的求解难度;然后设计了上下界子算法以及降阶子算法,基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的分支定界算法,降低了时间复杂度,同时可以对解空间进行大量剪枝加快求解速度;最后通过分析和求解一个示例来进一步阐述所提算法的原理和执行过程。     

变邻域搜索算法求解机器人制造单元调度问题——排序依赖转换时间

针对排序依赖转换时间的两机器机器人制造单元调度问题的NP难特性,设计了变邻域搜索算法求解。为了加快算法收敛速度,设计了工件阻塞时间最小化生成初始解;为了搜索到更好解,分析了算法的参数取值。通过随机产生算例测试,提出算法优于模拟退火算法,证实了提出算法的有效性。     

整数线性规划的改进分支定界算法

分支定界(B&B)算法是求解整数线性规划(ILP)问题的一种最常用的方法,如何划分问题(分支)和按何种策略选择子问题进行扩展是影响算法效率的两个重要因素.提出了一种改进的分支定界算法,采用伪费用分支策略划分问题,采用深度优先搜索(DFS)策略选择子问题进行扩展,并在Matlab中编程实现.数值实验表明,改进的算法能够有效提高求解效率,当问题规模较大时,改进效果尤其明显.     

自动化制造单元调度算法综述*

作为未来先进制造系统的重要发展方向,自动化制造单元（robotic cells）在半导体和印刷电路板制造、化学电镀、钢铁冶炼和机械制造等行业获得了日趋广泛的应用。为全面总结自动化制造单元调度算法的研究现状,对自动化制造单元进行分类,在此基础上综述了国内外自动化制造单元调度方法取得的进展及存在的问题,并指明了其进一步的研究方向。     

基于分支定界和神经网络的实时调度策略

为解决一些对精度和实时性要求较高的调度问题,设计一个基于分枝定界算法和人工神经网络的实时调度算法.策略先使朋分枝定界算法来找到m个作业的最佳排序.在生成足够多的排序以后,将排序作为训练样本来训练一个m维人工神经网络,从而得到一个m维的人工种经网络主矩阵.在实际的乍产环境中,先对实际到达的n(n>m)个作业进行分组,再利用离线生成的人工神经网络主矩阵对每个分组进行初始排序.最后将每个分组看作一个整体,根据Palmer算法得到n个作业的最终排序.仿真表明该策略具有较好的实时性,同时也能达到较高的精确性.     

基于分支定界和神经网络的实时调度策略

本文提出一种基于分枝定界算法和人工神经网络的实时调度算法来解决双环厂磨削车间的调度问题。该策略先使用分枝定界算法来找到m个作业的最佳排序。在生成足够多的排序以后,将这些排序作为训练样本来训练一个m维人工神经网络,从而得到一个m维的人工神经网络主矩阵。在实际的生产环境中,先对实际到达的n（n〉m）个作业进行分组,再利用离线生成的人工神经网络主矩阵对每个分组进行初始排序。最后将每个分组看作一个整体,根据Palmer算法得到n个作业的最终排序。     

混合流水车间插单重调度的超启发式遗传算法

针对带有紧急订单的混合流水车间插单重调度问题,提出了一种双层编码的超启发式遗传算法。针对混合流水车间具有的订单排序和机器选择的双决策特征,在算法低层设计双层编码方案,在个体中表示订单排序和机器选择两类信息,对应一个唯一调度解,进而提出了12种排序和选择启发式对个体进行迭代优化;在算法高层采用自适应遗传算法,用来确定订单排序启发式和机器选择启发式的操作组合以及各组合执行的次序,并设计了自适应变异算子来优化算法的有效性。大规模数据实验的结果表明,所提算法具有很好的求解质量和求解效率。     

A scheduling problem in blocking hybrid flow shop robotic cells with multiple robots

This paper addresses the robotic scheduling problem in blocking hybrid flow shop cells that consider multiple part types, unrelated parallel machines, multiple robots and machine eligibility constraints. Initially, a mixed integer linear programming (MILP) model is proposed to minimize the makespan for this problem. Due to the complexity of the model, a simulated annealing (SA) based solution approach is developed for its solution. To increase the efficiency of the SA algorithm, a new neighborhood structure based on block properties is applied. The performance of the proposed SA is assessed over a set of randomly generated instances. The computational results demonstrate that the SA algorithm is effective with the employed neighborhood structure. Additionally, this study shows that the appropriate number of robots depends on the sequence of processing operations to be performed at each stage.     

改进果蝇算法求解混合流水车间调度问题

针对混合流水车间调度问题(HFSP),本文提出了一种新的基于果蝇算法和变邻域搜索的混合优化方法.首先,将关键块内的工序与同阶段其他机器上的工序进行交换,提出了一种基于关键路径的HFSP新邻域结构.其次,针对HFSP的阶段式解码特性,提出了一种邻域解的快速评估方法,并验证了快速评估方法的高效性.然后,基于提出的新邻域结构,并将N7和K-insertion邻域结构引入HFSP,设计了基于上述3种邻域结构的变邻域搜索方法,以此为基础提出了一种针对HFSP的混合优化方法.最后,通过对Carlier和Liao等经典测试集进行测试,验证了所提新邻域结构的可行性和有效性,并将该方法与其他文献的方法进行了对比,验证了所提方法的优越性.     

流水车间调度问题的快速多目标混合进化算法

针对最大完工时间最小和总流经时间最小的双目标流水车间调度问题,提出一种快速多目标混合进化算法。算法将矢量评价遗传算法的采样策略与一种新的基于Pareto支配与被支配关系的适应度函数的采样策略进行了融合。新的采样策略弥补了矢量评价遗传算法(VEGA)采样策略的不足。VEGA善于搜索Pareto前沿面的边缘区域,但却忽略了Pareto前沿面的中心区域,而新的采样策略则倾向于Pareto前沿面的中心区域。这两种机制的融合保证了混合算法能够快速平稳地向Pareto前沿区域收敛。此外,由于混合采样策略不需要考虑距离,使得算法效率也得到了很大的提升。在对Taillard基准测试集进行的仿真实验结果显示,相对于非支配排序遗传算法(NSGA-Ⅱ)和强度Pareto进化算法(SPEA2),该快速多目标混合进化算法在收敛性和分布性两方面都有所提高,并且算法的效率也得到了改进。所提出的混合算法能够更好地解决双目标的流水车间调度问题。     

反向人工蜂群算法求解混合流水车间调度问题

针对以最小化最大完工时间为优化目标的混合流水车间调度问题,提出一种融合反向学习策略的反向人工蜂群算法求解该问题。首先,根据混合流水车间调度问题的特点,建立了对应的数学模型和仿真优化模型;其次,在寻优过程中为了避免陷入局部最优,分别在种群初始化、雇佣蜂和观察蜂三个阶段引入了反向学习策略,采用两点间逆序策略和元素交换策略加快寻优速度,并采用精英保优策略保留最优解;最后,选取2个实例和21个不同规模的benchmark算例进行仿真实验,通过与相关算法的实验结果进行对比分析,验证了所提算法能有效求解此类问题。     

An MO‐GVNS algorithm for solving a multiobjective hybrid flow shop scheduling problem

This paper addresses the multiobjective hybrid flow shop (MOHFS) scheduling problem. In the MOHFS problem considered here, we have a set of jobs that must be performed in a set of stages. At each stage, we have a set of unrelated parallel machines. Some jobs may skip stages. The evaluation criteria are the minimizations of makespan, the weighted sum of the tardiness, and the weighted sum of the earliness. For solving it, an algorithm based on the multiobjective general variable neighborhood search (MO‐GVNS) metaheuristic, named adapted MO‐GVNS, is proposed. This work also presents and compares the results obtained by the adapted MO‐GVNS with those of four other algorithms: multiobjective reduced variable neighborhood search, nondominated sorting genetic algorithm II (NSGA‐II), and NSGA‐III, and another MO‐GVNS from the literature. The results were evaluated based on the Hypervolume, Epsilon, and Spacing metrics, and statistically validated by the Levene test and confidence interval charts. The results showed the efficiency of the proposed algorithm for solving the MOHFS problem.     

批量流水线调度问题的混合差分进化算法

针对E/T指标的批量流水线调度问题,提出了差分进化调度算法。该算法采用基于实数的编码方式,利用最优目标个体的扰动产生变异个体,通过变异个体与目标个体的交叉产生试验个体,提高了最优目标个体信息共享,并结合模拟退火算法给出了两种混合求解策略。仿真试验表明了所得算法的可行性和高效性。     

A hybrid variable neighborhood search algorithm for solving the limited-buffer permutation flow shop scheduling problem with the makespan criterion

This paper investigates the limited-buffer permutation flow shop scheduling problem (LBPFSP) with the makespan criterion. A hybrid variable neighborhood search (HVNS) algorithm hybridized with the simulated annealing algorithm is used to solve the problem. A method is also developed to decrease the computational effort needed to implement different types of local search approaches used in the HVNS algorithm. Computational results show the higher efficiency of the HVNS algorithm as compared with the state-of-the-art algorithms. In addition, the HVNS algorithm is competitive with the algorithms proposed in the literature for solving the blocking flow shop scheduling problem (i.e., LBPFSP with zero-capacity buffers), and finds 54 new upper bounds for the Taillard's benchmark instances.     

A neural network model and algorithm for the hybrid flow shop scheduling problem in a dynamic environment

A hybrid flow shop (HFS) is a generalized flow shop with multiple machines in some stages. HFS is fairly common in flexible manufacturing and in process industry. Because manufacturing systems often operate in a stochastic and dynamic environment, dynamic hybrid flow shop scheduling is frequently encountered in practice. This paper proposes a neural network model and algorithm to solve the dynamic hybrid flow shop scheduling problem. In order to obtain training examples for the neural network, we first study, through simulation, the performance of some dispatching rules that have demonstrated effectiveness in the previous related research. The results are then transformed into training examples. The training process is optimized by the delta-bar-delta (DBD) method that can speed up training convergence. The most commonly used dispatching rules are used as benchmarks. Simulation results show that the performance of the neural network approach is much better than that of the traditional dispatching rules.This revised version was published in June 2005 with corrected page numbers.