Scheduling jobs on two uniform parallel machines to minimize the makespan

Author

Sandhya Kodimala, University of Nevada, Las VegasFollow

Award Date

5-1-2013

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Wolfgang Bein

Second Committee Member

Ajoy K. Datta

Third Committee Member

Lawrence L. Larmore

Fourth Committee Member

Venkatesan Mutukumar

Number of Pages

54

Abstract

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 used to benchmark the efficiency of the proposed online algorithms.

Keywords

Completion time; Computer algorithms; Offline; Online; Online algorithms; Parallel computers; Parallel scheduling (Computer scheduling); Scheduling; Uniform parallel

Disciplines

Computer Sciences | Theory and Algorithms

File Format

pdf

Degree Grantor

University of Nevada, Las Vegas

Language

English

Repository Citation

Kodimala, Sandhya, "Scheduling jobs on two uniform parallel machines to minimize the makespan" (2013). UNLV Theses, Dissertations, Professional Papers, and Capstones. 1850.
http://dx.doi.org/10.34917/4478269

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/