加工时间可控单机加权总完工时间Pareto优化研究

Pareto Optimization for Single Machine Scheduling with Controllable Processing Time to Minimize Total Weighted Completion Times

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

For single machine scheduling problem minimizing total weighted completion time, when job＇ s pro- cessing time could be compressed by allocating extra resources, jobs＇ processing sequence and compression times are optimized simultaneously. Two in-conflicts objectives are concerned： schedule performance measured by compressed jobs＇ total weighted completion times, and resource cost measured by linear function of jobs＇ compression times. The problem has been proved to be NP -hard. In order to bridge the gap that this problem has rarely been solved from the perspective of Pareto optimization, we make use of algorithm hybridization to im- prove classic NSGA-II which tends to be pre-mature during evolution. In hybridized algorithm, Archived Multi- Objective Simulated Annealing（AMOSA） is integrated to jump out of local optimum, external archive is built up to enhance population diversity, and master/slave parallel structure is designed to improve solving efficiency. Fi- nally for verification purposes, first hybridized algorithm is used to solve Benchmark test functions ZDT1-6, and the results demonstrate that the proposed method is applicable and effective for test functions with various struc- tures and shapes. Second, problem features are utilized to design effective encoding scheme and correspondingly randomly generated problem instances are solved. The analysis of proximity and diversity of obtained Pareto front further verify the effectiveness of hybridized algorithm for solving single machine scheduling with controllable pro- cessing time to minimize total weighted completion times.