.png){kind=icon}
返回
Preemptive scheduling on two parallel machines with a single server
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cie.2013.07.020.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This paper addresses a preemptive scheduling problem on two parallel machines with a single server. Each job has to be loaded (setup) by the server before being processed on the machines. The preemption is allowed in this paper. The goal is to minimize the makespan. We first show that it is no of use to preempt the job during its setup time. Namely, every optimal preemptive schedule can be converted to another optimal schedule where all the setup times are non-preemptively performed on one machine. We then present an algorithm with a tight bound of 4/3 for the general case. Furthermore, we show that the algorithm can produce optimal schedules for two special cases: equal processing times and equal setup times, which are NP-hard in the non-preemptive version. (C) 2013 Elsevier Ltd. All rights reserved.
Keyword:
Preemptive scheduling
Sever
Algorithm
Worst case ratio
Makespan
期刊
IF:
6.5
论文数:
1.0W
被引数:
3.8W
机构
引用论文
.png){kind=icon}
Equal processing and equal setup time cases of scheduling parallel machines with a single server
PREAI
分享收藏
查看更多内容