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

School of Management

Sichuan University

Research output: Contribution to journal › Article › peer-review

9 Scopus citations

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’ 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 Σ.

Original language	English
Pages (from-to)	207-213
Number of pages	7
Journal	Optimization Letters
Volume	10
Issue number	1
DOIs	https://doi.org/10.1007/s11590-014-0838-3
State	Published - 1 Jan 2016

Keywords

Algorithms
Bounded processing times
Grade of service
Online scheduling
Total processing time

Access to Document

10.1007/s11590-014-0838-3

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this