【作者】 张维存；

【导师】 郑丕谔；

【作者基本信息】 天津大学 ， 管理科学与工程， 2007， 博士

【摘要】 柔性作业车间调度问题(FJSP)比传统作业车间调度问题的复杂性更高,其求解难度更大。本文利用蚁群和粒子群混合优化算法研究了柔性作业车间调度一类问题的求解方法,主要工作与创新点如下:1、研究了蚁群粒子群混合优化算法在单目标柔性作业车间调度问题中的应用。首先,根据FJSP的求解特点,建立了主-从两级协调的蚁群粒子群混合算法结构。然后,对于主级蚁群优化算法构建了工序可选加工设备吸取图模型,设计了蚂蚁的解构造图和蚂蚁在工序可选加工设备间的转移概率;对于从级粒子群优化算法,采用位置矩阵的粒子表示方法,以粒子元素向量中优先权值的次序表示作业车间调度问题(JSP)中工件调度的次序,并在此基础上设计优先权值向量的解码方法。最后,以实验方式分析了蚁群粒子群混合优化算法中主要参数的取值问题。2、研究了蚁群粒子群混合优化算法在能力约束和多目标柔性作业车间调度问题中的应用。针对上述两类柔性作业车间调度问题分别重新设计了蚁群优化算法中蚂蚁转移概率的局部启发式信息的计算和更新方式,使主级蚁群优化算法既能够在能力约束的柔性作业车间调度问题中处理能力约束条件,又能够在多目标柔性作业车间调度问题中实现设备总负荷和关键设备负荷最小两个优化目标。3、研究了蚁群粒子群优化算法在多模式资源受限项目调度问题(MRCPSP)中的应用。首先,根据MRCPSP的求解特点,建立了主-从两级协调的蚁群粒子群混合算法结构。然后,对于主级蚁群优化算法设计了蚂蚁在任务间游历的转移概率和蚂蚁在任务执行模式间游历的模式优选概率;对于从级粒子群优化算法,采用基于任务的粒子表示方法,以任务优先权值标示任务的执行次序,并在粒子的解码中设计了任务优选概率的优选规则。最后,选用项目调度标准问题库(PSPLIB)中的测例,以实验的方式对蚁群粒子群混合优化算法中的主要参数取值进行优化。更多还原

【Abstract】 Due to machine constraint, flexible job shop scheduling is much more complex than traditional job shop scheduling and even more difficult to be solved in view of optimization. In this dissertation, a hybrid of ant colony and particle swarm optimization algorithms is used to solve flexible scheduling problems such as flexible job shop scheduling. In this dissertation, the main work and innovations are as follows:1. Flexible job shop scheduling problems with single objective are studied using the hybrid of ant colony and particle swarm optimization algorithms. First, A hybrid of ant colony and particle swarm optimization algorithms with master-slave structure is proposed based on the characteristic of flexible job shop scheduling problems to be solved. Then, an ant solution construction graph is presented and the transfer probability of ant between machines which can be selected to process job based on the extract graph of job processing machines for the ant colony algorithm at the master level. While, at the slave level, a decoding method is designed for particle based on the sequence of priority number in particle position matrix. Finally, the value of primary parameters in the hybrid algorithm is analyzed by experiments.2. Capacity constrained and multi-objective flexible job shop scheduling problems are studied using the hybrid of ant colony and particle swarm optimization algorithm. The computing and updating method of local heuristic information in ant transfer probability is redesigned based on the characteristics of the problems above-mentioned. Therefore, not only the capacity constraints can be dealt with, but also the minimum of total machine load and bottle-neck machine load can be realized by the ant colony optimization algorithm at master level.3. The mutli-mode resource-constrained project scheduling problems are studied using the hybrid of ant colony and particle swarm optimization algorithm. First, A hybrid of ant colony and particle swarm optimization algorithm with master-slave structure is proposed based on the characteristic of mutli-mode resource-constrained project scheduling problems to be solved. Then, the transfer probabilities of ant between tasks and between task-modes which can be selected to perform task based on the extract graph of task performing models for the ant colony algorithm at the master level. While, at the slave level, a decoding method including task-selecting probability is designed for particle based on the sequence of priority number in particle position vector . Finally, the value of primary parameters in the hybrid algorithm is analyzed by experiments based on the examples of project scheduling problem library (PSPLIB).更多还原