This paper explores selected heuristics methods, namely CDS, Palmer’s slope index, Gupta’s
algorithm, and concurrent heuristic algorithm for minimizing the makespan in permutation
flow shop scheduling problem. Its main scope is to explore how different instances sizes
impact on performance variability. The computational experiment includes 12 of available
benchmark data sets of 10 problems proposed by Taillard. The results are computed and
presented in the form of relative percentage deviation, while outputs of the NEH algorithm
were used as reference solutions for comparison purposes. Finally, pertinent findings are
commented.