Master of Science (MS)
First Committee Member
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
Computer science; Operations research
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.
Adusumilli, V. L. Kumar, "Flow shop scheduling with two machines" (2005). UNLV Retrospective Theses & Dissertations. 2018.