Master of Science (MS)
First Committee Member
Number of Pages
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.
Average; Batching; Completion; Heuristics; Jobs; Time; Under; Weighted
University of Nevada, Las Vegas
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 firstname.lastname@example.org and include clear identification of the work, preferably with URL.
Raymond, Lewis A, "Heuristics for batching jobs under weighted average completion time" (2006). UNLV Retrospective Theses & Dissertations. 1972.