李亚志 朱 夏

(东南大学计算机科学与工程学院，南京211189)

(东南大学计算机网络与信息集成教育部重点实验室，南京211189)

无等待流水作业调度是实际生产调度环境中 一个重要的有约束组合优化问题，可描述为:n 个任务在m 台机器上按给定加工时间，顺序进行加工，且任务在加工过程中不能被中断.常见的优化目标有最小化最大完工时间［1-2］、总延迟［3］和总完工时间［4-6］等.其中，最小化总完工时间是实际应用中的重要指标，可促进资源的稳定有效利用、任务的快速周转以及制品库存的最小化.该问题在m≥2 时为NP-难问题［4］.

目前，通常采用元启发式和启发式算法求解该问题.元启发式算法包括声搜索算法［6］、离散粒子群算法［7］、基于可变邻域搜索的混合遗传算法［8］等.启发式算法可分为构造启发式算法和复合启发式算法.Rajendran 等［9］提出了2 种基于任务插入的构造启发式算法.Bertolissi［10］提出了1 种基于比较的构造启发式算法.Aldowaisan 等［4］基于置换策略提出了4 种复合启发式算法.Framinan 等［5］提出了1 种复合启发式算法(FNM).FNM 算法是目前用于求解最小化总完工时间的无等待流水作业调度问题的最新复合启发式算法.

元启发式算法随着任务数n 的增加，其运行时间会越来越长，难以适用于实时性要求高的大规模无等待流水作业调度问题.在启发式算法中，邻域结构的设计是提高算法性能的关键.鉴于此，本文构造了一个基于插入-分段的邻域结构，提出了一种基于插入-分段的复合启发式算……