One-operator two-machine flow shop scheduling with setup times for machines and total completion time objective

Date of Award


Publication Type

Master Thesis


Industrial and Manufacturing Systems Engineering



Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.


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.