中文摘要：

研究了一类机器带周期性维护时段且完工工件需要运输的新型排序问题。在该问题中,机器需要进行周期性的维护,且被维护时段打断的工件加工不可恢复;工件具有不同的尺寸且工件的加工时间与物理尺寸大小具有一定的比例关系,每个维护时段内只允许加工一个批次的工件;加工完的工件需要由一辆带有容量限制的运输工具运往客户。算法的目标是极小化所有工件加工完成并运送到客户的时间。证明了该问题是强NP-Hard问题,设计了该问题的一个多项式时间近似算法,并证明了该算法的最坏情况界不大于5/3。

英文摘要：

A new single machine scheduling problem with periodic maintenance and workpiece delivery coordination is considered in the paper.In this problem,the machine needs periodic maintenance,and the interrupted workpiece in maintenance period cannot be recovered.The workpieces have different size,and certain proportional relation exists between workpiece processing time and physical size.A batch of workpieces can only be processed in each maintain period.The finished workpieces need to be delivered to the customer by a vehicle with capacity limitation.The obj ective of algorithm is to minimize the duration from finishing all workpieces to delivery to the customer.We first prove that the problem is NP-hard problem.Then,we provide a polynomial time approximation algorithm and prove the worst case boundary of this algorithm is not greater than 5/3 .