An efficient local search for minimizing completion time variance in permutation flow shops

This paper illustrates that by exploiting the structure of hard combinatorial optimization problems, efficient local search schemes can be designed that guarantee performance in solution quality and computational time. A two-phase local search algorithm is developed and applied to the permutation flow shop scheduling problem, with the objective of minimizing the completion time variance. New and significant analytical insights necessary for effectively solving the permutation flow shop problem are also presented and used in this research. Computational results indicate that for test problems, the local search obtained optimal solutions for many instances, within few seconds of CPU time. For other benchmark problems with jobs between 50 and 100, the proposed algorithm, ADJ-Reduced improved the existing best known values within a practical time frame.