Algorithms to minimize completion time variance in a two machine flowshop

This paper presents algorithms to minimize the variance of completion time (CTV) when n jobs have to be processed on two machines. All the jobs visit the machines in the same order or technological sequence. These algorithms are applicable in manufacturing systems where both the facilities could be within the factory or situations where one facility represents the bottleneck machine within the shop floor while the other represents the subcontractor facility. The problem is also applicable in file handling systems where two individuals have to process files in a fixed sequence. The paper presents heuristic algorithms that identify the sequence of jobs that minimizes completion time variance. The solutions are compared with a lower bound and are found to give results in the range of 5–10% deviation from the lower bound. In addition, the simulated annealing algorithm developed in this paper gives the optimum solution for all the problems tested up to 11 jobs.