Quasi-Optimal Low-Complexity Algorithms for the Permutation Flowshop Problem with Weighted Tardiness Penalties

Abstract

The permutation flowshop scheduling problem (PFSP) with N jobs and M machines is NP-hard for M > 2. This paper considers a generalized objective combining a fixed penalty for each tardy job with a penalty proportional to tardiness, under job-specific release times and due dates. Existing heuristics such as NEHedd address the conventional proportional-tardiness objective and do not account for this penalty structure. We propose three low-complexity heuristics: (i) a Pareto-filtered insertion heuristic extending the NEH construction, (ii) a windowed near-exhaustive selection heuristic, and (iii) a hybrid that retains the better solution from the insertion heuristic and NEHedd. The methods are evaluated on 5,100 randomly generated instances spanning three job-to-machine ratios and three traffic intensities. The insertion heuristic achieves 7.2% lower average penalty than selection while running 16 times faster, and its advantage increases from 0.6% at low traffic to 12.5% at high traffic. Insertion achieves lower average penalties than NEHedd on all tested instance sizes under low traffic, and on smaller instances under medium and high traffic. The hybrid achieves over 10% penalty reduction compared to NEHedd for smaller instances, while the relative reduction decreases with increasing configuration size. Runtime analysis indicates polynomial scaling for insertion, with O((N M )b), 1.31 < b < 1.67.