Sevast'yanov's algorithm for the flow-shop scheduling problem

We consider the flow-shop scheduling problem. The objective is to schedule the jobs on the machines so that we minimize the time by which all jobs are completed. We studied and implemented different versions of the algorithm of Sevast'yanov based on linear programming to solve this problem. Using CPLEX, we did computational tests with random instances having up to 1000 jobs and 100 machines. If the size of the flow-shop scheduling problem is small or if the running time is not a critical factor, the Nawaz–Enscore–Ham approximation algorithm still performs better. But if the running time is an important factor, Sevast'yanov's algorithm can be a very good alternative especially in presence of very large scale instances with a relatively small number of machines.