Master of Science in Computer Science
First Committee Member
Second Committee Member
Ajoy K. Datta
Third Committee Member
Fourth Committee Member
Number of Pages
We present a new branch and bound algorithm for solving three machine permutation flow shop problem where the optimization criterion is the minimization of sum of completion times of all the jobs. The permutation flow shop problem (F||∑Ci ) belongs to the class of NP-hard problems; finding the optimal solution is thus expected to be highly computational. For each solution our scheme gives an approximation ratio and finds near optimal solutions. Computational results for up to 20 jobs are given for 3 machine flow shop problem when the objective is minimizing the sum of completion times. The thesis also discusses a number of related but easier flow shop problems where polynomial optimization algorithms exist.
Branch and bound algorithms; Combinatorial optimization; Permutations; Production scheduling; Scheduling
Kodimala, Swapna, "A Branch and Bound Method for Sum of Completion Permutation Flow Shop" (2014). UNLV Theses, Dissertations, Professional Papers, and Capstones. 2110.