Abstract:In the permutation flowshop scheduling problem with limited waiting time constraints, the waiting time of each
job between two consecutive machines is restricted by some upper bound. Based on the deep discussion of the duration time between two adjacent jobs in one job permutation and the relations of its upper and lower bound, a heuristic algorithm is proposed. In the algorithm, a travelling salesman problem(TSP) concerning the duration times is built to obtain an initial schedule, and then an extended inserting method is presented for the further optimization. To measure algorithm performance, an approach to calculate a lower bound of the problem is proposed. Numerical results show effectiveness and feasibility of this heuristic algorithm.