华荣伟，潘虹，严甜海

（1.杭州医学院，浙江 杭州 310053；2.浙江大学 数学科学学院，浙江 杭州 310058）

0 引言

在实际生产中，可能因机器发生故障在一段时间内不能加工工件，也可能因预防性检修暂时停止加工，这就引出了在机器维护时段的排序问题。对机器在维护时段的排序问题研究始于20 世纪80 年代［1-2］，相关模型和结果可参考综述文献［3-5］。根据工件在加工过程中因机器维护被打断后的不同处理方式，分为三类［4］：（1）维护时段结束后，已经完成的部分作废，需重新加工该工件，称不可恢复（nonresumable）；（2）维护时段结束后，只需继续加工该工件尚未完成的部分，称可恢复（resumable）；（3）维护时段结束后，除继续加工该工件尚未完成的部分，还需处理已完成的部分，称半可恢复（semiresumable）。下文若不特别说明，所涉及的均为不可恢复问题。根据机器维护时段是否具有规律性，分为周期性维护（periodic maintenance）和非周期性维护。在周期性维护中，同一台机器两个相邻的维护时段之间具有某种规律。目前已有研究的模型大致可分为三类：相邻维护时段之间间隔恰为T，称为不可移动［6］；相邻维护时段之间间隔不超过T，称为可移动［7］；相邻维护时段之间间隔不小于-T，不超过-T，称为双向可移动［8］。一般假定维护时长t 为一固定值。对非周期性维护问题，一般均假设每台机器至多只有一个维护时段，否则很可能不存在最坏情况比为常数的近似算法［9］。因此，对有多个维护时段的周期性维护问题研究更困难，研究成果也相对较少。对于单……