题目：约束满足算法在制定生产计划调度中的应用研究

生产计划是生产管理中最关键的环节之一，随着市场竞争的日趋激烈，每个企业都在寻找好的生产与运作管理方案，以提高企业的生产、经营和管理效率，从而提高企业的核心竞争优势。而生产与运作管理的核心是生产作业调度问题能否高效地获得最（次）优解，因此研究生产作业调度问题具有很大的理论意义和现实意义。本文的研究重点为生产作业调度中具有代表性，也是最难的Job Shop作业调度，问题是具有NP-完全特性的约束满足问题。约束满足在解决这类问题时，最通用的方法是采用带回溯深度优先的搜索方法。在前人研究的基础上，提出一种更接近实际应用的基于“序”的约束满足算法。在“序”的框架下，构造相应的算法策略：约束一致性检查策略、变量/值的启发式排序，并设计带有“序”特点的回跳策略，保证在“序”的搜索下，碰到冲突时，搜索状态能回跳到产生冲突的搜索结点，同时，确保搜索的安全性，不会把更好的部分解忽略掉。设计一组实验数据，利用本文提出的方法求解，把结果和其它已有的约束满足方法比较，证明算法的可行性和有效性。最后，针对实际生产作业会遇到的情况，在原有的算法上加入松弛参数，让算法来解决一个构造的实际问题，检验算法解决实际问题的能力。约束满足算法和当前一些成功的启发性算法（如遗传算法，模拟退火等）相比，虽然有搜索效率低的特点，但由于其描述问题能力强，能灵活的解决实际问题中的一些突发事件等特点，并且随着搜索技术的逐渐提高，作为人工智能领域内通用高效的约束满足算法，也将会成为解决OR领域问题一种重要解决手段。