Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs

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.

Keywords:

• scheduling problem
• semi-online
• hierarchical constraint
• competitive ratio

2010 AMS Subject Classifications::

• 90B35
• 68M20
• 68R05

Acknowledgements

We wish to thank the referee for the valuable suggestions, which improved the readability of this paper. This research has been partially supported by NSFC (61300016,11101065) and ‘China Scholarship Council (CSC)’. G. Dósa acknowledges the financial support of the Hungarian State and the European Union under the TAMOP-4.2.2.A-11/1/ KONV-2012-0072, and his research is also supported in part by K-TET 10-1-2011-0115.