返回

生产调度机理模型

模型

发布时间:2019/08/28 20:03

标签:

摘要:对制造型企业来说效率是生产的关键。而合理的调度有利于提高生产效率。生产调度,即对生产过程进行作业计划,作为一个关键模块,是整个先进生产制造系统实现管理技术、运筹技术、优化技术、自动化与计算机技术发展的核心。

生产调度机理模型

对制造型企业来说效率是生产的关键。而合理的调度有利于提高生产效率。生产调度,即对生产过程进行作业计划,作为一个关键模块,是整个先进生产制造系统实现管理技术、运筹技术、优化技术、自动化与计算机技术发展的核心。

生产调度将某项生产制造工作,在尽可能满足约束条件(如工艺路线、资源情况、交货期)的前提下,通过下达生产指令,安排其组成部分所使用的资源、加工时间及加工的先后顺序,以获得产品制造时间或成本等的最优化。生产调度包括两个方面,一是加工设备和工件的排序,二是确定各工序的开始以及结束加工时间。随着柔性生产模式的发展,研究生产调度问题对制造企业的意义更大。良好的作业调度有利于企业维持生产力的稳定、提高设备的利用率、缩短产品生产周期等。

有效的调度方法和优化技术的研究与应用,是实现先进制造和提高生产效益的基础和关键,其研究主要可分为建模和调度算法设计两方面。通常,可以用来表示任意一个调度问题,表示机器的加工环境,表示工件的加工特性,表示加工性能指标。常见的车间调度问题有作业车间调度问题、流水车间调度调度问题和柔性车间调度问题等,主要研究n 个工件在m 台机器上的加工过程,通常是特殊的开环调度问题。求解调度问题的方法统称为调度优化算法,它可区分为精确求解方法和近似求解方法。其中精确求解方法包括解析方法、穷举方法、分支界定等;近似求解方法包括基于规则等构造方法、领域搜索方法等。

传统的优化目标是单个,例如,设备利用率最低、订单总体完成时间最短等等,但是越来越多的场景需要实现多目标优化。多目标优化是存在多个管理目标时,在给定区域、约束上的最优化管理。多个目标间往往存在相互协调或者相互竞争、矛盾的关系,因此许多研究致力于寻求全局最优解。

多目标优化主要解决方法是化多为少的方法,即把多目标化为比较容易求解的单目标或双目标,如主要目标法、线性加权法、理想点法等,以及分层序列法和层次分析法。目前针对多目标优化方法的研究也有较多是基于智能算法的数学模型,如基于帕累托( Pareto ) 方法的多目标进化算法( Multi-objective Evolutionary Algorithms,MOEAs ),包括遗传算法( Genetic Algorithm,MOGA )、非支配排序遗传算法( Non-dominated Sorting in Genetic Algorithm-II ,NSGA-II )、粒子群优化算法(Particle Swarm Optimization,PSO)等。

遗传算法是最为流行的一类进化算法,它利用交叉(crossover)和变异(mutation)算子来产生新解。遗传算法的最大优势在于它的通用性,即它既可以解决连续多目标优化问题,又可以解决组合多目标优化问题。例如当决策变量为实数编码时,它可以采用模拟二进制交叉与多项式变异;当决策变量为二进制编码时,它可以采用单点交叉与随机翻转变异;当决策变量为序列编码时,它可以采用次序交叉与随机插入变异。此外对于一些有着复杂编码的优化问题,研究者也可以为遗传算法设计出特定的交叉和变异算子。一般来说遗传算法在不同问题上的综合性能较为稳定。

非支配排序遗传算法(NSGA-II),在应用NSGA-II算法解决实际问题时,首先设定种群的参数:最大的进化代数Genmax,种群规模Pop-size,交叉概率Pc,变异概率Pm;考虑到约束条件时,还需要说明决策变量的上下限,目标函数的个数。

计算过程开始时,首先初始化产生初始种群,然后该种群通过进化操作产生子代种群,紧接着再将亲子两代种群合并成规模为2N 的种群Rn。接下来对种群Rn中的个体进行非劣等级的排序,非劣排序的目的就是将子代与父代种群混合在一起,对于种群中染色优劣的程度,用适应度函数来评价。通过这一过程,完成亲代与子代个体非劣的检验,在对个体进行非劣检验的同时,就开始对种群中的个体进行非劣排序,根据其排序的序值,依次将第一等级、第二等级、……第n 等级依次填充到下一代种群Pn+1,每填充一次,检查Pn+1中的种群规模是否超过N;如果没超过,则继续填充,但是,如果将第m 个非劣等级中的个体填充进去后,Pn+1中的个体数超过N 时,则用密度估计的方法选择m 等级分布性较好的个体填入其中,使得Pn+1的个体规模恰好为N。

粒子群算法(particle swarm optimization)通过模拟鸟类的飞行行为来更新种群,其中每个解的下一次更新方向受到惯性、历史最优位置以及全局最优位置的共同影响。这种让所有解向着最优位置更新的机制使得粒子群算法具有较快的收敛速度;但反过来,它在多峰问题上容易陷入局部最优。粒子群算法通常只用于求解连续多目标优化问题;通过将组合问题连续化,一些工作也将它应用于求解组合多目标优化问题。

标准PSO算法计算步骤:

(1)任意赋予粒子群中粒子的最初位置以及速度,并初始设定种群的大小、迭代多少次、约束条件、停止条件等;

(2)计算每个粒子的适应值;

(3)把所有粒子的适应值逐个与个体极值进行对比。若适应值更好,就用该适应值替代相应的个体极值;

(4)把所有粒子的适应值逐个与全局的极值进行对比,若适应值更好,则用该适应值替代当前全局极值;

(5)根据公式计算确定每个粒子的位置和飞行速度;

(6)如果没有达到预设的停止准则(通常设置为最大迭代次数),则返回步骤2,若达到则停止计算。