基于多规则设备分配及工序排序的FJSP多目标集成优化方法

为降低柔性作业车间调度多目标优化的复杂度,提高优化效率,提出一种基于多规则设备分配及工序排序的柔性作业车间调度多目标集成优化方法.建立了一类以完工时间、设备最大负荷、设备总负荷以及制造成本为优化目标的柔性作业车间调度多目标优化模型;针对模型的组合爆炸特点,为降低其复杂度,提出一种将多规则设备分配及工序排序相结合的集成调度思想;为进一步提高求解效率,提出一种面向对象数据处理技术用于处理各实体之间的数据交换;基于改进的非支配排序遗传算法思想,提出了基于多规则设备分配及上序排序的柔性作业车间调度多目标集成优化算法.通过仿真对比与应用验证了所提方法的有效性.     

柔性工作车间调度问题的多目标优化方法研究

针对各工件日标不同的多目标柔性作业车间调度问题,构建了以加工成本、加工质量及制造工期为目标函数的柔性作业车间调度多日标优化数学模型.针对传统的加权系数遗传算法不能很好地解决柔性作业车间调度多目标优化问题,提出采用改进的强度Pareto进化算法,对柔性作业车间调度问题进行多目标优化,从而得出柔性车间调度问题的Pareto综合最优解.最后,结合项目实施,以某大型空分装备企业的车间调度为例,证明了文中提出的方法能很好地解决柔性工作车间调度的多目标优化问题.     

免疫算法求解多目标柔性作业车间调度研究

研究了多目标柔性作业车间调度问题,优化了设备分派方案。建立了多目标柔性作业车间调度的数学模型。提出了双种群双倍体自适应免疫算法,并用该算法求解某航空制造企业的多目标柔性作业车间调度问题,得到了优化调度方案。仿真结果表明,双种群双倍体自适应免疫算法是求解多目标柔性作业车间调度问题的有效算法。     

基于改进非支配排序遗传算法的多目标柔性作业车间调度

采用多目标进化算法解决具有工件释放时间、工件目标差异的柔性作业车间调度问题。依据实际制造系统中存在较多的最大完工时间、平均流经时间、总拖期时间、机器总负荷、瓶颈机器负荷和生产成本性能指标,建立多目标柔性作业车间调度模型。针对柔性作业车间调度问题的特点,设计一种扩展的基于工序的编码及其主动调度的解码机制,以及初始解产生机制和有效的交叉、变异操作;针对非支配排序遗传算法(Non-dominated sorting genetic algorithm II,NSGA-II)在非支配解排序和精英选择策略方面的不足,设计一种改进的非支配排序遗传算法,应用改进的算法求解柔性作业车间调度问题得到一组Pareto解集,并运用层次分析法选出最优妥协解。通过测试基准和模拟实际生产的实例,验证提出算法的可行性和有效性。     

基于Pareto优化的离散自由搜索算法求解多目标柔性作业车间调度问题

针对多目标柔性作业车间调度问题搜索空间的离散性和求解算法的收敛性,提出一种基于Pareto优化的离散自由搜索算法来求解多目标柔性作业车间调度问题。在建立基于Markov链数学模型的基础上,证明了算法以概率1收敛;引入首达最优解期望时间来分析算法收敛速度,并分析了算法时间复杂度。采用基于工序排序和机器分配的个体表达方式,在多目标柔性作业车间离散域,利用自由搜索算法在邻域小步幅精确搜索和在全局空间大步幅勘测进行寻优;通过自由搜索算法自适应赋予个体各异辨别能力和Pareto优化概念来比较个体优劣性,不仅保留优化个体,而且使个体寻优方向沿多目标柔性作业车间调度问题Pareto前沿逼近。通过对搜索过程中产生的伪调度方案进行可行性判定,以确保调度方案可行。采用10×10FJSP和8×8FJSP问题的实例进行寻优测试,验证了所提算法的可行性和有效性。     

考虑工件移动和成本的多目标柔性作业车间调度问题优化研究

针对考虑工件移动时间约束的柔性作业车间调度问题,构建了以加工总成本和最大加工时间最小为目标的数学模型并用改进遗传算法求解。针对柔性作业车间调度问题(FJSP)特性,算法中采用基于工序的集成编码操作,实现工序排序和机器匹配的内在关联并由此产生可行的调度方案;根据编码结构设计了有效的交叉和变异操作,从而避免了非法调度解的出现;为克服遗传算法的早熟收敛和减少调度开销,用贪婪解码算法生成主动调度、设计了自适应变异规则并采用混合子代产生模式提高染色体适应值。最后通过测试问题的求解及数值分析,证明了算法和模型的有效性及鲁棒性。     

考虑批量装配的柔性作业车间调度问题研究

柔性作业车间调度是生产调度领域中的一个重要组合优化问题,由于取消了工序与加工设备的唯一性对应关系,因而相较于作业车间调度问题,具有更高的复杂度。针对该问题在批量装配方面的不足,考虑将批量因素与装配环节同时集成到柔性作业车间调度问题当中。以成品件的完工时间为优化目标,对该批量装配柔性作业车间调度问题进行了数学建模。针对该模型,提出一种多层编码结构的粒子群算法,并对该算法的各个模块进行了设计。最后,以实例验证了该数学模型的正确性及算法的有效性。     

基于混合遗传算法的柔性作业车间调度研究

为更有效地求解柔性作业车间调度问题,提出一种混合遗传算法(蚁群-遗传算法)。在分层法的基础上,首先采用蚁群算法解决工艺路线选择问题,再通过遗传算法解决传统的作业车间调度问题。在混合遗传算法求解过程中,不断地在前期优化中获取调度知识,用于指导后期的优化过程。通过标准案例测试,验证了混合遗传算法对于解决柔性作业车间调度问题的有效性。     

复杂制造环境下的改进非支配排序遗传算法

针对柔性作业车间多目标调度问题,在考虑机器、操作人员等资源约束和交货日期不确定性的基础上,构建了以加工成本、客户满意度及生产总流程时间为目标函数的模糊调度数学模型。针对传统的加权系数方法不能很好地解决柔性作业车间调度多目标优化问题的缺点,提出改进的非支配排序遗传算法,采用改进的拥挤密度排序法改善同一非劣等级内个体的排序;提出自适应交叉和变异策略,克服了种群早熟化,改善了算法的收敛速度;采用改进精英策略保持种群多样性,改善了算法的搜索性能。将该算法应用于某机械公司的人机双资源多目标柔性车间模糊调度,仿真结果证明了该方法的有效性和可行性。     

柔性作业车间机床与搬运机器人联合调度方法

针对当前柔性作业车间机床和搬运机器人单独调度存在的不匹配问题,以车间完工时间为目标,提出基于多代竞争强进化遗传算法的机床与机器人联合调度方法。对多工件、多工序、多机床、多机器人的柔性作业车间联合调度问题进行了描述;考虑了机床生产和机器人搬运的时序约束,建立了最小化车间完工时间的优化模型;使用工序链、机床链及机器人链缠绕的染色体编码方式,将联合调度问题转化为算法优化问题;在遗传算法中引入多代竞争机理和强进化算子,其中多代竞争机理增加了优秀染色体的遗传概率,强进化算子具有保留优秀基因片段和强制差基因进化的能力。经生产实验验证,在15个工件44道工序的调度中,该算法的车间完工时间比标准遗传算法缩短了14.75%;另外,在不同规模的工件生产调度中,与克隆选择算法和标准遗传算法相比,该算法的迭代次数最少、车间完工时间最短。上述实验结果充分证明了多代竞争强进化遗传算法在柔性作业车间生产联合调度中的优越性。     

多目标柔性作业车间调度优化研究

提出了一种集成权重系数变化法和小生境技术的混合遗传算法,建立了包括时间、成本、交货期满意度和设备利用率在内的多目标优化模型。采用基于工序的编码方式和“间隙挤压法”活动化解码方法;遗传算子包括选择、交叉、变异3种类型;选择操作采用轮盘赌选择方式。为了保证解的收敛性和多样性,采用了精英保留策略和小生境技术。交叉操作采用线性次序交叉方式;变异操作采用互换操作变异方法。染色体的适应度是各个目标函数的随机加权和。仿真实验证明,提出的混合遗传算法可以有效解决柔性作业车间多目标调度优化问题。     

Developing two multi-objective evolutionary algorithms for the multi-objective flexible job shop scheduling problem

The aim of this paper is to study multi-objective flexible job shop scheduling problem (MOFJSP). Flexible job shop scheduling problem is a modified version of job shop scheduling problem (JSP) in which an operation is allowed to be processed by any machine from a given set of capable machines. The objectives that are considered in this study are makespan, critical machine work load, and total work load of machines. In the literature of the MOFJSP, since this problem is known as an NP-hard problem, most of the studies have developed metaheuristic algorithms to solve it. Most of them have integrated their objective functions and used an integrated single-objective metaheuristic algorithm though. In this study, two new version of multi-objective evolutionary algorithms including non-dominated sorting genetic algorithm and non-dominated ranking genetic algorithm are adapted for MOFJSP. These algorithms use new multi-objective Pareto-based modules instead of multi-criteria concepts to guide their process. Another contribution of this paper is introducing of famous metrics of the multi-objective evaluation to literature of the MOFJSP. A new measure is also proposed. Finally, through using numerous test problems, calculating a number of measures, performing different statistical tests, and plotting different types of figures, it is shown that proposed algorithms are at least as good as literature’s algorithm.     

存在多设备工序的综合调度算法

针对工序集中存在需要多台设备协同完成加工的多设备工序的综合调度问题,提出一种把多设备工序设计成在多个相关设备上同时加工的多个虚拟工序的方法。该算法把产品加工树转化为多设备工序被设计成虚拟工序组的虚拟加工工艺树,为了优先调度虚拟工序组,将虚拟加工工艺树分解为以虚拟工序组为根结点的子树和剩余标准工序组成的子树,优先调度以虚拟工序组为根结点的子树;当以虚拟工序组为根结点的子树不唯一时,按子树上虚拟工序组个数多少确定子树的调度次序;对每个以虚拟工序组为根结点的子树,优先调度虚拟工序组个数较多的路径上工序;为了使相关虚拟工序同时开始加工,提出虚拟工序动态调整策略。理论分析和实例表明,所提出的调度算法能够较好地解决存在多设备工序的综合调度问题。     

具有柔性加工路径的作业车间批量调度优化研究

古典作业车间调度问题已经被研究了几十年并证明为 NP- hard问题。柔性作业车间调度是古典作业车间调度问题的扩展 ,它允许工序可以由一个机床集合中的多台机床完成加工 ,调度的目的是将工序分配给各机床 ,并对各机床上的工序进行排序以使完成所有工序的时间最小化。本文采用遗传算法进行柔性作业车间调度研究 ,针对柔性作业车间问题提出了一种新颖直观的基因编码方法以适用于批量调度 ,并分析了几种批量调度方案 ,最后给出了这些调度的仿真结果 ,证明单件最佳调度不适合扩展成批量最佳调度     

考虑多目标的工艺规划与调度集成问题研究

针对工艺规划与调度集成问题在多目标优化方面的不足,考虑将多目标优化集成到工艺规划与调度集成问题中。以最长完工时间、加工成本及设备最大负载为优化目标,对该多目标工艺规划与调度集成问题进行建模,并提出了一种非支配排序遗传算法,鉴于加工信息的多样性,使用多层结构表示可行解,对该算法的选择及遗传操作等步骤进行了设计。最后,以实例验证了上述模型的正确性及算法的有效性。     

多目标柔性作业车间调度决策精选机制研究

针对多目标柔性作业车间调度优化无法找到唯一最优解的问题，提出多目标遗传算法和层次分析法模糊综合评判的分阶段优化策略。提出优化阶段和精选阶段的优化任务，优化阶段选出一组Pareto解集，精选阶段从Pareto解集中选出最优解；在精选阶段运用层次分析法和模糊评判集成的策略精选调度决策。决策算例证明提出的方法是可行的，可很好地帮助决策者选择出一个最满意的解。     

多工艺路线多资源多目标的作业调度优化

针对多工艺路线多加工资源多目标的作业调度问题,提出了一种启发式活动调度算法,将该方法与多目标遗传算法及模糊优选技术相结合,得到了一种新调度算法.基于工序的染色体编码方法和基于活动启发式算法的交叉算子的运用,有效地缩小了遗传算法的搜索空间.将随机产生的权系数与模糊优选技术相结合,有助于遗传算法搜索到多个优良的调度方案,这为决策者得到最满意的调度方案提供了保证.仿真结果表明该算法是可行的,与国外学者的同类研究相比,具有一定的优越性.     

A GRASP heuristic for the multi-objective permutation flowshop scheduling problem

This paper presents a multi-objective greedy randomized adaptive search procedure (GRASP)-based heuristic for solving the permutation flowshop scheduling problem in order to minimize two and three objectives simultaneously: (1) makespan and maximum tardiness; (2) makespan, maximum tardiness, and total flowtime. GRASP is a competitive metaheuristic for solving combinatorial optimization problems. We have customized the basic concepts of GRASP algorithm to solve a multi-objective problem and a new algorithm named multi-objective GRASP algorithm is proposed. In order to find a variety of non-dominated solutions, the heuristic blends two typical approaches used in multi-objective optimization: scalarizing functions and Pareto dominance. For instances involving two machines, the heuristic is compared with a bi-objective branch-and-bound algorithm proposed in the literature. For instances involving up to 80 jobs and 20 machines, the non-dominated solutions obtained by the heuristic are compared with solutions obtained by multi-objective genetic algorithms from the literature. Computational results indicate that GRASP is a promising approach for multi-objective optimization.     

电机产品加工的动态调度算法

考虑多个具有不同开始时间的电机产品加工动态调度问题，将产品加工树的工序，分为具有唯一紧前或紧后工序的相关工序和独立工序两类，提出相关工序调度的拟关键路径法和独立工序调度的最佳适应调度法。结合拟关键路径法和最佳适应调度法，提出考虑关键设备的工序紧凑的多产品动态调度算法。实例数据表明，动态调度算法在总加工时间方面比一般启发式算法更短，适合于有不同开始时间的多产品动态调度环境。     

Aggregation and disaggregation of end items in a class of multistage production systems

Aggregation of end items in a class of multistage production systems within a hierarchical scheduling framework is considered. This class is one of flexible machining and assembly systems where each end item is assembled from a number of components. Each component undergoes a sequence of operations on various machines. The assembly structure of all items is flat. At least for some operations on some machines, set-ups are not negligible. Aggregation of constraints and items is employed and the problem of aggregate capacitated lot-size scheduling is formulated. The solution of the original detailed scheduling problem is found by disaggregating the solution of the aggregate scheduling problem. The process of disaggregation is formulated as a mixed integer programming problem, which is shown to be a fixed-charge transshipment problem. An efficient branch and bound/transshipment solution scheme for the disaggregation problem is proposed and validated. A case study on real plant data is presented. This work was supported by the ACME Directorate of the Science and Engineering Research Council, Grant No. GR/D 51476, and was carried out in collaboration with Lucas Aerospace (Engines Divisions)