Minimizing Total Weighted Flow Time with Calibrations
文献类型：会议论文
| 作者 | Vincent Chau; Minming Li; Samuel McCauley; Kai Wang |
| 出版日期 | 2017 |
| 会议日期 | 2017 |
| 会议地点 | Washington |
| 英文摘要 | In sensitive applications, machines need to be periodically calibrated to ensure that they run to high standards. Creating an efficient schedule on these machines requires attention to two metrics: ensuring good throughput of the jobs, and ensuring that not too much cost is spent on machine calibration. In this paper we examine flow time as a metric for scheduling with calibrations. While previous papers guaranteed that jobs would meet a certain deadline, we relax that constraint to a tradeoff: we want to balance how long the average job waits with how many costly calibrations we need to perform. One advantage of this metric is that it allows for online schedules (where an algorithm is unaware of a job until it arrives). Thus we give two types of results. We give an efficient offline algorithm which gives the optimal schedule on a single machine for a set of jobs which are known ahead of time. We also give online algorithms which adapt to jobs as they come. Our online algorithms are constant competitive for unweighted jobs on single or multiple machines, and constant-competitive for weighted jobs on a single machine. |
| 语种 | 英语 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/12636]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 作者单位 | 2017 |
| 推荐引用方式 GB/T 7714 | Vincent Chau,Minming Li,Samuel McCauley,et al. Minimizing Total Weighted Flow Time with Calibrations[C]. 见:. Washington. 2017. |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。