传统的调度研究假设机器可以一直被使用,直到加工完所有需要加工的工件.然而,在现实生产活动中,往往需要对机器进行预防性的维护.常见的维护类型有:单次维护、周期维护和工具更换维护.本文研究了预防性维护下一类混合型平行机调度问题:有n个工件需要加工,有两台平行机可供使用,其中一台需要工具更换维护,另一台需要周期维护,目标是确定每次工具更换维护的开始时刻和每个工件所对应的机器及其开始加工时刻使得这n个工件的时间表长(即最后完工的工件的完工时刻)最小.本文的主要工作如下.(1)分析了该问题的计算复杂性和不可逼近性.证明了该问题是强NP-难的并且不存在最坏情况界小于2的多项式时间算法除非P=NP.(2)为求解中小规模的调度实例,基于“把维护看作工件”、“机器拼接”和“工件与加工位置一一对应”的思想给出了两个数学规划模型,基于“装箱问题”的思想给出了另外两个数学规划模型,并编程实现了上述四个模型.(3)为求解大规模的调度实例,基于“工件完成时间优先分配机制”,“机器完成时间优先分配机制”,经典的“LPT规则”和“LS规则”设计了四个启发式算法.通过对上述四个算法所生成的调度方案的研究,提出了对上述算法得到的调度方案进行“后优化”想法并以此为基础设计了四个新的算法.注意到存在实例表明没有一个算法占绝对优势,于是把上述八个算法的输出结果中最好的一个做为最终输出,这样就得到了第九个启发式算法.(4)从理论上对上述九个算法进行了最坏情况分析.证明了当最后一个非空维护间隔中至少有两个工件时,上述九个算法的最坏情况界均为2.(5)通过数值实验对上述九个算法进行了平均误差分析和最大误差分析.为了避免使用数学规划模型求解大规模的调度实例,根据机器的特点设计了“逐次半毫升水量转移算法”来求最优时间表长的一个下界,根据工件加工的特点得到了最优时间表长的另外一个下界.取这两个下界中较大者做为数值实验中的比较对象,通过编程实现了上述九个算法和下界,给出了工件规模为20,200和2000下各36组参数(每组参数各取100个实例)对应的平均误差和最大误差.结果表明,基于“机器完成时间优先分配机制”和“LPT规则”的算法误差较小.(6)假定维护时长是其上一次维护间隔中的负载(即所加工的工件的加工时长之和)的非负增函数,得到了该平行机调度问题的一个扩展版本,给出了四个数学规划模型.