Master of Science (MS)
First Committee Member
Wolfgang . Bein
Second Committee Member
Laxmi . Gewali
Third Committee Member
Lawrence . Larmore
Fourth Committee Member
Zhiyong . Wang
Number of Pages
There is an increasing demand for a phenomenon that can manifest benefits gained from grouping similar jobs together and then scheduling these groups efficiently. Batching is the decision of whether or not to put the jobs into same group based on certain criteria. Batching plays a major role in job scheduling in Information Technology, traffic controlling systems, and goods-flow management. A list batching problem refers to batching a list of jobs in the same order or priority as given in the problem.
In this thesis we consider a one-machine list batching problem under weighted average completion. Given sequence of jobs are scheduled on single machine into distinct batches. Constraint is to batch these jobs into a fixed but arbitrary number ‘k’ of batches. Each batch can have any number of jobs (within the given list) grouped without changing the order of jobs. We call it a k-Batch problem. This is offline form of the batching problems, and is solved by reducing to a shortest path problem. We give an improved and faster version of the algorithm to solve k-Batch problem in O(n2) time.
University of Nevada, Las Vegas
Kapoor, Shradha, "Batching Problems with Constraints" (2019). UNLV Theses, Dissertations, Professional Papers, and Capstones. 3624.
IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/