This paper investigates the permutation flowshop scheduling problem subject to maximum and minimum time lag constraints with the objective of minimizing the makespan, a decision problem challenge frequently encountered in many manufacturing environments. This problem is known to be NP-hard, and a number of constructive heuristics have been proposed in the literature. By leveraging two problem-specific properties (i.e. reversibility and critical path), we propose four new constructive heuristics. The comprehensive computational evaluation carried out demonstrates that the proposed heuristics significantly outperform the existing ones in both solution quality and efficiency.