摘要
The problem of minimizing the maximum lateness on a single machine with family setups is considered.To solve the problem, dominance property is studied and then introduced into the tabu search(TS) algorithm.With the dominance property, most unpromising neighbors can be excluded from the neighborhood, which makes the search process always focus on the most promising areas of the solution space.The proposed algorithms are tested both on the randomly generated problems and on the real-life problems.Computational results show that the proposed TS algorithm outperforms the best existing algorithm and can solve the real-life problems in about 1.3 on average.
The problem of minimizing the maximum lateness on a single machine with family setups is considered.To solve the problem, dominance property is studied and then introduced into the tabu search(TS) algorithm.With the dominance property, most unpromising neighbors can be excluded from the neighborhood, which makes the search process always focus on the most promising areas of the solution space.The proposed algorithms are tested both on the randomly generated problems and on the real-life problems.Computational results show that the proposed TS algorithm outperforms the best existing algorithm and can solve the real-life problems in about 1.3 on average.
基金
supported by the Major State Basic Research Development Program of China (973 Program)(2002CB312205)
the National Natural Science Foundation of China (60574077
60874071
60834004)
the National High Technology Research and Development Program of China (863 Program) (2007AA04Z102)