黄　霞　叶春明　包晓晓

1(上海理工大学管理学院　上海 200093)2(江苏科技大学　江苏 张家港 215600)



作业车间调度问题的杂草优化算法求解

黄霞1,2叶春明1包晓晓1

1(上海理工大学管理学院上海 200093)2(江苏科技大学江苏 张家港 215600)

摘要针对作业车间调度问题JSP(Job-shop scheduling problem)，提出一种入侵式杂草优化算法。该算法中，子代以正态分布方式在父代个体周围扩散，兼顾全局搜索和局部搜索，并根据迭代次数不同对二者强度进行调节。通过典型算例进行仿真试验，并在反复实验中对算法参数进行修正。测试结果表明杂草算法求解作业车间调度问题的可行性和有效性，优于萤火虫算法和基本粒子群算法，是解决生产调度问题的一种有效方法。

关键词杂草优化算法作业车间调度问题最大完工时间

0引言

作业车间调度问题JSP是许多生产调度问题的简化模型，具有很多实际应用背景。作为一类满足任务配置和顺序约束要求的资源分配问题，JSP已被证明是最困难的约束组合优化问题和典型的NP-hard问题[1]。由于作业调度问题的复杂性，即使在规模较小时，当前要获得最优解仍是非常困难。它的求解难度远大于流水线调度问题，针对其算法的研究一直是学术界和工程界共同关注的重要课题。如何利用有限的资源，满足被加工任务的各种约束，并确定工件在相关设备上的加工顺序和时间，以保证所选择的性能指标最优，即研究如何有效地求解JSP，有着非常重要的理论意义和实用价值。……