求解零等待流水车间调度问题的改进蝙蝠算法

针对零等待流水车间调度问题特性,设计了一种蝙蝠算法进行求解.算法模拟蝙蝠捕食搜索行为进行寻优,利用基于最小位置值规则的随机键编码方式来表示问题解,采用基于NEH方法的局部搜索策略和随机交换、插入、逆序操作的变邻域搜索策略来提高局部优化性能,进一步根据Metropolis概率准则接受劣解来避免早熟.通过典型算例对所提算法进行仿真测试并与粒子群算法和RAJ启发式算法进行对比,结果表明所设计算法求解零等待流水车间调度问题的有效性和优越性,是求解流水车间生产调度问题的一种有效工具.     

具有学习效应的置换流水车间调度问题布谷鸟搜索算法求解

对于以最小化最大完工时间为目标的置换流水车间调度问题,现有研究较少考虑学习效应对生产调度的影响,构建了具有学习效应的PFSP问题数学模型.采用ROV的编码方式,应用布谷鸟搜索算法进行离散优化问题求解.通过对Car类问题的大量仿真测试,表明了布谷鸟搜索算法求解该类问题的可行性和有效性.同时,证明了学习效应能够降低最大完工时间,从而提高生产效率.     

置换流水车间调度问题的中心引力优化算法求解

目前求解置换流水车间调度问题的智能优化算法都是随机型优化方法,存在的一个问题是解的稳定性较差。针对该问题,本文给出一种确定型智能优化算法——中心引力优化算法的求解方法。为处理基本中心引力优化算法对初始解选择要求高的问题,利用低偏差序列生成初始解,提高初始解质量;利用加速度和位置迭代方程更新解的状态;利用两位置交换排序法进行局部搜索,提高算法的优化性能。采用置换流水车间调度问题标准测试算例进行数值实验,并和基本中心引力优化算法、NEH启发式算法、微粒群优化算法和萤火虫算法进行比较。结果表明该算法不仅具有更好的解的稳定性,而且具有更高的计算精度,为置换流水车间调度问题的求解提供了一种可行有效的方法。     

改进的布谷鸟算法求解考虑运输时间的分布式柔性流水车间调度问题

针对分布式制造环境下多车间调度问题特点,结合企业实际生产情况,考虑相邻工序间的运输时间,建立以最小化最大完工时间为优化目标的分布式柔性流水车间调度模型,提出一种改进布谷鸟算法用于求解该模型。算法改进包括设计了一种基于工序、车间和机器的三层编码方案;根据问题特点设计了混合种群初始化策略以提高种群质量;改进了布谷鸟搜索操作使其适用于求解该模型;设计了一种种群进化策略以提高算法收敛速度及解的质量。最后通过仿真实验,与多种算法对比,验证所提算法的有效性和优越性。     

考虑机器能耗的绿色作业车间调度问题

针对传统作业车间调度,在保证交货期的前提下,以机器能耗最小为目标研究带有关机/重启策略的绿色车间调度问题。首先建立数学规划模型,然后在遗传算法的框架下,根据问题特点提出了一种局部调整的解码方式,在排产时进行工序的移动并确定其开始加工时刻。最后进行小规模算例运算,验证数学规划模型的有效性,再利用算例对基于局部调整解码和顺序解码的遗传算法进行对比测试,结果表明提出的局部调整解码可以在降低机器能耗的同时提高求解效率。     

无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案

本文考虑n个工件的无限批量机器调度问题．一台机器可以同时加工B≥n个工件．每个工件具有一个正权因子、一个释放时间和一个加工时间．一个批次的加工时间是该批次所包含所有工件的加工时间的最大者．在同一批次中加工的工件有相同的完工时间，即它们的共同开始时间加上该批次的加工时间．对于最小化加权完工时间和问题，本文给出了第一个多项式时间近似方案(PTAS)．对任意给定精度，该算法的运行时间为线性的．     

混沌神经网络优化算法用于求解无等待流水调度问题的最小最大完工时间

利用李小平等提出的相邻工件加工结束时间差矩阵,将求解无等待流水调度问题的最小最大完工时间(Makespan)问题映射为TSP问题,构造对应的能量函数,进而得到随机混沌神经网络(SCSA)算法.实验结果证明该混沌神经网络优化算法优于RAJ算法和GANRAJ算法.     

DBR理论求解柔性作业车间调度问题

针对柔性作业车间调度完工时间最小问题,提出一种结合DBR(鼓-缓冲器-绳子)理论和改进遗传算法的方法。在问题初始化时,建立瓶颈机器识别机制改善初始化方法,提高初始解的质量;在运算过程中依据关键路径建立瓶颈机器的识别机制和调度策略。为了更好保留每代中的优良解,采用外部精英库对优良解进行解保留。运用提出的算法求解基准测试问题,实验结果验证了算法的可行性和有效性。     

考虑模糊交货期的柔性作业车间动态调度研究

针对柔性作业车间调度在机器故障扰动情况下的动态性,采用基于事件与周期混合驱动的滚动窗口再调度策略进行动态调度.对于工件交货期模糊的情况采用梯形交货期窗口表示,并运用字典序多目标规划的方法,以平均流经时间最小、能耗最小、客户满意度最大为目标,建立多目标柔性作业车间动态调度模型,并设计了改进的自适应免疫遗传算法,在对种群进行初始化时,将初始化机器、初始化工序及随机初始化结合在一起,并对模型进行求解.将算例仿真结果与遗传算法所得的结果进行对比,验证算法的有效性.     

含不相关机的动态可重入柔性流水车间问题的混合DABC-GA算法

为了改善生产线的物流平衡和加强阶段间的时间衔接,扩展一般可重入柔性流水车间调度理论,以最小化总加权完工时间为目标,研究了每阶段含不相关并行机的动态可重入柔性流水车间问题,工件在各阶段的加工时间取决于加工它的机器。鉴于所研究问题为NP-hard问题,首先,建立整数规划模型;其次,设计元胞矩阵编码方案,提出融合离散人工蜂群算法和遗传算法的一种混合算法以获得问题的近优解;最后,为了评估混合算法的性能,将所提出算法和一些元启发式算法进行了不同规模问题的对比测试,实验结果说明了所提算法的有效性。     

柔性Flow shop最小和调度问题的启发式研究

本文研究有n个作业须在s个处理机中心进行加工，处理机中心i由l1个同速机组成的非抢占式柔性nowshop加权完成时间调度问题。每个作业有同样的加工路径通过每个处理机中心，但只需在处理机中心的任一台机器上加工处理，作业到达时间相同。目的是确定一个作业在每个处理机中心机器上的可行调度序列，使所有作业在最后处理机中心的加权完成时间总和最小化。在作业处理时间和权重有界、每个作业的工序处理时间为同分布的随机变量、不同作业的处理时间相互独立时，通过分组这种机器环境，我们证明该问题在作业数趋于无究时，一个基于加权最短处理时间的启发式算法是渐近最优的。     

An Enhanced TSP-Based Heuristic for Makespan Minimization in a Flow Shop with Setup Times

This paper presents an enhanced heuristic for minimizing the makespan of the flow shop scheduling problem with sequence-dependent setup times. The procedure transforms an instance of the problem into an instance of the traveling salesman problem by introducing a cost function that penalizes for both large setup times and bad fitness of schedule. This hybrid cost function is an improvement over earlier approaches that penalized for setup times only, ignoring the flow shop aspect of the problem. To establish good parameter values, each component of the heuristic was evaluated computationally over a wide range of problem instances. In the testing stage, an experimental comparison with a greedy randomized adaptive search procedure revealed the conditions and data attributes where the proposed procedure works best.     

工件带到达时间的两阶段柔性流水作业的近似算法

研究了工件带到时间的两阶段柔性流水作业的排序问题,基于求解流水作业和平行机问题的算法思想,提出两个相应的近似算法H(R)和H(MR(?)),证明了这两个算法的最坏情况性能比分别为3-1/m和2/5-1/m,讨论了界的紧性,并利用数值模拟以分析算法与最优值的近似性能比.     

加权完工时间和的调整时间可分离Flow shop排序问题

讨论了2台机器调整时间可分离的FlowShop排序问题,目标函数为极小化加权完工时间和.给出了对于一种特殊情况,问题存在多项式最优算法的充分条件.接着又给出了求解该问题的一个分枝定界法.     

预制构件流水车间订单接受与调度的集成优化

针对预制构件生产管理过程中订单工期紧和生产能力不足的问题,在充分考虑中断和不可中断工序,串行和并行工序等复杂工况特点的基础上,以最大化净利润为目标,建立了一种订单接受与调度集成优化模型。鉴于问题的NP难性和模型的高度非线性,通过集成问题性质、构造启发式、邻域搜索和破坏-构造机制,提出了一种混合加速迭代贪婪搜索框架。其中,在调度构造阶段,为提高算法求解质量和搜索效率,设计了两种融合订单插入操作性质的加速构造策略。计算结果显示,与混合遗传禁忌搜索算法,遗传算法以及禁忌搜索算法相比,本文所提算法具有更好的求解质量和搜索效率。同时验证了所提出的加速构造策略能够有效减少算法运行时间。该研究有望显著提高预制生产企业净利润和客户满意度。     

流水车间作业排序问题蚁群算法研究

本文运用蚁群算法研究辨台处理机、目标函数为时间表长最小的同顺序排列流水车间作业排序问题，设计出解决该问题的算法步骤与流程。最后，通过仿真比较该算法与解决该问题的其它启发式算法性能，计算效果比较满意。     

An Algorithm for the Job Shop Scheduling Problem based on Global Equilibrium Search Techniques

The job shop scheduling problem is considered, and an algorithm based on the global equilibrium search method is proposed for its solution. Computational experiments using well-known benchmark problems are presented. Several new upper bounds for these problems are obtained.Research partially supported by NSF and AirForce grants.     

Heuristic Approaches for a Scheduling Problem in the Plastic Molding Department of an Audio Company

A production scheduling problem for making plastic molds of hi-fi models is considered. The objective is to minimize the total machine makespan in the presence of due dates, variable lot size, multiple machine types, sequence dependent, machine dependent setup times, and inventory limits. Goal programming and load balancing are applied to select the set of machine types and assign mold types to machines, resulting in a set of single-machine scheduling problems. A mixed-integer program (MIP) is formulated for the general problem but could solve only small instances. A single-machine scheduling heuristic is designed to adopt a production sequence from a travelling salesman solution. The start time of every cycle is determined by a simplified MIP. Production cycles are defined to equalize the stockout times of mold types. A post-processing step reduces the number of setups in the last cycle. Results using real-life data are promising. Characteristics giving rise to high machine utilization are discussed.