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

Heuristic Algorithm Based on the Probabilistic Model of Search Space

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

According to a kind of typical constraint satisfaction problem-Job shop scheduling, the probabilistic model of the search space is presented. Based on three analytical factors-the operation start probability, individual demand probability of operation for machine and machine aggregate demand in the model, a new heuristic algorithm is built. The simulation result shows that this new algorithm obtains the optimal result of FT06 benchmark scheduling problem at the smaller time cost.