计算机辅助车间作业计划研究

摘要

车间作业计划模块是企业ERP系统的关键部分，直接关系着企业的生产、经营和管理效率，有效的计划算法能最大限度地降低生产成本，增强市场竞争力。研究车间作业计划问题具有重大的理论意义和经济价值。　　单件车间作业计划问题是制造业共存的问题，属于典型的组合优化难题，难以用常规方法求解，近几年来各种智能计算方法逐渐被用来解决作业计划问题。遗传算法是模仿自然选择和遗传学机理的一种邻域搜索算法，具有对优化问题的弱依赖性、全局最优性、鲁棒性和隐含并行性等特点，被广泛应用于各种工程领域。但在解决单件车间作业计划问题时，仍存在一些局限。本文研究应用遗传算法求解单件车间作业计划问题，主要在以下几个方面作了一些研究工作：　　1.探讨了单件车间作业计划问题的数学模型，优化目标和启发式算法。讨论了遗传算法的思想、基本组成、理论基础以及与传统搜索算法的比较优势。2.提出一种求解单件车间作业计划问题的简单遗传算法。在分析大量不可行解的产生原因和特征基础上，设计了新的染色体编码方法及相应的遗传算子。新编码方法实现了工序、机器、时间距阵的耦合，兼有基于工序和基于工件两种编码方法的优点，该算法可以避免产生不可行作业计划。3.为克服简单遗传算法容易早熟和收敛速度慢的缺陷，在简单遗传算法基础上提出一种改进的混合遗传算法。混合遗传算法在产生初始种群时引入启发式方法，采用自适应遗传参数和交替使用两种交叉算子；在搜索方式中加入模拟退火机制，采用只对部分优秀染色体进行退火操作的新策略，这样在保证增强寻优能力的情况下尽量减少运算量。4.编制了启发式算法，简单遗传算法，混合遗传算法的可视化算法程序，利用不同规模的典型问题对各种算法进行了仿真测试，测试结果表明简单遗传算法有比启发式算法更好寻优性能；改进的混合遗传算法与简单遗传算法相比，其寻优能力更强，收敛速度更快。

目录

文摘

英文文摘

致谢

第一章绪论

1.1课题研究的意义

1.2车间作业计划问题概述

1.3国内外研究状况

1.4课题背景和研究内容

1.4.1课题背景

1.4.2主要研究内容

第二章单件车间作业计划问题的理论模型

2.1问题的描述及数学模型

2.1.1问题描述

2.1.2问题的数学模型

2.1.3文中符号及其意义

2.2 Job Shop问题的计算复杂度分析

2.3 Job Shop的典型性能指标

2.4 Job Shop问题的析取图表示

2.5不可行排序分析及其判断方法

第三章一般的n/m/J/Cmax问题启发式算法

3.1三种作业计划与正规性指标

3.2活动作业计划和无延迟作业计划的生成方法

3.2.1活动作业计划的构成步骤

3.2.2无延迟作业计划的构成步骤

3.3基于优先分配规则的启发式算法

第四章遗传算法的基本原理

4.1遗传算法的基本组成

4.2遗传算法原理分析

4.3遗传算法的优势

4.4 Job Shop编码方法的评价原则

第五章单件车间作业计划的简单遗传算法设计

5.1常用编码方式及其性能分析

5.1.1基于完成时间的编码

5.1.2基于工件的编码

5.1.3基于工序的编码

5.2编码方法

5.2.1编码

5.2.2解码

5.3初始种群

5.4适应度函数

5.5选择算子

5.6交叉算子

5.7变异算子

5.8进化停止准则

5.9遗传参数的选择

5.9.1种群规模

5.9.2交叉概率

5.9.3变异概率

5.10程序编制与实例仿真

5.10.1遗传算法程序结构

5.10.2程序的数据结构

5.11测试结果分析

第六章单件车间作业计划的混合遗传算法求解

6.1初始种群的产生方法改进

6.2遗传算子的参数改进

6.2.1选择算子的改造

6.2.2自适应交叉、变异概率

6.3交叉算子的加强

6.4混合遗传算法的构造

6.4.1模拟退火算法的工作原理

6.4.2混合遗传算法流程

6.5测试结果

结论与展望

参考文献