Limited waiting time constraint restricts the maximal and minimal waiting times of a job between consecutive machines. This constraint widely exist in the manufacturing environment with transportation requirement and high production continuity due to the unstable physical or chemical nature of intermediate product. The permutation flowshop scheduling problem with rejection is a joint decision of job rejection and production scheduling, which is to determine rejected jobs and the schedule with accepted jobs. This joint decision problem is considered with the objective to minimize the sum of total rejection cost and total tardiness cost, and an upper bound is set for the makespan in this problem. A co-evolutionary genetic algorithm is presented, in which an encoding scheme is proposed to divide a chromosome into two subsets, respectively corresponding to job rejection and job sequencing. The initial population is produced by dispatching rules, and the co-evolutionary strategy is introduced into this algorithm to coevolve the two subset population. Moreover, a memory-based dynamic probability generation method is presented to determine the probabilities to run the genetic operators, and some decoding rules are set to ensure the feasibility of a solution and optimize its total cost. Computational experiments are carried out to verify the effectiveness of this algorithm, and the impact of problem parameters on the performance of this algorithm are also studied in the experiments.