加工和装配是产品制造的主要任务,加工和装配任务调度对产品的生产率和经济性都有很大的影响。加工和装配任务调度算法是研究虚拟制造、敏捷制造和精益制造中设计计算机集成制造系统的基础,不仅是当前调度理论中所研究的重要问题之一,而且在机械制造及自动化等先进制造技术领域发挥重要的作用。此项研究既可以促使调度问题的发展及其相关问题的研究,又可以使企业实现加工和装配调度计划的合理编排,从而减少人们的繁杂劳动,合理优化地组织生产,缩短生产周期,降低成本,提高生产效率。不仅符合当前国家大力发展装备制造业的国情,有重要的理论和社会意义,而且还会产生可观的经济效益。本文针对简单产品工序调度(本文简称产品调度)算法局限于纯加工或纯装配调度,无法考虑工件间存在约束关系的复杂产品制造过程中内在的加工和装配之间的并行关系,影响产品制造效率的问题,通过对工件间存在约束关系的复杂产品调度问题分析,对工件间存在约束关系的复杂单个(多个、动态)产品加工和装配过程综合调度优化、工件间存在约束关系的产品在有相同设备情况时的调度优化、快速判断影响加工与装配过程的可增加瓶颈设备和工件间存在约束关系时工序非紧密衔接的调度优化等4个问题进行了研究,并对提出的算法进行了分析和实例验证:1.对工件间存在约束关系的复杂单个产品,为了实现产品加工和装配过程综合调度,提出采取统一控制加工和装配设备、统一调度加工和装配工序的方法;为了减少工序的选择范围,提高调度效率,提出根据复杂单个产品树状工艺图(工艺树)动态地生成备选的预调度工序集合;通过综合考虑加工树纵(加工路径)横(加工工序层)结构关系,提出短用时、长路径和动态调整等调度策略进行工序调度优化,实现具有纵横双向调度优化的效果。对复杂多产品和多产品动态调度问题采取建立虚拟工艺树的方法向复杂单个产品问题简化,方便复杂多产品问题和复杂多产品动态问题的调度优化算法的实现。2.对工件间存在约束关系的复杂产品在有相同设备情况时的调度优化问题,通过分析产品工艺树结构,利用树状结构具有末端分枝繁衍的特点,对工艺树进行分段,根据末端工序的特点将工序分为相关工序和独立工序,并根据前沿贪心规则和最优适应规则对段内工序设计了调度的目标函数,再利用递归迭代完成整个复杂产品工艺树上工序的调度;对相同设备工序提出进行二次均衡分配的具有互补性的调度函数,使独立工序与相关工序或相关工序与相关工序并行处理,实现相同设备充分并行处理。通过构造成虚拟工艺树的方法,简化并解决相同设备情况时多产品或动态产品调度问题。3.对制约工件间存在约束关系的复杂产品生产效率的单一设备,通过对并行工序的研究,提出为每个工序标记它所在工艺图中的路线号,快速判断设备上并行工序的方法,以并行工序总时间最大设备为可增加的制约产品生产效率单一设备,即可增加的瓶颈设备。当并行工序总时间最大设备不唯一时,考虑紧前工序影响其后继工序开始加工的时间,提出将紧前工序数作为判断可增加瓶颈设备的第二因素。通过设计虚拟工艺树,解决了动态调度中确定可增加瓶颈设备的问题。4.对工件间存在约束关系的复杂产品工序非紧密衔接时的调度优化问题,为了表现工序间空隙的约束关系,提出了该类问题扩展工艺树结构;定义工序非紧密衔接的空隙为虚拟的延迟工序,并为虚拟的延迟工序设计虚拟设备,提出了工序非紧密衔接调度问题向一般调度问题转化的策略,将工序非紧密衔接的调度问题转化为一般工件间存在约束关系的复杂产品调度问题;通过对拟关键路径和最佳适应调度算法的分析,设计了一种通过优先调度延迟工序,对标准工序分批采用拟关键路径法和最佳适应调度法,同时考虑关键设备上标准工序尽量紧凑的非紧密衔接工序的动态调度优化算法。