Tight upper bounds for semi-online scheduling on two uniform machines with known optimum
Open Access
- 14 June 2017
- journal article
- research article
- Published by Springer Nature in Central European Journal of Operations Research
- Vol. 26 (1) , 161-180
Abstract
We consider a semi-online version of the problem of scheduling a sequence of jobs of different lengths on two uniform machines with given speeds 1 and s. Jobs are revealed one by one (the assignment of a job has to be done before the next job is revealed), and the objective is to minimize the makespan. In the considered variant the optimal offline makespan is known in advance. The most studied question for this online-type problem is to determine the optimal competitive ratio, that is, the worst-case ratio of the solution given by an algorithm in comparison to the optimal offline solution. In this paper, we make a further step towards completing the answer to this question by determining the optimal competitive ratio for s between \(\frac{5 + \sqrt{241}}{12} \approx 1.7103\) and \(\sqrt{3} \approx 1.7321\), one of the intervals that were still open. Namely, we present and analyze a compound algorithm achieving the previously known lower bounds.
Keywords
Funding Information
- National Natural Science Foundation of China (11471286, 11271324)
- National Research, Development and Innovation Office – NKFIH (SNN 116095)
- VKSZ (12- 24 1-2013-0088)
This publication has 21 references indexed in Scilit:
- Semi-online scheduling problems on a small number of machinesJournal of Scheduling, 2013
- Geometric representation for semi on-line scheduling on uniform processorsOptimization Methods and Software, 2010
- Semi-online scheduling on two uniform processorsTheoretical Computer Science, 2008
- Semi on-line scheduling on three processors with known sum of the tasksJournal of Scheduling, 2007
- The On-Line Multiprocessor Scheduling Problem with Known Sum of the TasksJournal of Scheduling, 2004
- On-line bin-stretchingTheoretical Computer Science, 2001
- On-Line Load Balancing for Related MachinesJournal of Algorithms, 2000
- Better Bounds for Online SchedulingSIAM Journal on Computing, 1999
- Semi on-line algorithms for the partition problemOperations Research Letters, 1997
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969