Researches on the no-wait permutation flow shop earliness and tardiness scheduling problem

Given the same due date and no idle time in processes, a heuristic algorithm for the earliness and tardiness penalties scheduling problem in permutation flow shop is proposed. Firstly, the algorithm gets the relatively good sequence of the jobs according to the sorted sequence regulation of 7 jobs. And then, the NEH algorithm is used to get the optimized solutions. At last, the optimal solutions are achieved by comparing the neighborhood searching results for every solutions. In the middle scale and small scale problems, the extent of similarity between the solutions got by the heuristic algorithm and the optimal solutions is 99%. Meanwhile through testing the standard deviation of the large scale samples, it is shown that the stability of the solutions is very good. In large scale problems, the heuristic algorithm appears good optimized performances and its calculated results are better than those got by ILOG-constraint programming(CP) optimized engine.