【作者】 董兴业；

【导师】 黄厚宽；

【作者基本信息】 北京交通大学 ， 计算机应用技术， 2008， 博士

【摘要】 对于NP-完全问题,通常不能有效地求得问题的最优解,而是使用启发式算法在可接受的时间内找到问题的尽量好的解。车间调度(shop scheduling)问题具有约束性、非线性、多极小性、大规模性、多目标性等特点,一般属于NP-完全问题,目标解的搜索涉及解空间的组合爆炸。线性规划、分支定界等传统方法对于稍大规模的车间调度问题的求解无能为力,因此,通常使用启发式算法求解。车间调度是一个交叉性研究领域,吸引了运筹学、数学、管理学、决策学、自动化、计算机等领域的众多专家学者,同时,车间调度与控制技术是实现生产高效率、高柔性和高可靠性的关键,有效实用的调度方法和优化技术的研究与应用已成为先进制造技术的基础,因此研究求解车间调度问题的启发式算法有现实意义。本文研究了启发式算法在一类经典的车间调度问题——同顺序流水作业——中的应用,取得的主要研究成果如下:1.针对以最小化最大完工时间为目标的同顺序流水作业,在著名的NEH算法的基础上,提出了一个改进的构造性算法NEH-D。NEH-D算法主要从两点改进了NEH算法:首先使用一个更优的排序规则,在该规则中,不仅考虑了工件的总加工时间,而且考虑了这些加工时间的标准方差;其次,使用了一个消解插入冲突的策略。使用的优先规则有利于改进算法的性能;使用的消解插入冲突的策略对算法性能的改进起关键的作用。实验表明,NEH-D算法的性能优于NEH算法的性能,也优于最近提出的NEHKK算法和NEHKK1算法的性能;2.研究了求解目标为最小化最大完工时间的禁忌搜索算法的几个要素对算法性能的影响。结果表明提出的搜索策略对算法性能有较明显的影响,而提出的禁忌表结构、禁忌状态和不同的初始解对算法的性能没有明显的影响;3.针对以最小化总流程时间为目标的同顺序流水作业,提出了一个迭代局部搜索算法。该算法对初始解不是很敏感:当算法陷于局部极小时,需要对当前最优解做扰动并继续搜索,此时扰动强度对算法的性能有明显的影响。实验表明该算法的性能优于当前已有的算法,且该算法改进了90个基准问题中47个问题的当前最优解;4.针对求解最小化最大完工时间和总流程时间的多目标同顺序流水作业,提出了一个多目标局部搜索算法。针对两个目标,用现有的构造性算法牛成两个解,作为该算法的初始解,然后从这两个初始解出发,以贪婪的方式求出新的Pareto最优解集,持续改进Pareto前沿。选择新的Pareto解的条件是该解既不被原解支配,也不被产生原解的解支配,同时对某个目标改进最大。当所有的解都陷入局部极小时,扰动已得到的Pareto解集,然后从扰动后的解集出发重新搜索。初始解和选择新的Pareto解的方法对算法性能有显著的影响。在基准问题上,与文献中已有算法的比较结果表明提出的算法的总体性能更优,特别是对较大规模的问题,且此差异具有显著性。更多还原

【Abstract】 For NP-complete problems, global optimal solutions can not be found at a reasonable cost. These problems are usually solved by heuristic algorithms with the objective of finding a solution as good as possible in an acceptable time. Shop scheduling problems have many features, such as constraint, non-linear, large-scale, multi-objective, and usually NP-complete. Solving these problems often encounters combinatorial explosion. Traditional methods, such as linear programming and branch&bound, are not very useful to solve shop scheduling problems with a little large scale, and these problems are usually solved by heuristic algorithms.Shop scheduling is an interdisciplinary field and attracts many researchers from operations research, mathematics, management science, decision science, automation science and computer science, etc., and at the same time, shop scheduling and control are key techniques to realize high efficiency, high flexibility and high reliability of producing. The research and application of effective and practical scheduling methods and optimizing techniques have become the basis of advanced manufacturing technology. So, the research of heuristics for solving shop scheduling has practical sense.The application of heuristic algorithm in the permutation Howshop sequencing problem (a classic problem of shop scheduling) is studied in this paper, and the main results are as follows:1. As for the problem with makespan criterion, an improved constructive heuristic NEH-D is proposed, which is based on the famous NEH heuristic. The NEH-D heuristic improves the NEH in two aspects: firstly, the jobs are sorted by a more effective priority rule, in which the sum of processing times of a, job is considered, in addition to the standard deviation of these processing times; secondly, a tie-breaking strategy is presented in the constructing phase. The priority rule is beneficial to the improvement, while the strategy is the key point to the improvement. Experimental results show that the performance of the NEH-D is not only statistically significantly better than that of the NEH, but also statistically significantly better than that of the NEHKK and NEHKK1 heuristics proposed recently;2. As for the problem with makespan criterion, the effects of several components in tabu search algorithm are studied. The results show that the proposed search strategy has obvious effect on the performance of the algorithm, while the proposed tabu list structure, tabu status and different initial solution have little effect on it;3. As for the problem with total flowtime criterion, an iterated local search algorithm is proposed. The initial solution has little effect on the algorithm: when the algorithm is trapped into a local optimum, it needs to perturb the best-so-far solution and continue the searching process, while the perturbation strength has significant effect on the performance of the algorithm. Comparisons are carried out and the results show that the performance of the proposed ILS is statistically significantly better than that of those existing algorithms. It improves the best known solutions for 47 out of 90 benchmarks;4. A multi-objective local search algorithm (MOLS) is proposed for solving the problem with bi-objectives of makespan and total flowtime. The MOLS is to start from two initial solutions, which are constructed by existing heuristics with respect to both objectives, respectively; then to search new Pareto optimal solutions in a greedy way until the process is trapped into a local optimum. The conditions of choosing a new Pareto solution are that the solution is not dominated by the original solution and the solution from which the original solution was generated, and at the same time, the solution has minimal value with at least one of the two objectives. When all the Pareto optimal solutions are trapped into local optima, perturb the Pareto optimal solutions and restart the search process. The initial solutions and method of choosing new Pareto optimal solution have significant effect on the performance of the MOLS. The results of comparison with existing algorithms on benchmarks show that the MOLS performs better, especially for relatively large instances. The performance differences have statistical significance.更多还原