SINGLE-MACHINE FLOW-TIME SCHEDULING WITH SCHEDULED MAINTENANCE

被引：185

作者：

LEE, CY ^{[1
]}

LIMAN, SD ^{[1
]}

机构：

[1] TEXAS TECH UNIV,DEPT IND ENGN,LUBBOCK,TX 79409

来源：

ACTA INFORMATICA | 1992年 / 29卷 / 04期

关键词：

D O I：

10.1007/BF01178778

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we investigate a single machine scheduling problem of minimizing the sum of job flow times subject to scheduled maintenance. We first provide an NP-completeness proof for the problem. This proof is much shorter than the one given in Adiri et al. [1]. The shortest processing time (SPT) sequence is then shown to have a worst case error bound of 2/7. Furthermore, an example is provided to show that the bound is tight. This example also serves as a counter-example to the 1/4 error bound provided in Adiri et al. [1].

引用

页码：375 / 382

页数：8