调度是运筹学与控制论学科的重要研究方方向,关于它的论文有很多。在这些经典的调度问题中,通常假设工件的加工时间通常为常数,并且在工件加工过程中机器可以持续加工工件。在这错综复杂的现实生活中,调度问题是不拘一格的,有时工件的实际加工时间随其开始加工时间的推迟而增大,工作效率越来越低;有时工件的实际加工时间随其开始加工时间的推迟而减小,工作效率越来越高;而有些情况下,工件的实际加工时间是与其所排位置相关的。与此同时,由于一些内部的原因和外部环境的限制,会使机器在加工过程中发生中断,使机器不能持续工作。基于此,本文研究带机器随机故障和加工时间与位置相关的平行机调度问题。该问题中,工件的实际加工时间是与其所排位置相关的一般函数。在机器运行过程中,某些随机事件的发生会导致部分机器不能正常工作。本文假设这些随机事件的开始时间已知,且它们会以一定的概率持续一段时间。当随机事件发生时,本文考虑工件可中断和不可中断两种不同的情形下,目标是最小化工件总完成时间的期望。本文将对相应问题不同情形的复杂性进行分析并设计相应的伪多项式时间算法。具体研究内容如下:(1)工件不可中断:在机器数量固定的情况下,证明了相应问题是NP难的,设计了伪多项式时间动态规划算法,进而说明了相应问题是一般NP难的。具体地,本文仅详细分析两台机器中有一台机器发生中断的情况,然后简单讨论如何将结论推广到m台机器中有K台机器会发生中断的情况。(2)工件可中断:在机器的数量变化时,证明了相应的问题是强NP问题;在机器数量为固定值且发生中断的机器大于等于两台的情况下,证明了该问题是NP难的,设计了伪多项式时间动态规划算法,进而说明了相应问题是一般NP难的;然而,当中断仅发生在一台机器上时该问题是否为NP难的仍是未知的。