大规模定制中顺序间歇过程批调度研究

间歇过程生产在大规模定制中占有重要地位,顺序间歇过程是一种常见的间歇过程,现有研究将顺序间歇过程调度分为需求分批与批次调度两步求解过程,忽略了它们之间相互制约、不可分割的内在联系,为了校正这种人为断裂,以获得真正意义上的最优化调度,提出了顺序间歇过程批调度问题.用α | β | γ法对顺序间歇过程批调度问题进行描述,给出了基本的作业属性、加工环境和批调度性能指标.针对基于完成时间的性能指标,提出了两个并行机间歇过程批调度问题,在分析了几个有用性质后,将两个问题分别等价为固定费用运输问题和非线性运输问题.     

基于轮盘赌编码和粒子群算法的并行机调度优化

将粒子群算法用于优化并行机调度问题,将遗传算法选择策略方法中的轮盘赌方法引入到编码方法中,提出了一种基于轮盘赌的粒子编码方法,用于表示并行机调度问题的解。通过对两个并行机算例的计算说明,基于轮盘赌编码方法的粒子群算法都能有效地对并行机调度问题进行优化。     

基于网络流的多并行机可中断开放车间调度算法

为提高开放车间的生产效率,研究了多并行机可中断开放车间调度问题,提出了基于网络流的调度算法.针对车间的特点,建立了以制造期最短为目标的整数规划模型,提出了工件有就绪时间约束时制造期下界的计算方法.采用网络流理论表示机器与工件间的分配关系和时间约束,建立了开放车间的网络流模型,将调度问题转换为最大流问题.引入最小负载优先和最大工作量优先两条启发式规则,设计了基于预流推进的最大流算法,并针对最大流算法中存在的局部优化问题,提出了最大流优化方法,得到机器资源的分配结果.在此基础上,建立了加工时间矩阵及减量集合,求得各机器上工件的加工顺序.使用两组随机数据对算法进行了实验,通过与制造期下界的对比,验证了算法的正确性.     

基于两阶段蚁群算法的带非等效并行机的作业车间调度

针对带非等效并行机的作业车间生产调度问题,以制造系统的生产成本、准时交货率等为目标,构建生产调度多目标模型。利用蚁群算法在求解复杂优化问题方面的优越性,建立调度问题与蚁群并行搜索的映射关系,将调度过程分成任务分派和任务排序两个阶段,每个阶段分别设计蚁群优化算法,并将两阶段寻优蚂蚁有机结合,构建一种具有继承关系的两阶段蚁群并行搜索算法,可以大大提高获得较优解的概率,并且压缩求解空间,快速获得较优解。通过均匀试验和统计分析确定算法的关键参数组合,将两阶段蚁群算法应用不同规模的8组算例。结果表明,无论是优化结果还是计算效率,两阶蚁群算法均优于改进的遗传算法。将所提出两阶段蚁群算法应用于实际车间的生产调度,减少了生产过程中工序间等待时间和缩短了产品交付周期。     

基于混合差分进化算法的并行机批处理调度问题研究

考虑到实际生产中产品多、批量小的特点,建立了一种带工艺约束的并行机批处理调度优化模型。为解决调度中的分批问题,提出了一种新的基于产品需求量的批量划分方案及批量染色体编码方式,采用两级差分进化算法来解决批量划分和批次调度问题;针对标准差分进化算法收敛速度慢、易出现早熟现象等问题,引入动态随机搜索和随机变异的局部搜索策略,以增强标准差分进化算法的局部搜索能力。测试算例及调度实例的仿真结果表明,该算法能有效地提高算法收敛速度,平衡其全局搜索和局部探索能力。     

基于免疫算法的生产调度现状与展望

为提高生产调度的效能,首先阐述了生产调度和免疫算法的概况,然后分类讨论了免疫算法在生产调度问题中的研究现状,最后分析了目前此类研究中存在的问题和不足,并探讨了基于免疫算法的生产调度问题进一步的研究方向.     

基于工件聚类的并行机调度算法及其应用

针对纺织生产广泛存在的带工件释放时间、以最小化总拖期工件数和总拖期时间为目标的大规模并行机调度问题,提出一种基于工件聚类的遗传算法。该算法将求解过程分为工件聚类和工件排序两个阶段。在工件聚类阶段,基于影响并行机调度性能的重要调度特征量,采用改进的模糊C-均值聚类方法将所有待上机工件分为多个聚类;在工件排序阶段,采用基于规则编码的遗传算法,优化各聚类内工件的加工顺序。数值计算结果及实际应用效果表明,所提出的算法适用于求解带工件释放时间的大规模并行机调度问题。     

调度策略在并行机调度仿真的应用

等同并行机调度对提高生产率有着重要意义,针对动态随机环境,运用调度策略建立仿真模型,等同并行机调度以最大化吞吐率和最小化延迟工件量为多目标函数,仿真模型用于一个7台等同并行机的装配车间,模型参数和实验数据来自于某大型装备制造企业当前车间,现行调度主要采取先入先出(FIFO)策略。通过最小化加工时间优先(SPT)和最早订单完成时间优先(EDD)等策略用于仿真模型并与现行策略对比,仿真结果显示,将调度策略用于动态随机系统对企业提高生产效率有显著优越性。     

并行机调度问题粒子群优化研究

采用粒子群算法优化并行机调度问题,提出了基于机器和粒子位置取整的粒子编码方法和基于工件和粒子位置次序的粒子编码方法,并给出了两种不同粒子编码方法所对应的粒子群算法的步骤.通过对两个并行机算例的计算说明,基于两种不同编码方法的粒子群算法都能有效地对并行机调度问题进行优化,其中,基于工件和粒子位置次序的粒子编码所对应粒子群算法的优化性能要好些.     

生产时间可变间歇过程的Petri网模型及其调度

讨论了生产时间可变的多产品间歇过程的最优调度问题,给出了间歇过程在复杂中间的无限存储策略、有限存储策略、无中间存储策略和混杂存储策略下p-时间Petri网模型的描述方法,进而给出了基于可行调度集和修正分枝界定的间歇过程最短生产时间的最优调度算法.该算法利用一间歇过程最短生产时间不大于另一间歇过程最短生产时间的条件,有效地限制了对解空间的搜索,进而改善了算法的计算性能.仿真算例表明了所述方法的有效性.     

基于粒子群算法的并行多机调度问题研究

将港口拖轮作业调度问题描述为一类带特殊工艺约束的并行多机调度问题,采用粒子群算法求解该类调度问题,提出了一种2维粒子表示方法,通过对粒子位置向量进行排序生成有效调度,并采用粒子位置向量多次交换的局部搜索方法来提高算法的搜索效率。最后,通过计算验证了混合粒子群算法的有效性。     

带特殊工艺约束的双目标并行多机调度问题研究

港口的拖轮调度过程是一类带特殊工艺约束的并行多机调度问题.采用基于进化策略的混合算法,设计了基于工件的编码方式,对次序杂交算子进行了扩展,设计了一种扩展“倒位”变异算子,并采用相邻不同基因多次交换的局部搜索方法.算法的设计自动满足了工艺约束,保证了种群的多样性.设计了最大完工时间和生产加工成本双目标评价函数,最后通过计算对混合算法进行了验证.     

基于双线性链表编码的并行机大规模调度遗传算法

面向并行机大规模调度问题,提出了一种以工件聚类作为初始染色体种群构成基础的遗传算法。算法首先采用改进的模糊C-均值聚类算法,按影响调度的工件重要特性指标,将工件进行聚类;然后采用基于双线性链表结构的编码方式,表示工件聚类在并行机上的生产次序及任务数量,并据此设计了相应的交叉和变异算子;最后进行了实验分析及实例应用,该算法可以在合理的计算时间内获得满意的优化质量。     

基于免疫遗传算法的工艺设计与调度集成

为实现工艺设计与调度的并行分布式集成，建立了工艺规程调度仿真优化的数学模型，确定了模型的决策空间、目标函数及约束条件。提出了一种协同进化免疫遗传算法，用以同时优化零件的备选工艺规程组合和调度方案，通过工艺种群及调度种群的相互促进，实现协同进化，依据抗体的亲和力及抗体浓度来保持群体的多样性，根据抗体的激励度来进行免疫选择，采用最优解保持策略，确保算法的收敛性，考虑编码特点，工艺抗体采用均匀交叉及随机扰动变异，而调度抗体采用均匀顺序交叉及倒位变异。通过对10台设备10种零件的实例仿真，验证了算法的有效性。     

同型机在线调度问题研究进展

为了阐明在线调度的概念及其与在线算法的关系,为相关研究提供支持,对同型机在线调度问题的研究现状进行综述。描述了同型机在线调度问题的概念,以加工约束和目标函数为标准,对同型机在线调度问题进行分类。从基本模型、允许拒绝工件以及考虑机器适用约束等角度对逐个调度工件类在线调度问题进行回顾,从极小化最大完工时间、极小化加权完工时间和以及极大化加权按期完工工件数等角度对工件随时问到达类在线调度问题进行总结,指出了现有研究的不足,并探讨了同型机在线调度问题的未来研究方向。     

基于增强学习的平行机调度研究

尝试运用增强学习方法来研究平行机调度问题,通过定义系统状态、行为和报酬函数,把调度问题转化为平均报酬型半马尔可夫决策过程,并使用结合函数泛化器的R-Learning算法来解决.提出排名算法,并利用它和两种常用的调度规则(最短期望加工时间规则和先进先出规则)来定义增强学习的行为.实验结果表明,R-Learning算法通过仿真实验学习较优的调度策略,在不同的决策状态下选择最优或次优的行为,对每个测试问题的效果都优于以上任何一条调度规则.     

知识化制造环境下模糊调度模型和算法

为解决实际生产中一些不精确调度知识的描述问题,通过引入模糊理论中的测度概念,建立了模糊调度模型和求解该模型的混合模糊遗传算法.首先,在变速并行机生产环境下,针对工件加工时间和交货期的不确定性,基于可能性测度和必然性测度的定义,提出了工件拖期可信度指标,用于衡量工件发生拖期的可能性;然后,基于工件拖期可信度指标,建立了以最小化工件平均拖期可信度为目标的混合整数规划模型,通过分析该调度模型,得到最优模糊调度的相关性质;最后,以上述工作为基础,给出一种混合模糊遗传算法的求解方法,并以某电机制造企业为例,对所提出的算法进行了有效性验证.     

基于JIT的并行多机问题的病毒进化遗传算法

为了解决提高顾客对完工时间满意度的提前/拖期调度问题,提出了一种将病毒进化遗传算法和单机问题的有效算法相结合的求解方法。在该方法中,病毒进化遗传算法采用整数编码,简化了算法的实现难度,提高了算法的执行效率。每个染色体都代表完成零件加工的机器编码的组合,通过病毒种群对主种群的病毒感染,提高了逃脱局部极点的搜索能力。在每一代种群中,调用单机问题的有效算法,使达到用户满意度的零件数最大。数值仿真实验表明,该算法具有收敛速度快、优化效果好等特点,且适合于求解大规模问题。     

基于遗传算法和模型仿真的调度规则决策方法

为了完成特定生产环境下的调度规则选择问题,提出一种将遗传算法和过程仿真相结合的调度规则求解方式。在该求解方式中,遗传算法采用分段整数编码,每个染色体都代表一组可用于描述具体调度方案的规则组合;遗传操作包括选择、交叉、变异三种类型;为获得适应度函数值,利用基于某扩展Petri网的生产过程模型进行仿真,以在每一代种群中,得到与每个染色体相对应的各项性能指标值,进而以一种集成层次分析法和方案模糊评判的决策优化方法求取相应的适应度函数值。另外,为了改善串行遗传算法不切实际的解答时间,用主从式并行遗传算法代替传统遗传算法,保证了解在时间上和质量上的可行性。