使用OptaPlanner解决多工序、多机台(资源)排程的新思路
在解决多工序联动、多机台共享的场景下排程过程中,常用同时把所有存在前后接续关系的任务,和存在共用特性的机台,一起建模成为规划变量(Planning Entity)与问题事实(Problem Fact),并一次性提供给引擎进行求解运算。但这种方法,因为双链(下文详述)特性的存在,规划问题过于复杂,导致问题规模过大,从而令引擎的搜索究竟指数级增大,进行各种性能改善后,仍难以获得满意解;甚至部分情况下规划运算所得结果还不如人工排程方案。
双链模型可简述如下:将工序路线上前后工序形成的任务链(下称工序任务链),与机台上的接续的任务形成的机台任务链(下称机台任务链)综合在一起。对每个任务的开始时间(前推式计划)或结束时间(后拉式计划)进行优化,以缩短整体时间(以提升效率作为优化目标)。下图是本人在一开始的排程项目中对双链规划问题的描述,在以往的文章,及向Geoffrey的求教过程中均以该图说明双链模型及其可能遇到的问题;有兴趣者可查看更早前的文章 。
上述方案是本人目前想到的最佳解决双链排程问题的办法,若验证后可行,将会分享更多细节。