Award Date

1-1-2006

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

First Committee Member

Wolfgang Bein

Number of Pages

70

Abstract

Batching problems are machine scheduling problems, where a set of jobs with given processing requirements has to be scheduled on a single machine. The set of jobs has to be partitioned into subsets to form a sequence of batches. A batch combines jobs to run jointly, and each job's completion time is defined to be the completion time of the entire batch. For a batching problem, it is also assumed that when each batch is scheduled, it requires a setup time. One seeks to find a schedule that minimizes the total weighted completion time; This problem is NP-complete, but the problem can be solved efficiently in O(n log (n)) time if the order of the jobs is given. This is accomplished through a non-trivial reduction to on-line matrix searching in a totally monotone array. An implementation of this algorithm is part of the thesis work; To remove the requirement of a fixed order and thus to solve the original NP-complete batching problem, the space of permutations is searched using a genetic algorithm technique. The implementation uses a library of object-oriented functions, GAlib, to implement genetic algorithms. This highly versatile library was written by Mathew Wall of MIT; The thesis also seeks to find techniques to obtain an upper bound, which can be used to measure the quality of the solutions found by the heuristic.

Keywords

Average; Batching; Completion; Heuristics; Jobs; Time; Under; Weighted

Controlled Subject

Computer science

File Format

pdf

File Size

1423.36 KB

Degree Grantor

University of Nevada, Las Vegas

Language

English

Permissions

If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to digitalscholarship@unlv.edu and include clear identification of the work, preferably with URL.

Rights

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

Download


COinS