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 34

Indexed by:期刊论文

Date of Publication:2014-08-01

Journal:INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE

Included Journals:SCIE

Volume:25

Issue:5

Page Number:525-536

ISSN No.:0129-0541

Key Words:Online scheduling; competitive ratio; buffer

Abstract:In this paper we study an online minimum makespan scheduling problem with a reordering buffer. We obtain the following results: (i) for m > 51 identical machines, we give a 1.5-competitive online algorithm with a buffer of size inverted right perpendicular1.5minverted left perpendicular; (ii) for three identical machines, we give an optimal online algorithm with a buffer size six, better than the previous nine; (iii) for rn uniform machines, using a buffer of size m, we improve the competitive ratio from 2 + epsilon to 2 - 1/m + epsilon, where epsilon > 0 is sufficiently small and en is a constant.