Date of Award


Publication Type

Master Thesis


Industrial and Manufacturing Systems Engineering




In a manufacturing environment, when a worker or a machine switches from one type of operation to another, a setup time may be required. I propose a scheduling model with one operator and two machines. In this problem, a single operator completes a set of jobs requiring operations in a two-machine flow shop. The operator can perform only one operation at a time. When one machine is in use, the other is idle. Whenever the operator changes machine, a setup time is required. We consider the objective of total completion time. I formulate the problem as a linear integer programming with ' O'('n'3) 0-1 variables and ' O'('n'2) constraints. I also introduce some classes of valid inequalities. To obtain the exact solutions, Branch-and-Bound, Cut-and-Branch, Branch-and-Cut algorithms are used. For larger size problems, some heuristic procedures are proposed and the computational results are compared.