在一些经典调度问题中,通常假设工件的加工时间为常数,并且在加工过程中机器可以持续加工工件。但在许多实际生产过程中,由于机器的老化或其他原因会导致机器的加工效率下降,从而使得工件所需的实际加工时间随其开始加工时间的推迟而增大,这种现象称为机器具有恶化效应。同时,由于一些内部或外部原因,会使机器在加工过程中发生中断,往往不能持续工作。因此,需要对机器进行维护以提高机器的加工效率或防止机器发生中断。本文主要研究考虑机器可随机中断且具有时间相关恶化效应的平行机调度问题。在该问题中,由于机器恶化效应的影响,工件的实际加工时间定义为其开始加工时间的非减函数。此外,由于一些内部或外部原因,部分机器会发生随机干扰,其中中断的开始时刻是已知的,但中断是否发生具有一定的随机性且中断时长服从一定的概率分布。机器中断发生后,有两类决策可以考虑。一类是在机器中断发生后立即对机器进行维护,维护后的机器将恢复初始状态。另一类是不进行维护。目标是确定一个最优调度以最小化工件完工时间和的数学期望。本文的主要研究内容和创新点如下：(1)对于工件不可中断的情形,证明了当机器数为输入变量时相应问题是强NP-难的,当机器数为固定量时则是NP-难的。在机器数固定的条件下,针对中断发生后是否对机器进行维护两种情形,分别设计了伪多项式时间动态规划算法,进而说明了相应问题是一般NP-难的,进一步证明了当中断仅发生在其中一台机器上时,相应问题存在完全多项式时间近似方案。(2)对于工件可中断的情形,证明了当机器数为输入变量时相应问题是强NP-难的,当机器数为固定量且中断发生在其中至少两台机器上时相应问题是NP-难的。在机器数固定的条件下,针对中断发生后是否对机器进行维护两种情形,分别设计了伪多项式时间动态规划算法,进而说明当中断发生在其中至少两台机器上时相应问题是一般NP-难的。然而,当机器数为固定量且中断仅发生在其中一台机器上,相应问题是否是NP-难的仍是未知的。