GA/LP算法求解带组换装时间的单机调度问题

来源期刊：控制工程2010年第5期

论文作者：刘振刚 王道平

文章页码：710 - 713

关键词：单机调度;组换装时间;遗传算法;线性规划;

摘    要：以包头某钢铁线材企业实际调度问题为背景,针对带组换装时间的单机提前/拖期调度问题,建立了混合整数线性规划模型。根据模型的特点,将该问题的求解分为最优排序变量的确定和最优开工时间的确定两个层次。由于该问题是NP难的,提出了一种基于遗传算法和线性规划相结合的GA/LP算法。在算法中,利用GA在外层搜索遍历二元变量空间来优化工件排序;在内层则利用LP来确定满足约束条件的最优连续解。为了提高算法寻优性能,降低算法运行时间,提出了一种基于问题特征的种群初始化方法。最后,针对三种交叉算子在随机问题上进行了测试,实验结果表明,该算法能够有效求解问题。