Qr code
DALIAN UNIVERSITY OF TECHNOLOGY Login 中文
Xin Han

Professor
Supervisor of Doctorate Candidates
Supervisor of Master's Candidates


Main positions:Professor
Gender:Male
Alma Mater:Kyoto University
Degree:Doctoral Degree
School/Department:Software School
Discipline:Computer Software and Theory. Operation Research and Control Theory
Contact Information:hanxin@dlut.edu.cn 0086-411-62274404
Click: times

Open time:..

The Last Update Time:..

Current position: Home >> Scientific Research >> Paper Publications

Online minimum makespan scheduling with a buffer

Hits : Praise

Indexed by:会议论文

Date of Publication:2012-05-14

Included Journals:EI、Scopus

Volume:7285 LNCS

Page Number:161-171

Abstract:In this paper we study an online minimum makespan scheduling problem with a reordering buffer. We obtain the following results, which improve on work from FOCS 2008: i) for m identical machines, we give a 1.5-competitive online algorithm with a buffer of size 1.5m, which is better than the previous best result: 1.5-competitive algorithm with a buffer of size 1.6197m; ii) for three identical machines, to give an optimal online algorithm we reduce the size of the buffer from nine to six; iii) for m uniform machines, using a buffer of size m, we improve the competitive ratio from 2 +    to 2-1/m +   , where    > 0 is sufficiently small. ? 2012 Springer-Verlag.