Online tradeoff scheduling on a single machine to minimize makespan and total weighted completion time
Online tradeoff scheduling on a single machine to minimize makespan and total weighted completion time
复制标题
DOI：
10.1016/j.ijpe.2014.07.027
复制
发表时间：
2014-12
影响因子：
12
通讯作者：
Ran Ma;Jinjiang Yuan
中科院分区：
文献类型：
--
作者：
Ran Ma;Jinjiang Yuan
在本文中，我们引入在线权衡调度的概念，以最小化两个目标函数f1和f2同时。一个在线算法A称为（ρ 1，ρ 2）-竞争极小化f1和f2，如果A是ρ 1-竞争极小化f1和ρ 2-竞争极小化f2.一个（ρ 1，ρ 2）-竞争在线算法A称为非支配的，如果不存在其它（ρ 1′，ρ 2′）-竞争在线算法A′使得（ρ 1′，ρ 2′）≤（ρ 1，ρ 2）且ρ 1′< ρ 1或ρ 2′< ρ 2.对于单机在线折衷调度问题，以最小化完工时间和加权完工时间为目标，对每个α（0< α≤ 1），提出了一个非支配（1+ α，1+ 1/α）竞争在线算法.
In this paper we introduce the concept of online tradeoff scheduling to minimize two objective functions f 1 and f 2 simultaneously. An online algorithm A is called (ρ 1, ρ 2)-competitive for minimizing f 1 and f 2 if A is ρ 1-competitive for minimizing f 1 and ρ 2-competitive for minimizing f 2. A (ρ 1, ρ 2)-competitive online algorithm A is called nondominated if there is no other (ρ 1′, ρ 2′)-competitive online algorithm A′ such that (ρ 1′, ρ 2′)≤(ρ 1, ρ 2) and either ρ 1′< ρ 1 or ρ 2′< ρ 2. For the online tradeoff scheduling on a single machine to minimize makespan and total weighted completion time, we present a nondominated (1+ α, 1+ 1/α)-competitive online algorithm for each α with 0< α≤ 1.