工件到达时间未知的动态车间滚动重调度

研究工件动态到达且到达时间未知的车间重调度问题,目标是最小化所有工件的拖期和.动态事件频繁的调度环境,对调度算法的计算效率要求很高.在滚动时域分解方法框架下,提出关键工序集的概念,采用混合遗传算法确定关键工序集合及其对应的最优部分调度.在解码过程中,采用混合调度生成器将染色体中的基因转化为部分可行调度,对没有参与遗传进化的工序采用改进的修正交货期(Modified due date,MDD)规则确定其在机器上的加工顺序,以完全调度的目标值评价染色体的适应度.对大量算例的仿真表明基于关键工序集的重调度算法对动态事件的响应速度,大大优于基于完全工序集的重调度算法,并且具有良好的全局性能,兼顾了实际动态Job shop系统对调度性能和计算效率的要求.     

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

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

基于工序约束并行机模型的冲压线调度

根据双向冲压线的实际生产特点,提出了一种基于工序约束并行机的双向冲压线调度模型.在该模型中,工件同时在牛产线两端按设备顺序加工,且加工工件及其加工开始时间和完工时间受生产线两端工件工序数目约束和生产线设备加工能力的约束,给出了该约束的规则;设计了启发规则和遗传算法混合的求解算法.最后,以最大完工时间为优化指标进行验证,证明该模型具有较好的实用价值.     

电机产品加工的动态调度算法

考虑多个具有不同开始时间的电机产品加工动态调度问题，将产品加工树的工序，分为具有唯一紧前或紧后工序的相关工序和独立工序两类，提出相关工序调度的拟关键路径法和独立工序调度的最佳适应调度法。结合拟关键路径法和最佳适应调度法，提出考虑关键设备的工序紧凑的多产品动态调度算法。实例数据表明，动态调度算法在总加工时间方面比一般启发式算法更短，适合于有不同开始时间的多产品动态调度环境。     

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

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

基于邻域渲染的二车间综合调度算法

针对如何将复杂产品工序有效地分配到具有相同设备资源的两车间加工的问题,提出了基于邻域渲染的二车间综合调度算法。该算法为了实现产品加工尽早结束,提出关键设备均衡策略,将关键设备上的所有加工工序预先按并行加工时间最长方案均衡的分配到二车间;为了减少两车间之间的迁移次数,提出邻域渲染策略和同设备工序车间选择策略,通过计算未分配加工车间工序的邻域加工工序的渲染因子和影响因子确定其所在的加工车间;为了提高调度效率,采用动态关键路径策略和短用时策略确定工序调度次序,按序确定工序的加工车间和开始加工时间。分析和实例表明,所提出的算法产品加工时间较短、工序迁移次数较少且不增加算法复杂度。     

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

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

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

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

同顺序加工调度问题的一种精确求解方法

同顺序加工调度问题是NP问题,分析了这类问题的特点及求解的难点,结合广度优先搜索方法的特点,提出了启发式双侧广度优先搜索方法,混合使用动态规划方法、下界算法和近似求解方法求解同顺序加工调度问题.实验结果表明,启发式双侧广度优先搜索方法求解同顺序加工调度问题时,可以大大减少搜索次数,适合于求解工序较少的同顺序加工调度问题;如果下界算法较好,还能快速求解工序较多的同顺序加工调度问题.     

存在多设备工序的综合调度算法

针对工序集中存在需要多台设备协同完成加工的多设备工序的综合调度问题,提出一种把多设备工序设计成在多个相关设备上同时加工的多个虚拟工序的方法。该算法把产品加工树转化为多设备工序被设计成虚拟工序组的虚拟加工工艺树,为了优先调度虚拟工序组,将虚拟加工工艺树分解为以虚拟工序组为根结点的子树和剩余标准工序组成的子树,优先调度以虚拟工序组为根结点的子树;当以虚拟工序组为根结点的子树不唯一时,按子树上虚拟工序组个数多少确定子树的调度次序;对每个以虚拟工序组为根结点的子树,优先调度虚拟工序组个数较多的路径上工序;为了使相关虚拟工序同时开始加工,提出虚拟工序动态调整策略。理论分析和实例表明,所提出的调度算法能够较好地解决存在多设备工序的综合调度问题。