车间混合作业调度问题计算复杂性及算法收敛效率研究

发布时间：2024-03-14 03:21

　　本文在国内外相关研究的基础上,针对车间混合作业调度(MSP)问题进行了相关研究,涉及到模型建立、计算复杂性分析、算法实现、算法性能分析及验证等多方面的问题。 首先,由于MSP问题规模庞大、系统复杂,为了表达MSP问题内部的多层阶结构网络关系,本文利用网络理论对MSP问题建立了多级赋权图模型,对其进行了清晰的描述。 进而,对制造系统MSP问题的计算复杂性进行了分析,本文对其中包含的各种作业方式的计算复杂性分别进行了研究,并利用复杂性理论中归约和转换的思想,引入背包问题着重研究了其中两种作业方式的计算复杂性,最后表明MSP问题属于NP-hard问题,计算复杂度为指数级或阶乘级,不可能找到可以精确求得最优解的多项式时间算法。 然后,研究了遗传算法在解决MSP问题中的应用过程,并对遗传算法的收敛性能进行了讨论分析。本文提出了一种十进制整数和实数相结合的编码方案,并针对这种编码方式实施了具体的遗传操作,使得交叉操作不失继承性,变异操作能够实现种群的多样性;利用马尔科夫链(Markov)理论相关知识证明了所设计遗传算法以概率1收敛到全局最优,并对算法的收敛速度进行了分析,指出各参数取值不同时对算法...

【文章页数】：74 页

【学位级别】：硕士

【部分图文】：

图2.1车间HFSP调度简图

-13-图2.1车间HFSP调度简图JSP和FSP都是研究在m台机器上n个工件的加工过程，如果各个工件技术约束条件相同，一个JSP问题就会转化为一个较为简单的FSP问题，进而，如果各机器上各工件的加工次序也相同，那么问题就可以进一步转化为置换FSP问题。通常情况下，JSP....

图2.2MSP多级赋权图模型

2.4车间混合作业调度系统建模2.4.1模型建立研究制造系统MSP建模方法，对推动MSP调度方法在制造企业中的应用，开发新一代的企业生产管理控制系统，提高我国制造企业对市场需求的响应速度以及制造系统的运行效率，把我国建设成为管理水平先进的制造业基地具有重要的意义。对于制造系统M....

图3.2n个工件3阶段4台机器作业实例排序描述

∈jTiS∈证明过程如下：123maxH/m=1,m=1,m=2/C问题的判定形式有解的必要充分条件是背包问题。首先来证明问题的充分性：如果背包问题有解，则可以构造一个排序问题123max/m=1,m=1,m=2/C的实例，即工件总数为n=t+2；工件n1J的....

图3.3、n个工件4个阶段5台机器实例排序描述

工件nJ排在最后加工（如上图3.3），否则就会产生空闲时间，其他零件的安排亦如上图3.3所示。对于问题的必要性，可以用反证法来证明。若背包问题无解，则∑=≠0∈abciSi，那么对于每一个ST，都有加工顺序n1J，{}JiSi/∈，{}JiTSi/∈

本文编号：3927983