摘要：针对作业车间调度问题(JSP),在现有邻域结构的基础上进行拓展,提出一种新型邻域结构.通过对现有邻域结构中产生可行邻域解的约束条件进行松弛,能够使得当前解生成更多的可行邻域解.使用禁忌搜索算法将已有的3种常见的邻域结构与该新型邻域结构进行对比,使用TA数据集中的前50个算例进行验证.实验结果表明:设计的新型邻域结构无论在最优值还是平均值,都比其他3种邻域结构具有优势.实验数据表明:新型邻域结构在4种邻域结构中能够搜索的最多可行邻域解.尽管新型邻域结构搜索花费的时间最多,但由于使用了近似评估方法,因此搜索时间在可接受范围内.

摘要：自动导引车(AGV)在生产车间的应用,给车间调度带来许多额外的需要解决的实际问题,如运输任务AGV分配、AGV电量约束、AGV数量约束等,使得其调度问题更加复杂和困难。针对多AGV运输工件的作业车间调度的特点和约束条件,建立了考虑充电约束的多AGV运输工件的作业车间调度模型,通过虚拟设备的方法设计了工件分配和AGV运输任务的两段染色体编码,设计了工件分配和AGV任务分配的集成解码方法,并设计了改进遗传算法进行求解,进一步分析了AGV数量、AGV电量和运输时间等因素对优化目标的影响,最后通过作业车间典型算例仿真验证了模型与算法的有效性。

摘要：针对大规模作业车间调度问题,提出一种基于滚动窗分解的多瓶颈调度算法。该算法基于关键路径法进行多瓶颈机器的识别,沿时域将大规模调度问题分解为多个子问题进行求解。在子问题创建过程中,提出负荷均衡分布的规则,使得各工件在各子问题中的负荷均匀分布,以实现算法求解过程的稳定性;在子问题的求解过程中,遵循约束理论中瓶颈机主导非瓶颈机的原则,采用瓶颈工序最优化调度、非瓶颈工序采用分派规则快速调度的调度策略,提高算法的求解效率;通过相邻子问题间的工序衔接再优化过程,以及全局解评价子问题染色体适应度值策略,有效避免了子问题分解创建和求解过程的局限性,提高了算法的求解质量。仿真结果表明,该算法具有较佳的求解效率和质量。

摘要：针对作业车间准时制生产调度这类典型的非正规性能指标调度问题,采用禁忌搜索和数学规划的混合策略进行求解,即在每一迭代搜索过程中,首先由禁忌搜索得到各机器上的工序加工序列,再调用数学规划方法来优化各工序的开工时间。另外,设计了一种包含交换和插入两种移动操作的邻域构造方法。邻域构造方法通过交换相邻加工工序对来在当前解的邻域内寻优,而将目标工序插入块之间的间隙以解除块对相关工序的束缚,这种邻域结构有助于提高禁忌搜索求解准时制生产调度问题的搜索效率。48个标准算例的仿真结果证明禁忌搜索/数学规划方法在准时制生产调度解的质量方面具有一定优势。

摘要：针对动态多变环境下的作业车间调度问题,在基于周期和事件驱动的滚动窗口再调度策略基础上,采用冻结时段思想,同时又允许再调度在冻结时段内的资源上的闲置时段安排任务,并由此建立了机器存在不可用时段约束的动态调度模型。借鉴量子进化算法中量子旋转门更新量子位的方法,设计了三段式交叉操作,并在算法框架中嵌入了局部搜索操作,提出了混合差分进化算法作为再调度的优化方法。通过算法性能与作业车间动态调度实验,验证了所提动态调度方法的有效性。

摘要：在考虑用户互为竞争对手、不愿共享其目标的情况下,用户与车间共同组成调度决策群体,形成代理目标为私有信息的多代理作业车间调度问题。以最大化群体社会福利为优化目标,构建了多代理作业车间调度问题的数学模型。设计了遗传进化-评分决策两阶段协商调度机制,并提出了相应的两阶段协商调度算法。在不披露代理目标的前提下,遗传进化阶段采用帕累托优化排序算法,生成非支配调度方案集;评分决策阶段采用基于效用的线性转换评分算法,实现从非支配方案集中选出社会福利较优的调度方案。大量仿真研究表明,所提遗传进化-评分决策两阶段协商调度算法,其整体性能优于现有协商调度算法,能够产生社会福利更高的调度方案。

摘要：针对作业车间准时制调度这类复杂的非正规性能指标调度问题,基于机器加工序列和工序开工时间的两阶段优化策略,提出一种结合变邻域搜索和数学规划的混合调度算法。在变领域搜索的每次迭代过程中,通过在Swap和Insertion两类邻域结构内跳转搜索获得较优的机器加工序列,由此松弛了调度模型中最难满足的机器析取约束;然后调用数学规划方法对当前机器加工序列上的各工序开工时间进行优化计算。以引导工序向各自交货期靠拢为邻域设计原则,提出以紧邻工序对为移动对象的Swap和Insertion邻域结构;为增加搜索空间的多样性,变领域搜索中的局域搜索算法采用基于调度目标值容许偏差的阈值接受策略。对72个准时制调度的Benchmark算例的仿真结果表明,变领域搜索/数学规划混合算法获得了35个算例的已知最好解,并且更新了其中25个算例的已知最好解。

摘要：针对作业车间现有瓶颈识别方法的不足,提出了一种基于正交试验的瓶颈识别方法。该方法利用正交表和多种分派规则构造试验方案,以生产系统作业目标为衡量指标,快速便捷地实现瓶颈机器的识别。该方法能够在生产任务执行之前,预先给出瓶颈机器所在,以指导生产计划和相关生产准备。通过与移动瓶颈识别法对不同规模的作业车间调度问题标准算例进行仿真对比,证明了该方法的优越性和可靠性。

摘要：针对作业车间分批调度问题,集成可变子批划分和子批混排策略,考虑批量划分约束、子批混排加工约束等,建立了最小化能耗和完工时间的混排可变分批调度优化模型,并提出了一种改进多目标混合进化算法。为了协调算法的全局搜索与局部搜索性能,将Jaya算法种群更新机制引入基于分解的多目标进化算法中,同时结合混排可变分批调度问题特征,设计了一种基于子批拆分/合并与关键链相结合的局部搜索策略。基于不同规模算例,对比分析了所提出的算法与其他经典算法的求解性能。实验结果表明,所提出的算法在Pareto解集收敛性和分布性方面具有明显优势,同时所提出的混排可变分批策略可有效降低能耗、缩短完工时间。

摘要：加工时间离散可控作业车间调度问题(Job-shop scheduling problem with discretely controllable processing times,JSP-DCPT)是经典作业车间调度问题(Job-shop scheduling problem,JSP)的一类扩展问题。为避免通过多项式时间近似方法求解JSP-DCPT的近似问题,提出一种混合算法直接求解JSP-DCPT。该算法基于分解方法,嵌套一种禁忌搜索模拟退火混合算法TSSA和一种快速精英保留非支配排序遗传算法NSGA-II,以分别高效求解JSP-DCPT分解所得的JSP子问题和离散时间—成本权衡子问题。基于JSP标准算例FT06,FT10和FT20构造3个不同问题规模的测试算例,试验仿真结果表明,混合算法能够得到收敛的帕累托边界。