基于杂交模型及逻辑分解算法的JSSP研究

Hybrid model and logic-based decomposition algorithms on JSSP

作业车间调度,是指为具体的任务(工序)安排生产资源(机器)并确定合理的加工顺序,是一个典型的NP-Hard问题,有着广泛的研究。首先介绍混合整数规划MIP和约束编程CP的互补优势。然后建立JobShop调度问题的MIP/CP杂交模型,并针对杂交模型的特点提出一种基于逻辑的分解算法。最后用几个实例证明了该模型及算法的求解速度。

The job shop scheduling problem （JSSP） is a typically hard non-polynomial problem （NP-Hard） and has been widely researched by scholars. Firstly, the complementary strengths of MIP and CP are applied to solve the problems that are intractable if hybrid model and logic based decomposit solving them using either of the two methods alone. Then the MIP/CP ion algorithms are put forward. Finally, some examples illustrate that the the model and algorithms are effective in combinational optimization.