论文部分内容阅读
单元制造系统是高效的生产制造系统,可将成组技术灵活应用于批量生产环境。单元制造生产环境下的流水制造单元调度是无资源约束的机器调度优化问题,在医药生产、金属冶炼和食品加工等流程式企业的生产调度环境中有着广泛应用。该类问题的调度优化,可有控制生产过程,缩短生产企业的作业加工时间、缩短在制品库存时间、提高产品质量。多机的流水作业调度问题已经被证明是NP难问题。最优化算法由于具有指数时间复杂度而只适用于中小规模实例。因此,对于大规模实例,通常采用启发式或元启发式方法在合理时间求解。论文对几个典型流水制造单元调度优化问题进行深入研究,主要工作如下：(1)单目标的无等待流水制造单元调度。针对无等待流水制造单元调度问题,以最小化总完工时间为优化目标,提出基于插入-分段优化的无等待流水调度复合启发式算法；通过研究目标增量的性质并在分析现有启发式算法的邻域搜索特点基础上,提出基于插入-分段邻域结构的调度框架；采用迭代对换算法获得更高调度质量的排列。实验结果表明,所提出的算法性能稳定、实时性高。(2)单目标带SDFSTs约束的流水制造单元调度。针对带SDFSTs约束的流水制造单元调度问题,以最小化最大完工时间为优化目标,提出一个基于和声搜索的混合和声搜索算法：分析在单元制造生产环境下流水作业调度的特点,采用两层流水作业调度策略；应用RZ和PE优化算子,使得迭代优化算法获得更高调度质量的排列；提出一个简单实用的最差解丢弃方案,避免算法陷入早熟和局部收敛。实验结果表明,所提出的算法能有效提高解的质量,可应用于实时性要求不高的生产环境中。(3)多目标的流水制造单元调度。针对带SDFSTs约束的流水制造单元调度问题,以最小化总延迟时间和平均总完工时间为优化目标,提出一个基于和声搜索的双目标混合和声搜索算法；根据问题特点采用两层流水作业调度策略,在迭代优化算法中应用RZ优化算子,使得算法求得更高质量的解；为避免算法陷入早熟和局部收敛,采用交叉算子对解执行变异操作,使算法能够跳出局部最优解的搜索区域,扩大解的搜索范围。实验结果表明,所提出的算法能够得到高质量Pareto解。(4)单目标的跨单元流水制造单元调度。针对带SDFSTs约束的跨单元流水制造单元调度问题,以最小化最大完工时间为优化目标,提出一个复合启发式算法和两个元启发式算法;复合启发式算法采用NEH算法思想求得候选解,应用局部优化策略提高解的质量,直到不能进一步优化为止：在两个元启发式算法,即混合和声搜索算法和混合遗传算法中,引入局部优化策略,可获得高调度质量的排列。实验结果表明,复合启发式算法的执行效率高,混合遗传算法得到的解的质量好。