基于设备驱动和实质路径的动态并行综合柔性调度算法

针对静态重叠时间段在实际加工过程中并非一定重叠,导致工序并行处理效果不佳的问题,提出基于设备驱动和实质路径的复杂单产品动态并行综合柔性调度算法。该算法先按最短加工时间为工序选择计划加工设备,初步缩小工序加工设备的选择范围;再采用空闲设备驱动策略动态确定并行工序,对并行工序按提出的并行优化分配策略和最早加工结束策略确定并行加工设备。在采用并行优化分配策略时,运用实质短路径策略,避免了某空闲设备上存在多个只能串行加工的工序时,出现较长实质路径的情况。由于该算法在每一个设备驱动时刻,动态的分配可重叠加工的工序到不同的设备上同时加工,实现工序间实质性的并行处理。实例表明:该算法在不提高算法复杂度的前提下,不仅兼顾设备驱动策略和动态实质短路径策略的优点,而且提高了复杂单产品综合柔性调度设备利用率和并行处理率,缩短产品的完成时间。     

基于交货期紧迫度的综合调度算法

为解决开始时间与交货期都不相同的多品种小批量复杂产品综合调度问题,提出基于交货期紧迫度的综合调度算法。该算法根据产品加工的开始时间由前到后排序调度;当存在多产品开始时间相同时,根据产品优先加工的紧迫度,确定它们的调度次序;如果存在紧迫度相同的产品,将按交货期由早到晚排序调度;若交货期也相同,则将它们虚拟成一个产品统一调度;对被调度产品采用长路径策略和短用时策略确定其各工序的调度次序,并结合设备工序紧凑法确定工序的开始时间。该算法结合产品紧迫度和设备工序紧凑法的优点,使开始时间不同的多产品在尽量减少设备空闲时间的情况下,按交货期完工。理论分析和实例表明,该算法可在二次复杂度内给出较合理的综合调度方案。     

基于择时的二车间综合调度算法

针对现有二车间综合调度算法在处理具有相同设备资源的二车间综合调度问题时,注重工艺树的横向并行处理,忽略纵向串行工序之间的紧密度,将二车间均衡处理或减少工序迁移次数一并做为调度目标导致不必要时间开销的问题,提出了基于择时的二车间综合调度算法。同时,提出了工序序列排序策略,将加工工艺树划分为若干工序序列,并根据其路径长度确定调度次序;提出了二车间择时调度策略,为工序寻找加工开始时间和加工车间,生成使当前部分产品加工总用时最小的工序调度方案。若该方案不唯一,则选择在二车间中该工序加工结束时间最早的工序调度方案。所提算法既保证了并行工序的并行处理,又有效地提高了串行工序的紧密度,避免了无效工序迁移带来的时间开销。通过实例说明了所提算法的有效性。     

存在预启动设备的综合调度算法

针对目前综合调度研究中没有考虑存在预启动设备的情况,忽略预启动时间对整体加工时间影响的问题,提出存在预启动设备的综合调度算法.该算法在预启动设备处于空闲状态时采用提出的预启动长路径优先策略,在预启动设备处于工作状态时采用提出的预启动短路径优先策略,以提高预启动设备的并行化和减少了设备的预启动次数;采用提出的调整序列确定策略,确定产生设备空闲时间段的工序为调整目标;采用提出的可调序列工序调整策略,对产生设备空闲的工序的前序工序按层序对其加工时间进行调整,以提高设备的利用率.实例说明提出的算法解决了存在预启动设备的综合调度问题,有一定理论和实际意义.     

基于关键设备工序紧凑的工序分类、分批的Job-Shop调度算法

通过对产品加工树的分解,可将产品加工工序分为存在具有唯一紧前、紧后相关工序和独立工序,在对这两类工序研究分批综合应用拟关键路径法(ACPM)和最佳适应调度方法(BFSM)调度时,考虑关键设备的工序紧凑性。通过分析与实例验证,所提出的调度方法对解决复杂Job-Shop调度问题不仅算法简练而且效果较好。     

前移存在调整时间综合调度工序的算法

针对目前存在调整时间的综合调度算法只考虑快速插入调整时间实现调度方案,没有考虑调整时间会随工序次序改变影响调度结果的问题,提出通过改变工序调度次序前移存在调整时间综合调度工序的算法。该算法在保证相关工序不后移的条件下,通过改变相同加工设备上具有相同工艺紧后工序的工序调度次序,从而改变工序之间的调整时间,使调整工序最晚结束时间提前,使其工艺紧后工序开始时间有可能提前,从而实现提高设备利用率,提前产品最终完工时间。实例表明该算法可获得存在调整时间的综合调度问题的更优解。     

考虑层级调度次序的资源协同综合调度算法

针对同层工序数量较多的多品种单件或小批量复杂产品的综合调度问题,以优化产品加工的时间成本和提高设备利用率为目标,提出了考虑层级调度次序的资源协同综合调度算法。算法设计了三级调度策略,首先是优先级调度策略,提高了工序间纵向加工的紧密度;其次是叶节点调度策略,实现了横向工序的并行优化;最后是短用时调度策略,充分利用了设备的空闲时间,提高了设备利用率。利用基于Petri网的生产过程模型进行调度仿真,实验结果表明了算法的有效性和可行性。     

动态调整设备维护开始时间的综合调度算法

针对综合调度领域中关于设备维护的问题,提出动态调整设备开始维护时间的调度算法.算法在定义设备超负荷运行时间的基础上,按照加工设备与加工工序的对应顺序,首先调度叶结点工序分类集,再以实际加工完毕时间与设备预计维护时间差值最小的原则,利用动态规划的方法依次采用"关键路径法+短用时+层优先"的顺序调度工序集工序,判断设备是否存在超负荷的情况调整设备的维护始点,最后依据设备超负荷的具体情况决定设备开始维护的实际时间.通过实例表明,算法能够有效减少设备的超负荷运转,并提高设备利用率.     

存在设备无关延迟约束的综合柔性调度算法

针对加工和装配综合的柔性调度中忽略工序间存在设备无关延迟约束导致调度结果不精确的问题,提出存在设备无关延迟约束的综合柔性调度算法。该算法通过将设备无关延迟时间转换为设备无关延迟工序,提出存在设备无关延迟约束的综合柔性调度工艺模型;通过将设备无关延迟约束工序转换为顺序约束工序的策略,将存在设备无关延迟约束的柔性加工问题转换为一般柔性加工问题;对一般柔性加工问题采用短用时策略和设备均衡策略确定标准工序的加工设备,将一般柔性加工问题简化为一般综合调度问题并用长路径优先策略调度;对于路径长度相等且在同一设备上加工的标准工序,提出调度前续短路径策略选择调度工序。实例表明,该算法通过考虑设备无关延迟约束时间使综合柔性调度的结果更精确并且能减少产品总的加工时间。     

考虑串行工序紧密度的择时综合调度算法

针对目前综合调度算法在处理一般综合调度问题时为了兼顾加工工艺树中工序的并行处理,忽略串行工序之间紧密度,影响调度结果的问题,提出考虑串行工序紧密度的择时综合调度算法。该算法提出工序序列排序策略,从工艺树的整体结构出发,将其划分成内部工序只具有串行关系的工序序列,根据工序序列的长短确定其调度顺序;提出择时调度策略,结合工艺树自身特点,为调度工序选择若干合法加工时间点,分别在每个时间点调度工序,得到该工序的试调度方案集合,从其中选择加工总用时最小的方案作为工序调度方案,若不唯一,则选择工序加工时间最早的方案。实例表明,该算法既保证并行工序的并行处理,又有效提高串行工序的紧密度,优化了综合调度的结果。