题名 | 复杂Job Shop调度问题的遗传算法研究及其应用 |
作者 | 张龙 |
学位类别 | 工学博士 |
答辩日期 | 2007-06-08 |
授予单位 | 中国科学院研究生院 |
授予地点 | 中国科学院自动化研究所 |
导师 | 裘聿皇 ; 刘民 |
关键词 | 制造过程调度 Job shop 分解 遗传算法 模糊 Manufacturing process scheduling problem Job shop Decomposition Genetic algorithm Fuzzy |
其他题名 | Research on Genetic Algorithms for Complex Job Shop Scheduling Problems and Their Applications |
学位专业 | 控制理论与控制工程 |
中文摘要 | 制造过程调度是先进制造和自动化领域中前沿性研究方向。本文在国家973计划项目及国家自然科学基金项目等支持下,面向实际制造过程,研究适合求解复杂Job shop调度问题的遗传算法。 本论文的主要研究工作如下: 1)为了克服常用的基于操作编码的遗传算法在求解较大规模Job shop调度问题的缺点,提出了一种基于问题分解的自适应混合遗传算法。基于所定义的调度特征量—资源冲突程度,所有操作被动态划分为两部分,并分别采用不同的方法进行调度。另外,构造了一类模糊逻辑控制器来自适应调节染色体编码的长度,以减少算法搜索空间,提高算法性能。 2)针对较大规模具有局部交货期的Job shop调度问题,提出了一种基于问题特征的遗传算法。其中,在交叉及变异算子中使用了操作加工开始时间的区间约束特征。 3)针对大规模Job shop调度问题,提出一种基于预测机制的自适应分解优化算法。在求解过程中,将大规模调度问题动态迭代分解为多个优化子问题,并采用所提的遗传算法进行求解。其中,预测信息用于对优化子问题进行自适应调整及遗传算法中染色体的解码。 4)针对具有模糊加工时间的Job shop调度问题,提出一种基于模糊数逼近的混合遗传算法。首先,针对用于描述工件加工时间的具有不规则隶属函数的模糊数,采用规则的分段梯形模糊数逼近,并给出了逼近误差。进一步,基于上述模糊数逼近方法,提出一种大规模模糊数综合方法,包括模糊数求和,取大及比较运算。并分析了基于上述逼近方法实现模糊数求和与取大的运算误差及计算复杂度。 数值计算结果表明了上述算法的有效性。另外,部分算法采用来自实际汽车制造过程中的数据进行了验证。 |
英文摘要 | Research on manufacturing process scheduling problem is a front research direction in advanced manufacturing and automation fields. Facing the practical manufacturing process, this dissertation studies the genetic algorithms for the complex Job shop scheduling problem with the support of the National Basic Research Program of China (973 Program) and the National Natural Science Foundation of China. This dissertation includes the following main contents. 1)In order to overcome the defect of the GA with operation-based representation for solving larger scale Job shop scheduling problem, we propose a self-adaptive hybrid genetic algorithm based on the problem decomposition. On the basis of the defined scheduling characteristic—resource conflicting degree, all operations of the scheduling problem are dynamically divided into two parts, each of which is scheduled by means of different scheduling policies. Additionally, a fuzzy logic controller (FLC) is constructed to adjust adaptively the length of the chromosome so that the search space of the proposed GA could be reduced and the performance of the GA could be improved. 2)For larger scale Job shop scheduling problem with partial due date, we propose a new GA based on the problem characteristic, in which the characteristic of the time constraints is adopted in the crossover and mutation operations. 3)For the large scale Job shop scheduling problem, we propose a kind of self-adaptive decomposition algorithm based on prediction. The scheduling problem is dynamically decomposed into some optimization sub-problems, which are solved by means of the proposed GA. In the proposed algorithm, we determine the optimization sub-problems and decode the chromosomes based on the prediction information, respectively. 4)For the Job shop scheduling problem with fuzzy processing time, we propose a kind of hybrid genetic algorithm based on the approximation of the fuzzy number. First, we use a kind of regular piecewise trapezoid fuzzy number to approximate the irregular piecewise linear fuzzy number for formulating the uncertain processing time of the job, and give the approximation distance under certain conditions. Then, based on the above approximation, we give a new kind of fuzzy number integration method including the addition, the max and the comparison methods of the irregular piecewise linear fuzzy numbers. Additionally, we analyze the computation errors and computation complexity of the proposed addition and max methods, respectively. The numerical computational results reveal that the above algorithms are effective. Additionally, we validate the above partial algorithms using the data from the practical automobile manufacturing process. |
语种 | 中文 |
其他标识符 | 200218014603182 |
内容类型 | 学位论文 |
源URL | [http://ir.ia.ac.cn/handle/173211/6011] ![]() |
专题 | 毕业生_博士学位论文 |
推荐引用方式 GB/T 7714 | 张龙. 复杂Job Shop调度问题的遗传算法研究及其应用[D]. 中国科学院自动化研究所. 中国科学院研究生院. 2007. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论