约束满足混合算法求解并行机Job-Shop调度问题

Constraint satisfaction-based hybrid algorithm for Job-Shop scheduling problem with parallel machines

分析并行机Job-Shop调度问题的特点并建立其约束满足优化模型,结合约束满足与变邻域搜索技术设计了一个求解该问题的混合优化算法。该算法采用变量排序方法和值排序方法选择变量并赋值,利用回溯和约束传播消解资源冲突,生成初始可行调度,然后应用局部搜索技术增强收敛性,并通过结合问题特点设计的邻域结构的多样性提高求解质量。数据实验表明,提出的算法与其他两种算法相比,具有一定的可行性和有效性。

Analyzed the Job-Shop scheduling problem with parallel machines and established its constraint satisfaction optimization model.Proposed a hybrid optimization algorithm combined with constraint satisfaction and variable neighborhood search technique.In the algorithm,chosen a variable and assigned by variable ordering and value ordering method.Resolved resource conflicts using backtracking and obtained constraint propagation technology until a feasible schedule.Then the feasible schedule acted as an initial solution of the variable neighborhood search algorithm.Enhanced the convergence through local search technology and improved the quality of solution through the diversity of the designed neighborhood structures according to the characteristics of the problem.The feasibility and validity of the proposed hybrid method is demonstrated by the data experiment compared with the other two algorithms.