一种求解Job_Shop调度的变量排序启发算法

该文提出了搜索空间的概率模型,并以模型中的工序开工概率、工序对机床的独立需求概率和机床累计需求三个评价因子,构造了新的变量排序启发算法。仿真结果表明新算法在较小的计算时间代价下,显著提高了系统的搜索效率。

基于搜索空间概率模型的启发算法

针对一类典型的约束满足问题——Jobshop调度,提出了搜索空间的概率模型,并以模型中的工序开工概率、工序对机床的独立需求概率和机床累计需求3个分析要素,构造了新的启发算法。仿真结果表明该启发算法在较小的计算时间代价下,获得了FT06标准调度问题的最优解。

基于ParetoHeu和实例化失败统计的关联启发式方法

变量排序启发式是约束规划求解约束满足问题中的一项关键技术,对求解效率有着重要影响。为进一步提高基于关联的变量排序启发式方法CRBS对问题求解的效率和能力,提出了一种基于ParetoHeu和实例化失败统计的关联启发式PICRBS。PICRBS采用源于帕累托最优的启发式组合方式ParetoHeu,将CRBS与经典的通用启发式dom/wdeg进行结合,同时加入基于实例化失败次数的权值统计方法,为问题求解选择最有可能导致搜索发生回溯的变量。实验结果显示,针对多个问题实例,该方法在问题求解效率上高于CRBS和主流变量排序启发式。