无缓存流水线生产系统中AGV调度问题的研究

针对无缓存流水线生产系统中的AGV(automated guided vehicle)调度问题提出了复合评分的启发式调度算法,降低了系统中AGV执行任务的间隔等候时间.首先,通过建立数学模型,对目前主流的AGV规模估计方法做出了改进.其次,提出了一种新的基于复合评分禁忌搜索的AGV前瞻调度算法.不同于目前主流的以空驶距离为优化目标的调度算法,该算法能够以最小化工件延误时间、最小化AGV空驶距离等多目标来统筹调度AGV.最后,为验证所提算法的有效性,从多个角度与已有算法进行了实验对比.仿真实验结果表明,相较于其他算法,提出的前瞻调度算法能够更有效地解决无缓存流水线生产系统这一新场景的AGV调度问题.实车实验也证明了该算法在实际生产中的有效性.     

单线列车运行调整目标体系与算法模型的研究

为了解决列车运行调整优化过程中调整目标存在目标单一、适应性不强、不能满足实际运行情况等问题,在对各种常用的性能指标进行综合分析的基础上,并结合现场调查与调度经验,利用满意优化理论,分析了晚点列车的等级、晚点时间、晚点列车数量等不同性能指标对调整目标满意度的影响.提出了基于满意优化理论的列车运行调整目标体系模型,并将该模型与传统的列车运行调整目标体系在同样的实例环境下进行了仿真.仿真结果表明,与传统的列车运行调整目标体系相比,该模型在实际运行过程中具有更好的优化性和有效性.     

考虑能耗和准时的混合流水线多目标调度

针对加工时间和交货期模糊的混合流水线,考虑阶段内并行机互不相关、换模时间与工件加工次序相关等约束,面向降低生产能源消耗和保证准时交货的双目标调度问题,提出一种改进型差分进化算法.首先,以最小化系统能耗和准时交货惩罚为优化目标建立双目标优化数学模型;在此基础上,使用NEH(Nawaz, Enscore, Ham)方法获得优质初始解,并利用优质解挑战机制进行有效的邻域挖掘;同时,引入混沌搜索策略以保证算法的全局搜索能力;最后,将数值实验与有代表性的算法的计算结果进行对比,以验证所提算法的可行性与有效性.     

基于无监督学习的实时公交动态调度的研究

针对广州智能公交调度的优化问题,提出一种基于无监督学习的实时公交动态调度算法,结合乘客利益和公交公司利益总体最优为目标,通过无监督学习方法学习到公交客流出行特征表达的提取,利用吸引子传播(affinity propagation,AP)聚类算法的优化数据集与支持向量机(support vector machine,SVM)的训练样本集相结合建立预测模型训练,运用公交线网发车间隔和加权系数的目标函数优化调度数学模型,将多源信息融合及多策略的实时公交动态调度算法引入到求解模型中,利用深度学习的异常突发事件分类检测方法实现调度优化模型的实时调整。实验结果表明,AP聚类算法程序运行耗时16 s、高峰发车间隔5 min,比遗传算法运行效率更高、时间间隔更精确,实例证明模型和算法具有实用性和可靠性。     

基于分解多目标进化算法的光刻区调度方法

针对晶圆制造系统光刻区调度问题,考虑设备专用性约束、掩膜版数量约束及设备加工能力约束,以最小化总完工时间和光刻成本、最大化晶圆准时交付率和设备利用率为目标,提出了基于分解多目标进化算法的光刻区调度方法．针对非支配前沿点分布不均的问题,设计了基于聚类分析的参考点生成方法;综合考虑非支配解的分布均匀性、收敛性及计算资源的合理分配,改进了惩罚边界交叉聚合函数;设计了外部档案变邻域搜索方法,提高算法的求解质量和收敛速度．24组基准算例和晶圆制造仿真系统连续12个月的测试结果表明：提出的分解多目标进化算法相对于多种多目标进化算法,能够取得更好的收敛性和解的多样性．     

新工件到达锁定初始调度的单机重调度问题

研究了新工件到达锁定初始调度的单机重调度问题.即有一组带有不同释放时间的初始工件已经按照最小化完成时间和的优化目标调度完毕,形成初始调度且已锁定,此时有一组释放时间为零的新工件到达,且需要插入初始调度进行加工,其优化目标为最小化新工件的完工时间和.文中研究了新工件的加工过程可中断和新工件的加工过程不可中断,共2类新工件到达锁定初始调度的单机重调度问题.分析了重调度问题的复杂性,针对第一类重调度问题提出了多项式算法并证明了其最优性.证明了第二类重调度问题为NP完全问题,提出了一个多项式算法,并证明了该算法的有效性和最优解的特征,解决了企业实际问题并进一步丰富了重调度理论.     

面向分段涂装作业的混合流水车间调度

基于船舶分段涂装作业,提炼出具有重入和等待时间约束的两阶段混合流水车间调度问题.其中第一阶段含多台批处理机,第二阶段含多台离散机且存在一次重入过程,两阶段间有等待时间约束.以最小化最大完工时间为优化目标建立数学模型,提出一种结合Metropolis抽样准则和变邻域搜索的混合量子粒子群优化算法,并利用多种启发式规则进行解码.实例验证和数值分析表明,所提算法是解决分段涂装调度问题的一种有效方法.     

钢坯热轧加热炉区生产调度模型与算法

钢坯热轧加热炉区生产调度属于组合优化中的NP-complete问题.本文根据加热炉区生产特点建立了分别以生产能耗最小化和加热质量最优化为主次目标的钢坯加热炉区调度数学模型,将其归结为布尔可满足性问题,构造了采用二进制编码方式的遗传禁忌搜索算法进行求解.基于实际生产数据的模拟优化结果表明,该模型和求解方法充分满足了现场加热炉区生产调度的需求,在满足生产工艺约束的前提下,缩短了生产时间,提高了钢坯入炉温度和加热质量,与传统人工调度方法的结果相比具有更好的节能、高产效果.     

基于改进型多目标粒子群算法的晶圆制造系统瓶颈工作站调度

为了尽可能提高瓶颈工作站利用率,在获得较高系统产能的同时得到一个合理的制造周期,构建了以最小化瓶颈工作站的平均加权提前/拖期时间和最小化瓶颈工作站流程时间为优化目标的改进型多目标粒子群算法,并对瓶颈工作站进行了性能分析.将准时交货和快速生产要求分别映射为瓶颈工作站平均加权提前/拖期时间和流程时间,并构建了多目标优化模型.通过改进速度和位置的更新机制,对陷入局部最优的粒子进行交叉操作,设计了用于瓶颈工作站调度的改进型多目标粒子群算法.在不同作业规模下从算法的稳定性、Pareto前沿质量、收敛速度及运行时间出发,进行了调度仿真试验.结果表明该算法对提高瓶颈工作站的调度性能是有效的、可行的.     

基于禁忌搜索的柔性作业车间分批调度

针对柔性作业车间的分批调度问题,提出了一种基于禁忌搜索算法的柔性分批调度算法.首先进行批次初始划分;然后利用禁忌搜索算法优化批次加工路线和子批加工顺序;最后在零件子批数不变的前提下,利用批量变化局部搜索进行批量分割的优化,实现了最小化完工时间和机床负荷的调度目标.实例分析结果证明了柔性分批调度算法的可行性、高效性和适用性.
     

工件带准备时间的平行机调度问题的一个近似算法

提出了一个启发式算法,在该算法中,工件中断的次数至多为2N次,计算的复杂度为O(Nnlogn),并以一个实例加以说明.证明了对某些特殊的实例,该算法能够得到最优调度.指出了对于一般情况该算法的最坏情况误差界为(2(n-1))/n.     

基于缓冲区的同型机物资调度优化

现代物流运输车辆调度方法复杂多变。将缓冲区引入物流调度中,解决物资冗余的问题;分析了带缓冲区的两台同型机半在线调度优化问题,目标为最大化最小机器加工时间,给出了一个竞争比至少为2/3的半在线算法。     

并行流程式生产线调度问题的概率分析求解算法

并行生产线调度问题兼有并行机器和流程车间调度问题的特点 ,是一类新型的调度问题·针对工件在各工序具有任意加工时间的一般并行生产线调度问题 ,构造了整数规划模型 ,设计了基于概率分析的求解算法·对随机生成的测试问题进行求解的实验结果表明了算法的有效性     

基于规则与生物免疫机理的多目标作业调度方法应用研究

敏捷制造单元是一个涉及多目标、多约束和多扰动的复杂系统，它的最优作业调度求解有很大难度。这里分析了敏捷制造环境的作业调度规律及其特点，建立了用于调度启发式规则集合，构造了基于生物免疫机理的作业调度算法，并对生物智能算法涉及的相关参数进行了分析与优化。并且以调度案例库中的部分案例为对象，给出了基于规则和生物智能计算调度方法的优化结果，及其与其他调度方法的对比分析。     

两个代理的单机排序问题的多项式时间算法

考虑两个代理的单机排序问题,有两个代理A和B,分别具有各自的工件集JA和JB,并且代理A中所有工件的加工时间都相等.第一个代理A以加权完工时间和为目标函数,第二个代理B以最大加权完工时间为目标函数.问题的目标是寻找一种排序,使得第二个代理B的目标函数不超过给定上界Q(Q>0)的情况下,第一个代理A的目标函数达到最小.文章证明该问题可以在O(nlogn)内求解.     

钢铁企业生产与运输费用协调调度问题

针对钢铁企业生产前存在不可忽略运输的实际,研究了生产与生产前运输费用协调调度问题.由于钢铁企业被调度的工件体积较大及加工前不能等待太长的时间,因此运输车辆的容量及工件在机器前的缓冲等待时间有限制.考虑的机器环境为单机环境,单机前有无限的缓冲空间,运输车辆数目无限,调度的目标函数为传统的调度函数加上运输费用.对于不同的目标函数,证明了工件在单机加工前缓冲等待时间有限制的调度问题是强NP难的,对于运输车辆有容量限制问题的可解情况给出了多项式时间算法.     

基于萤火虫算法的学习遗忘效应BFSP问题研究

对于以最小化最大完工时间为目标的阻塞流水车间调度问题(BFSP),现有研究较少同时考虑学习效应及遗忘效应对生产调度的影响,为此构建了BFSP问题的学习遗忘调度模型,结合基于Pairwise的局部搜索策略,应用萤火虫算法对小批量生产时的学习遗忘效应BFSP问题进行求解.对Car类问题及其学习遗忘调度模型的大量仿真测试,表明了改进萤火虫算法求解该类问题的可行性和有效性.同时,证明了学习效应能够降低最大完工时间,从而提高生产效率;而遗忘效应会使得学习效果减弱,从而导致最大完工时间的增加,学习效应和遗忘效应在生产调度中的影响是客观存在且不可忽略的.     

调整时间可分离的无等待FlowShop调度问题

研究了3台机器调整时间可分离的无等待FlowShop调度问题,目标函数为极小化加权完工时间和·基于对问题的分析,给出了目标函数的一般表示·对某些特殊情况,给出了问题存在多项式最优算法的充分条件·在此条件下,将单机调度问题的WSPT规则应用到无等待FlowShop调度问题,得到了求解无等待FlowShop问题最优调度的分派规则·通过反例指出了文献中的某些错误·     

两类极小化最大加权完工时间排序问题研究

研究两个单机排序问题。目标函数均是最大加权完工时间。对于问题I｜｜maxw,c,证明了LW规则序是最优排序,而问题1｜r,｜maxw,cj．用3-划分问题归结。证明是强NP困难的。     

无线mesh骨干网络的路由与调度联合优化算法

在基于TDMA的无线mesh骨干网络中,考虑路由和调度的联合优化问题,最大化系统频谱利用率.综合考虑了节点业务、路径平均容量以及干扰等因素,提出了一种新型路由策略.对于汇聚网关的业务模式,提出了一种基于网关瓶颈极大团相关性的链路调度策略.考虑路由算法和调度算法的联合优化,设计了链路调度模块和路由模块的信息交互策略.仿真结果表明,该联合算法对于各种节点业务分布和各种干扰环境,均可很好地提高系统频谱利用率,在保证一定通信速率的情况下,节省了能量,实现绿色环保通信.