ONLINE SCHEDULING OF TWO UNIFORM MACHINES TO MINIMIZE TOTAL COMPLETION TIMES

被引：6

作者：

Liu, P. ^{[1
]}

Lu, X. ^{[1
]}

机构：

[1] E China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China

来源：

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION | 2009年 / 5卷 / 01期

关键词：

Scheduling; Uniform machine; Online algorithm; Competitive ratio; ALGORITHMS; SINGLE;

D O I：

10.3934/jimo.2009.5.95

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

In this paper, we study the online scheduling problem on two uniform machines with speeds 1 and s >= 1, in which jobs are arriving over time. We consider both the preemptive and the non-preemptive machine environments. We first present a 2.618-competitive algorithm for the non-preemptive setting with the objective to minimize the total completion times. In the preemptive setting with the objective to minimize the total weighted completion times, we give an online algorithm which has a competitive ratio of 2.

引用

页码：95 / 102

页数：8

共 14 条

[1] Online scheduling of a single machine to minimize total weighted completion time [J].

Anderson, EJ ;

Potts, CN .

MATHEMATICS OF OPERATIONS RESEARCH, 2004, 29 (03) :686-697

[2]

[Anonymous], 1996, LECT NOTES COMPUTER

[3] Approximation techniques for average completion time scheduling [J].

Chekuri, C ;

Motwani, R ;

Natarajan, B ;

Stein, C .

SIAM JOURNAL ON COMPUTING, 2001, 31 (01) :146-166

[4]

Correa JR, 2005, LECT NOTES COMPUT SC, V3509, P196

[5] Scheduling to minimize average completion time: Off-line and on-line approximation algorithms [J].

Hall, LA ;

Schulz, AS ;

Shmoys, DB ;

Wein, J .

MATHEMATICS OF OPERATIONS RESEARCH, 1997, 22 (03) :513-544

[6]

Labetoulle J., 1984, Progress in combinatorial optimization, P245, DOI DOI 10.1016/B978-0-12-566780-7.50020-9

[7]

Lawler E., 1993, LOGISTICS PRODUCTION, DOI 10.1016/S0927-0507(05)80189-6

[8]

LENSTRA JK, 1977, EUR J OPER RES, V1, P339

[9] A class of on-line scheduling algorithms to minimize total completion time [J].

Lu, X ;

Sitters, RA ;

Stougie, L .

OPERATIONS RESEARCH LETTERS, 2003, 31 (03) :232-236

[10] On-line scheduling to minimize average completion time revisited [J].

Megow, N ;

Schulz, AS .

OPERATIONS RESEARCH LETTERS, 2004, 32 (05) :485-490

← 1 2 →