Optimization Online


Semi-Online Scheduling on Two Uniform Machines with Known Optimum, Part II: Tight Upper Bounds

György Dósa(Dosagy***at***almos.vein.hu)
Armin Fügenschuh(fuegenschuh***at***hsu-hh.de)
Zhiyi Tan(tanzy***at***zju.edu.cn)
Zsolt Tuza(tuza***at***dcs.uni-pannon.hu)
Krzysztof Wesek(wesekk***at***hsu-hh.de)

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. Additionally, we implemented our algorithm and give some experimental results on its average performance. The algorithm applies the method of "safe sets", with the novel addition that the conditions are not required in a strict way but exceptions are accepted and handled with additional techniques.

Keywords: Scheduling, semi-online algorithm, makespan minimization, mixed-integer linear programming.

Category 1: Combinatorial Optimization (Approximation Algorithms )

Citation: Angewandte Mathematik und Optimierung Schriftenreihe / Applied Mathematics and Optimization Series AMOS#28(2015), Helmut Schmidt University / University of the Federal Armed Forces Hamburg, Germany

Download: [PDF]

Entry Submitted: 08/04/2015
Entry Accepted: 08/28/2015
Entry Last Modified: 08/04/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society