论文部分内容阅读
随着市场经济的发展,企业间竞争日益激烈,如何更好的进行车间作业调度、优化资源配置、提高生产效率,成为生产企业能否取得竞争优势的关键因素之一。车间作业调度属于组合优化范畴,具有高复杂、动态随机和多约束等特性,被证明是典型的NP难问题,对它的研究具有重大的理论意义和现实意义。因此,已成为生产企业和广大学者的一个研究热点。一直以来人们提出了各种算法和程序来加以解决,其中分枝定界(branch-and-bound, BAB)算法是精确算法的重要手段之一,得到国内外学者的广泛重视。应用分枝定界算法虽然能求得最优解,但较慢的求解速度和需要较多的内存空间一直是这一研究的瓶颈。为了改善这类问题的BAB算法的性能,较快缩减组合搜索空间与优化问题搜索空间,本文运用约束规划(constraint programming, CP)方法和分枝定界相结合求解Job-Shop问题,从一个新的角度解决具有一般性与挑战性的Job-Shop调度问题。本文给出了车间作业调度问题的定义,分析了车间作业调度问题可行的研究状况及方向,介绍了车间调度问题的分类、特点和目前主要的调度算法。详细介绍了CP的调度模型和目前主流的约束推理方法。本文着重研究了车间作业调度问题中的Job-Shop调度问题,给出了问题的模型及BAB与CP相结合的算法。针对Job-Shop调度问题做了以下两方面的研究：1)改进了Carlier J 1990年提出的edge-finding算法,将其应用到需要同一台机器的任务集合中带有优先关系的情况。即结合工作间优先关系和工作可行时间窗口的约束传播算法,应用问题实例说明算法的约束传播效果。2)提出了将BAB与CP结合的算法,将CP技术应用到BAB的削减分枝过程,融合了分枝定界优化能力和约束规划处理复杂约束的能力。基于1994年Brucker只将input/output约束推理技术应用到BAB的算法,本文将input/output negation、input-or-output应用到BAB算法中。实验结果表明将3种约束推理按顺序input/output→input/output negation→input-or-output得到的优化效果最好。最后,指出了本文的不足及进一步的研究方向。