APS排程:柔性化生产车间调度算法

2021年10月13日 25 次阅读      本文共1847字,预计阅读时间6分钟

柔性化生产车间调度问题的描述如下:

一个加工系统有 m 台机器,要加工 n种工件。每个工件包含一道或多道工序,工件的工序顺序是预先确定的;每道工序可以在多台不同的机床上加工,工序的加工时间随机床的性能不同而变化。调度目标是为每道工序选择最合适的机器、确定每台机器上各工件工序的最佳加工顺序及开工时间,使系统的某些性能指标达到最优。此外,在加工过程中还需满足以下约束条件:

( 1 ) 同一台机器同一时刻只能加工一个工件;

( 2 ) 同一工件的同一道工序在同一时刻只能被一台机器加工;

( 3 ) 每个工件的每道工序一旦开始加工不能中断;

( 4 ) 不同工件之间具有相同的优先级;

( 5 ) 不同工件的工序之间没有先后约束, 同一工件的工序之间有先后约束;

( 6 ) 所有工件在零时刻都可以被加工。

基于析取图论的分析算法
基于析取图论的分析算法

目前处理柔性化生产车间调度问题的常见算法包括禁忌搜索算法、遗传算法、以及TS+GA混合算法,混合算法在求解质量和求解效率上都比单一算法有明显改善。

禁忌搜索算法

禁忌搜索算法(Tabu Search或Taboo Search,简称TS算法)是一种全局性邻域搜索算法,模拟人类具有记忆功能的寻优特征。它通过局部邻域搜索机制和相应的禁忌准则来避免迂回搜索,并通过破禁水平来释放一些被禁忌的优良状态,进而保证多样化的有效探索,以最终实现全局优化。

简单TS算法的基本思想是:给定一个当前解(初始解)和一种邻域,然后在当前解的邻域中确定若干候选解;若最佳候选解对应的目标值优于“best so far”状态,则忽视其禁忌特性,用其替代当前解和“best so far”状态,并将相应的对象加入禁忌表,同时修改禁忌表中各对象的任期;若不存在上述候选解,则选择在候选解中选择非禁忌的最佳状态为新的当前解,而无视它与当前解的优劣,同时将相应的对象加入禁忌表,并修改禁忌表中各对象的任期;如此重复上述迭代搜索过程,直至满足停止准则。

简单禁忌搜索的算法步骤可描述如下:

(1)给定算法参数,随机产生初始解x,置禁忌表为空。

(2)判断算法终止条件是否满足?若是,则结束算法并输出优化结果;否则,继续以下步骤。

(3)利用当前解工的邻域函数产生其所有(或若干)邻域解,并从中确定若干候选解。

(4)对候选解判断藐视准则是否满足?若成立,则用满足藐视准则的最佳状态y替代x成为新的当前解,即x=y,并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象,同时用y替换“best so far”状态,然后转步骤6;否则,继续以下步骤。

(5)判断候选解对应的各对象的禁忌属性,选择候选解集中非禁忌对象对应的最佳状态为新的当前解,同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。

(6)转步骤(2)。

遗传算法

遗传算法(Genetic Algorithm, GA)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。

其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,不需要确定的规则就能自动获取和指导优化的搜索空间,自适应地调整搜索方向。

遗传算法以一种群体中的所有个体为对象,并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中,选择、交叉和变异构成了遗传算法的遗传操作;参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

遗传算法
遗传算法

遗传算法的基本运算过程如下: 

(1)初始化:设置进化代数计数器t=0,设置最大进化代数T,随机生成M个个体作为初始群体P(0)。 

(2)个体评价:计算群体P(t)中各个个体的适应度。

(3)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

(4)交叉运算:将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。

(5)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。

(6)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出,终止计算。

基于GA+TS的混合智能算法

综合禁忌搜索算法(TS)和遗传算法(GA)的优势,整合混合智能算法,混合算法在求解质量和求解效率上都比单一算法有明显改善。

基于GA+TS的混合智能算法
基于GA+TS的混合智能算法