点击次数：

论文类型：期刊论文

发表时间：2016-02-25

发表刊物：运筹与管理

收录刊物：PKU、ISTIC、CSCD

卷号：25

期号：1

页面范围：35-45

ISSN号：1007-3221

关键字：加工时间可控 并行混合算法 多样性 收敛性 Pareto优化 controllable processing time parallel hybrid algorithm diversity proximity pareto optimization

摘要：针对单机环境最优化加权总完工时间问题，当工件加工时间可通过分配资源进行压缩时，研究对工件的加工次序和时间压缩量的优化，从而权衡调度性能目标和资源成本目标。调度性能目标为压缩后工件的加权总完工时间，资源成本目标为工件压缩量的线性函数。此问题复杂性已被证明为NP-hard，为弥补较少有研究从Pareto优化角度求解该问题有效前沿的不足，针对经典NSGA-II求解时易早熟收敛的特点，采用算法混合方式进行优化方法研究。融合归档式多目标模拟退火算法跳出局部极值的优势，启用外部存档策略提升种群的多样性，采用主从模式的并行结构提升求解效率。最后为检验优化方法的有效性，一方面通过对Benchmark 测试函数ZDT1-6的求解，表明混合算法对不同结构和形状目标函数兼具普适性和有效性；另一方面结合问题特点设计有效编码方式，针对随机生成算例进行求解。通过分析有效前沿收敛性和多样性，验证了所提方法对于优化加工时间可控单机加权总完工时间问题的有效性。