传统的调度研究假设机器一直可以使用直至加工完所有需要加工的工件。然而在实际的加工过程中，机器的某些零件，如机床的刀具由于磨损常常需要更换。在更换这些零件期间，机器是不可以加工工件的。记零件的使用寿命为T，把更换零件看作是对机器进行维护。本文研究了机器需要这种维护的一个单机调度问题1,M[0，T]‖Cmax和一个平行机调度问题P2,M1M[0，T]‖Cmax，其中M[0，T]表示机器相邻维护的时间间隔在区间[0，T]内取值，M1M[0，T]表示机器M1需要维护且其相邻维护的时间间隔在区间[0，T]内取值。对于上述两个调度问题，我们不仅需要安排工件的加工还需要确定何时对机器进行维护。目标是使得最后完工的工件的完工时刻尽量早。　　 首先，我们证明了这两个问题都是NP-难的。其次，我们设计了基于经典的LPT（Longest Processing Time first）算法的近似算法MLPTS和MLPTP分别来解决这两个问题。此外，我们还研究了调度问题P2,M1M[0，T]‖Cmax在线时的LS算法。我们证明了：（1）对于调度问题1,M[0，T]‖Cmax，MLPTS算法的最坏情况比是2；（2）如果P≠NP，那么MLPTS算法是调度问题1,M[0，T]‖Cmax的多项式时间最优近似算法；（3）对于调度问题1,M[0，T]‖Cmax，若t≤T，则MLPTS算法的最坏情况比小于3／2；（4）对于在线的调度问题P2,M1M[0，T]‖Cmax，LS算法的竞争比是2；（5）对于调度问题P2,M1M[0，T]‖Cmax，MLPTP算法的最坏情况比是3/2。