Physical Sciences and Mathematics Commons^™

Scheduling Jobs On Two Uniform Parallel Machines To Minimize The Makespan, Sandhya Kodimala

UNLV Theses, Dissertations, Professional Papers, and Capstones

The problem of scheduling n independent jobs on m uniform parallel machines such that the total completion time is minimized is a NP-Hard problem. We propose several heuristic-based online algorithms for machines with different speeds called Q₂||C_max. To show the efficiency of the proposed online algorithms, we compute the optimal solution for Q₂||C_max using pseudo-polynomial algorithms based on dynamic programming method. The pseudo-polynomial algorithm has time complexity O (n T²) and can be run on reasonable time for small number of jobs and small processing times. This optimal offline algorithm is …

An Online Algorithm For The 2-Server Problem On The Line With Improved Competitiveness, Lucas Adam Bang

UNLV Theses, Dissertations, Professional Papers, and Capstones

In this thesis we present a randomized online algorithm for the 2-server problem on the line, named R-LINE (for Randomized Line). This algorithm achieves the lowest competitive ratio of any known randomized algorithm for the 2-server problem on the line.

The competitiveness of R-LINE is less than 1.901. This result provides a significant improvement over the previous known competitiveness of 155/78 (approximately 1.987), by Bartal, Chrobak, and Larmore, which was the first randomized algorithm for the 2-server problem one the line with competitiveness less than 2. Taking inspiration from this algorithm,we improve this result by utilizing ideas from T-theory, game …