论文摘要
生产计划和调度处于计算机集成制造系统的核心位置,它向上对企业的经营战略决策层负责,向下对监控控制层发出控制指令,确保生产的有序进行,是CIMS成功实施与否的关键。生产调度问题关系着企业成本的控制和利益的最大化,对于促进我国的制造业走向全球化、信息化、集成化有着深远的影响。Flowshop调度是一个典型的调度问题,本文着重研究通过设计和改进智能优化算法来解决flow shop调度问题,并通过大量的仿真实验,验证了所提算法的可行性和有效性。对于以Makespan为目标的置换flow shop问题,引入了一种新的智能优化算法蛙跳算法,蛙跳算法融合了SCE (Shuffled Complex Evolution)算法和离散粒子群算法的优良思想,实现了全局的信息共享。针对蛙跳算法容易产生非法调度的问题,设计了一种新青蛙跳跃规则来改善基本蛙跳算法的算法性能,仿真实验表明改进的蛙跳算法比基本的蛙跳算法和遗传算法更加有效。对于加工时间不确定的flow shop调度问题,通过模糊数学的方法来描述加工时间的不确定性,在基本蛙跳算法的基础上,借鉴交换子和交换序的概念,提出了“交换序构造的初始位置随机机制”和“交换子的随机插入机制”这两种追踪策略。通过与遗传算法比较,仿真实验结果验证了改进蛙跳算法在解决具有不确定性加工时间的flow shop问题上的有效性。对于以总流经时间为目标的置换flow shop问题,提出了一种全新的遗传算法,异步遗传局部搜索算法AGA (Asynchronous Genetic Local Search Algorithm)。AGA包含三个阶段:在第一个阶段产生随机的初始种群,其中的一个解由构造型的启发式算法产生;在第二个阶段,种群内的个体两两配对,进行异步进化操作,其中运用了一个简单的交叉算子和一个加强的邻域搜索策略;在最后一个阶段,采用一个重启策略来防止算法陷入局部极小。仿真实验表明,AGA比一些经典的算法和两个最近提出的后启发式算法更加有效,同时对于90个Benchmark问题,AGA得到了89个目前已知的最优解,其中54个是由AGA最新得到的。