Optimal algorithm for semi-online scheduling on two machines under GoS levels

Taibo Luo; Yinfeng Xu

doi:10.1007/s11590-014-0838-3

Optimal algorithm for semi-online scheduling on two machines under GoS levels

Taibo Luo
, Yinfeng Xu

管理学院

Sichuan University

科研成果: 期刊稿件 › 文章 › 同行评审

9 引用（Scopus）

摘要

Recently, Liu et al. (J Combin Optim 21:138–149, 2011) studied the semi-online scheduling problem on two machines under a grade of service provision. As the sum of jobs’ processing times Σ is known in advance and the processing times are bounded by an interval [1,α] where 1<α<2, they presented an algorithm which is (Formula Presented)-competitive when (Formula Presented). In this paper, we give a modified algorithm which is shown to be optimal for arbitrary α and Σ.

源语言	英语
页（从-至）	207-213
页数	7
期刊	Optimization Letters
卷	10
期	1
DOI	https://doi.org/10.1007/s11590-014-0838-3
出版状态	已出版 - 1 1月 2016

访问文件

10.1007/s11590-014-0838-3

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{54e329d45cd34b3e9ccc90e2a2d0e6d4,

title = "Optimal algorithm for semi-online scheduling on two machines under GoS levels",

abstract = "Recently, Liu et al. (J Combin Optim 21:138–149, 2011) studied the semi-online scheduling problem on two machines under a grade of service provision. As the sum of jobs{\textquoteright} processing times Σ is known in advance and the processing times are bounded by an interval [1,α] where 1<α<2, they presented an algorithm which is (Formula Presented)-competitive when (Formula Presented). In this paper, we give a modified algorithm which is shown to be optimal for arbitrary α and Σ.",

keywords = "Algorithms, Bounded processing times, Grade of service, Online scheduling, Total processing time",

author = "Taibo Luo and Yinfeng Xu",

note = "Publisher Copyright: {\textcopyright} 2014, Springer-Verlag Berlin Heidelberg.",

year = "2016",

month = jan,

day = "1",

doi = "10.1007/s11590-014-0838-3",

language = "英语",

volume = "10",

pages = "207--213",

journal = "Optimization Letters",

issn = "1862-4472",

publisher = "Springer Verlag",

number = "1",

}

TY - JOUR

T1 - Optimal algorithm for semi-online scheduling on two machines under GoS levels

AU - Luo, Taibo

AU - Xu, Yinfeng

PY - 2016/1/1

Y1 - 2016/1/1

N2 - Recently, Liu et al. (J Combin Optim 21:138–149, 2011) studied the semi-online scheduling problem on two machines under a grade of service provision. As the sum of jobs’ processing times Σ is known in advance and the processing times are bounded by an interval [1,α] where 1<α<2, they presented an algorithm which is (Formula Presented)-competitive when (Formula Presented). In this paper, we give a modified algorithm which is shown to be optimal for arbitrary α and Σ.

AB - Recently, Liu et al. (J Combin Optim 21:138–149, 2011) studied the semi-online scheduling problem on two machines under a grade of service provision. As the sum of jobs’ processing times Σ is known in advance and the processing times are bounded by an interval [1,α] where 1<α<2, they presented an algorithm which is (Formula Presented)-competitive when (Formula Presented). In this paper, we give a modified algorithm which is shown to be optimal for arbitrary α and Σ.

KW - Algorithms

KW - Bounded processing times

KW - Grade of service

KW - Online scheduling

KW - Total processing time

UR - https://www.scopus.com/pages/publications/84953837282

U2 - 10.1007/s11590-014-0838-3

DO - 10.1007/s11590-014-0838-3

M3 - 文章

AN - SCOPUS:84953837282

SN - 1862-4472

VL - 10

SP - 207

EP - 213

JO - Optimization Letters

JF - Optimization Letters

IS - 1

ER -

Optimal algorithm for semi-online scheduling on two machines under GoS levels

摘要

访问文件

其它文件与链接

学术指纹

引用此