多目标粒子群算法求解混合多处理机任务作业车间调度问题研究

摘要

混合多处理任务作业车间调度(Hybrid Job-shop Scheduling with Multiprocessor Task, HJSMT)是作业车间调度和多处理机任务调度的混合调度问题,即每个工件由多个工序组成且每个工序都需要一组机器同时进行加工.目前对HJSMT研究较少且集中于单目标问题,因此针对多目标HJSMT问题,本文以最小化最大完工时间和最小化总拖延时间为目标建立双目标HJSMT模型,提出一种新的改进多目标粒子群算法(IMOPSO)对其求解.该算法以IPOX交叉和多轮变异策略更新粒子;根据动态邻域思想设计新的外部种群寻优机制(EPOM)寻找每一代较优解,结合个体拥挤距离删减并维护外部种群.采用5-Job与10-Job两个算例分别进行仿真实验,结果表明IMOPSO算法在选取邻域粒子数量为2时求解效果最好,并且通过与NSGA-II算法进行对比,验证了IMOPSO的有效性.