混合离散教与学算法求解复杂并行机调度问题

摘要：

针对制造行业中广泛存在的一类复杂并行机调度问题,即带到达时间、多工序、加工约束和序相关设置时间的并行机调度问题(Parallel machine scheduling problem with arrival time,multiple operations,process restraints and sequence-dependent setup times,PMSP_AMPS),建立问题的排序模型并提出一种混昆合离散教与学优化算法进行求解,优化目标为最小化最大完工时间.首先,根据标准教与学算法(Teaching-learning-based optimization,TLBO)中两阶段个体更新公式的特点,在保留每一阶段个体更新公式框架不变的前提下,对公式中具体改变实数个体或向量的每个核心操作均用所设计的排列操作进行替换,使其可直接在离散问题解空间中执行基于标准教与学算法机理的全局搜索,从而明显提高了原算法的全局搜索效率.其次,采用交换操作和插入操作构造了一种简洁有效地变邻域局部搜索,对全局搜索发现的优质解区域进行细致搜索,从而进一步增强了算法的性能.通过对不同测试问题的仿真实验和算法比较,验证了所提算法可有效求解PMSP_AMPS.

关键词：并行机调度、多工序、序相关设置时间、到达时间、离散教与学

所属期刊栏目：46

资助基金：国家自然科学基金;云南省自然科学基金项目

在线出版日期：2020-06-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共15页

页码：805-819