Award Date


Degree Type


Degree Name

Master of Science (MS)


Computer Science

First Committee Member

Wolfgang Bein

Number of Pages



A flow shop problem has n jobs (i = 1.. , n) on m machines (j = 1, . . . , m) and a job consists two operations and the jth operation of each job must be processed on machine j. Any job can start only on machine j if it is completed on machine j-1 and if machine j is free. Each operation has a known processing time pij. The work here focuses on the case m = 2 where the objective is to minimize (1) the makespan (Cmax) and (2) the average completion time (sumCi); We first review an efficient greedy algorithm by Johnson for Cmax and give detailed proofs; The we note that in the case of sumCi the problem is harder, in fact it is NP-hard. To tackle this problem we have implemented a branch and bound algorithm to find the optimal schedules in some cases. We also constructed a genetic algorithm under MIT's GALib C++ package. Solutions from the branch and bound algorithm are used as benchmarks for the solutions found by the genetic algorithm.


Flow; Machines; Scheduling; Shop

Controlled Subject

Computer science; Operations research

File Format


File Size

993.28 KB

Degree Grantor

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 and include clear identification of the work, preferably with URL.


IN COPYRIGHT. For more information about this rights statement, please visit