运筹与管理2016，Vol.25Issue(1)：35-45,11.DOI:10.12005/orms.2016.0005
加工时间可控单机加权总完工时间 Pareto 优化研究
Pareto Optimization for Single Machine Scheduling with Controllable Processing Time to Minimize Total Weighted Completion Times
摘要
Abstract
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 ZDT 1-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 .关键词
加工时间可控/并行混合算法/多样性/收敛性/Pareto优化Key words
controllable processing time/parallel hybrid algorithm/diversity/proximity/pareto optimization分类
信息技术与安全科学引用本文复制引用
王杜娟,刘锋,王建军,王延章..加工时间可控单机加权总完工时间 Pareto 优化研究[J].运筹与管理,2016,25(1):35-45,11.基金项目
国家自然科学基金项目（71501024；71502026；71271039；70902033）；教育部“新世纪优秀人才支持计划”项目（ NCET-13-0082）；中央高校基本科研业务费专项资金资助项目 （）
