Job Shop系统任务分配与能力规划耦合优化问题—应用并行遗传算法

摘要

生产系统的任务分配问题和能力规划问题作为两个单独的子问题，已经得到广泛的研究。其中，任务分配问题是指在零件加工路线已知的基础上对系统中各个加工中心的生产任务进行合理分配，使得加工中心之间满足负荷平衡要求；能力规划问题是指合理安排加工中心机器数量以满足生产成本要求。目前为止，这两个问题都是作为相互独立的子问题展开研究。也就是说，解决任务分配问题时，通常假设能力规划的结果已知；同样的，能力规划问题的研究也是建立在任务分配的结果已知的基础上的。然而，实际情况中，生产系统任务分配问题和能力规划问题之间相互耦合。在给加工中心分配生产任务的同时，需要调节加工中心生产设备数量，以便顺利完成该加工任务；同样，在决定加工中心的生产设备数量时，需要根据生产成本约束来调节加工中心的生产任务。 不同于已有的工作，本文在排队网络的基础上，对相互耦合的散件加工型制造系统（Job Shop）任务分配问题和能力规划问题展开并行研究。分别以开环散件加工型制造系统（Open Job Shop，OJS）和闭环散件加工型制造系统（Closed Job Shop， CJS）为例展开分析，建立上述两类系统的数学模型。其中任务分配问题的优化目标是使得各个加工中心负荷平衡；能力规划问题的优化目标是使得在生产率满足一定要求的前提下生产成本最小。本文应用排队网络理论计算两个优化问题的性能指标，提出一种并行遗传算法（Concurrent Genetic Algorithm，CGA）来解决上述耦合优化问题，并且通过数值实验验证了此算法的有效性。 本文的主要研究成果如下： 1．建立了开环和闭环Job Shop型制造系统任务分配问题和能力规划问题的耦合优化模型。 利用排队理论分析法，建立了开环和闭环Job Shop系统任务分配问题和能力规划问题的数学模型。这里，一个问题（任务分配问题或能力规划问题）的决策变量都是另一个问题目标函数或约束条件中的参数，从而形成耦合。由于这两个优化目标的相互冲突，二者难以同时达到最优，为此以获得二者的满意性能为目标，建立弱化的耦合优化模型。 2．并行遗传算法的提出。该方法简单易实现，简化了多个优化目标的并行优化过程。 在遗传算法的基础上，利用可以将不同优化问题的决策变量编码到同一条染色体的编码思想，让一条染色体的一个完整进化过程包含多个子遗传算法。每个优化目标对应一个子遗传算法，它们并行运行。通过适应度函数的构造来控制优化方向，其中考虑了每个优化问题的决策变量对多个目标函数的影响。 3．进行了数值试验，验证了这一并行遗传算法的有效性。 4．在VC6．0下完成了Job Shop任务分配与能力规划并行优化应用程序开发，实现了并行遗传算法。

目录

文摘

英文文摘

声明

第一章 绪论

1.1 研究背景

1.1.1 研究对象的选择

1.1.2 问题的提出及基本概念

1.1.3 耦合关系分析及多目标并行优化概念

1.2 国内外研究现状

1.2.1 任务分配问题

1.2.2 能力规划问题

1.2.3 排队网络

1.3 本论文的工作

1.3.1 建模及并行算法

1.3.2 算例分析

1.3.3 算法实现

第二章 开环Job Shop系统仿真建模及并行算法

2.1 总体建模思想

2.1.1 系统假设

2.2 变量定义

2.3 基于排队网络的开环Job Shop型制造系统模型

2.3.1 任务分配问题

2.3.2 能力规划问题

2.3.3 耦合关系分析

2.4 问题转化和并行性分析

2.4.1 问题转化

2.4.2 并行性分析

2.5 遗传算法基本概念

2.5.1 遗传算法的特点

2.5.2 遗传算法的基本操作

2.6 并行遗传算法

2.6.1 算法定义

2.6.2 染色体的进化过程

第三章 闭环Job Shop系统仿真建模及并行算法

3.1 基于排队网络的闭环Job Shop型制造系统模型

3.1.1 任务分配问题

3.1.2 能力规划问题

3.1.3 耦合关系分析

3.2 问题转化和并行性分析

3.2.1 问题转化

3.2.2 并行性分析

3.3 并行遗传算法

第四章 多目标并行遗传算法算例分析

4.1 开环Job Shop算例分析

4.1.1 四个加工中心开环Job Shop

4.1.2 十个加工中心开环Job Shop

4.2 闭环Job Shop算例分析

4.2.1 四个加工中心闭环Job Shop

4.2.2 二十个加工中心闭环Job Shop

4.3 结论

第五章 Job Shop任务分配与能力规划并行遗传算法的实现

5.1 算法目的

5.2 并行优化应用程序开发

5.2.1 界面定义

5.2.2 具体实现

5.2.3 算法运行结果

第六章 结论与展望

6.1 论文的主要工作与结论

6.2 工作展望

致谢

参考文献

发表论文列表