Hits:

Indexed by:Journal Papers

Date of Publication:2015-05-04

Journal:INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS

Included Journals:SCIE、EI

Volume:92

Issue:5

Page Number:873-881

ISSN No.:0020-7160

Key Words:90B35; 68M20; 68R05; scheduling problem; hierarchical constraint; competitive ratio; semi-online

Abstract:In this paper, we consider three versions of semi-online hierarchical scheduling problems on two identical machines, with the purpose of minimizing the makespan. In the first version, we assume that the total size of jobs with lower hierarchy is given and we get the tight bound . In the second one, assume that the total size of jobs in each hierarchy is given and we get the tight bound . In the third one, we assume that the total size of jobs with lower hierarchy is known in advance and a buffer of size K is given to store at most K jobs temporarily. We propose an optimal algorithm with competitive ratio using K=1 and show that a bigger buffer size is not helpful.