机械工程学报

作者：赵诗奎

单位：济南大学机械工程学院 济南 250022

关键词：作业车间调度,禁忌搜索算法,路径重连,无延迟调度,最大完工时间；

基金：国家自然科学基金资助项目（51775240）

针对作业车间调度问题（Job shop scheduling problem，JSP），以优化最大完工时间为目标，提出一种路径重连和禁忌搜索混合算法。结合JSP领域知识设计路径重连，分别将正向无延迟调度解和反向无延迟调度解作为导向解。在正向无延迟和反向无延迟调度甘特图中，每一道工序的左边与右边分别无可用空闲时间。提出基于当前解工序头长度的正向无延迟调度转化算法，以及反转工件工艺路线，基于当前解工序尾长度的反向无延迟调度转化算法。设计新的基于精英解的回溯禁忌搜索算法，能够充分利用迭代过程中的历史解信息。不但提取更新的当前最优解加入到精英解集合，而且当最优解连续不更新代数达到设定值时，提取区间代数内较好的当前解加入到精英解集合。实现精英解池的不断补充和动态更新，使得算法可以持续进行回溯搜索。采用移动范围更广的邻域结构进行搜索，将路径重连与禁忌搜索算法混合，对JSP问题基准算例进行测试，验证了所提算法的有效性。

来源：2021年第14期

《机械工程学报》期刊编辑部

查看机械工程学报杂志2021年第14期