机器调度问题是一类典型的组合优化问题,受到了学术界广泛的关注。在实际的生产活动中,往往会出现机器由于突发故障或预防性维护活动而导致不可用的情形,因此,对考虑机器存在不可用时段的调度问题的研究显得十分重要。在此背景下,本文研究了机器具有维护时段的平行机调度问题,分别对机器维护时长固定和维护时长不固定两种情况进行了研究与分析。针对机器具有固定维护时长的情形,研究了最小化最大完工时间的问题。基于对经典的LPT(Longest Processing Time First)和FFD(First Fit Decreasing)规则的改进,提出了MFFD-LPT算法,理论证明了该算法的最坏误差界为9v/5u,同时提出了MFFD-LPT算法的修正算法DA,大规模随机数据实验证明了DA算法对MFFD-LPT算法求得的解的修正率在20%-30%之间,体现了很好的修正效果。接着,本文考虑了一种更为普遍的情形,研究了机器具有不固定维护时长的平行机调度问题,调度的目标同样是最小化最大完工时间。在机器具有固定维护时长的研究基础上,提出了MFFD-LPT’算法,通过数学分析,证明了MFFD-LPT’算法的最坏误差界为9R/5L,然后通过模拟退火算法对MFFD-LPT’算法产生的解进行修正,最后进行了大规模计算机模拟实验,验证了算法的有效性。