A penalty-based heuristic algorithm for the permutation flowshop scheduling problem with sequence-dependent set-up times

This paper considers the permutation flowshop scheduling problem with sequence-dependent set-up times and develops a penalty-based heuristic algorithm to find an approximately minimum makespan schedule. The proposed algorithm determines the penalty in time associated with a particular sequence and selects the sequence with the minimum time penalty as the best heuristic solution. Computational results comparing the effectiveness and efficiency of the proposed penalty-based heuristic algorithm with an existing savings index heuristic algorithm are reported and discussed.