论文部分内容阅读
随着市场竞争的日趋激烈，每个企业都在寻求最佳的生产与运作管理方案，以提高企业的生产、经营和管理效率，从而提高企业的核心竞争优势。调度是影响制造业生产效率的关键因素。合理调度可以缩短制造期、减少库存、按时交货。生产调度问题种类繁多，方法多样，其中车间作业调度问题（Job Shop SchedulingProblem, JSSP）是著名的机器调度问题，同时也是困难的NP-hard组合优化问题之一。人们为解决这一难题已经付出几十年的努力，但至今在求解质量和计算效率上都还不能令人满意。在对车间作业调度问题的研究过程中，产生了大量确定性算法和启发式算法。尤其是近二十多年来，通过模拟自然界中生物进化、物理变化和人类行为过程而开发的元启发式算法，如遗传算法、模拟退火算法、粒子群优化算法、蚁群优化算法等，为解决调度问题提供了新的手段，引起了国内外学者广泛的兴趣。但按照Wolpert等提出的“优化问题没有免费的午餐”理论，任何算法不能保证在所有问题或一类问题的所有实例上都产生比其它算法好的结果。这样，在算法研究中就不能追求优于其它算法的最好算法，而是应该将需要解决问题的自身特征一并纳入研究范围，根据不同问题设计不同的算法。文化基因算法就是这样的一种算法框架，在算法环节中既包含种群中个体间的信息交换，也包含基于问题特征的局部搜索，为不同类型的调度问题研究提供了一条新的思路。本文在对用文化基因算法解决车间作业调度问题的各个环节进行深入分析研究的基础之上，提出了适用于最小化制造期、最小化总加权拖期时间和同时优化多个目标的车间作业调度问题的文化基因算法。主要研究工作如下：①用文化基因算法解决车间作业调度问题首先要设计算法的各个环节。本文分析了基于工序的编码和二进制编码两种典型的调度问题表示方法。定义了调度问题解空间的欧氏距离，并以此为工具对文化基因算法解决调度问题过程中包含的解码方法、进化操作、进化模式等关键环节进行深入研究。②提出了一种新的种群进化模式。这种进化模式中的交叉过程和变异过程对相应的操作方法执行多次，然后选择产生个体中的最优者进入下一代，以保证父代个体的优良特征得到较好地继承。将交叉过程和变异过程并列，并在交叉过程中嵌入随机变异，父代个体必须经过交叉或者变异才能进入下一代种群，避免直接拷贝父代个体导致算法收敛到局部最优。与简单遗传算法的对比分析表明，该进化模式能够让子代个体较好地继承父代特征，且保持较广的搜索范围。③针对最小化制造期车间作业调度问题，在对常见的基于关键路径和关键工序块的调度问题邻域结构分析的基础上，为最小化制造期问题选定合适的邻域结构。将提出的进化模式和采用最速下降控制策略的爬山法局部搜索相结合，组成文化基因算法。对经典测试问题的数值实验表明，该算法在计算效果上与其它主流算法相比具有一定优势。④对于计算难度更大、优化指标和工期相关的最小化总加权拖期时间车间作业调度问题，本文分析研究了已有邻域结构的移动操作定义模式，提出了三种新的邻域结构。将这些邻域结构与已有邻域结构进行对比分析，以此为基础设计文化基因算法，并通过数值实验验证算法的有效性。⑤对于多目标车间作业调度问题，提出一种基于精英保留策略的多目标文化基因算法。研究了多目标优化领域中主流算法的设计理念，提出在进化过程和局部搜索中嵌入精英保留策略的多目标文化基因调度算法。对拥有两个和三个优化目标的车间作业调度问题的数值实验表明，所提算法计算效果好于经典的NSGAII算法，得到的计算结果好于经典文献给出的结果。⑥本着理论联系实际的原则，本文在理论研究的基础上，结合企业实际需求，将研究成果应用于具体的生产管理系统，对生产任务进行调度，生成生产作业计划，为科学组织生产活动提供依据。