当前位置：搜档网 › 改进细菌进化算法在作业车间调度问题的应用

改进细菌进化算法在作业车间调度问题的应用

(完整版)智能算法在柔性车间调度中的应用

智能算法在柔性作业车间调度中的应用摘要：为提高企业生产效率，合理的流水车间生产调度显得尤为重要。本文介绍了三种智能算法（蚁群算法、遗传算法、改进粒子群算法）在车间生产调度中的应用，主要介绍了算法的基本思想、模型结构、算法实现以及运用前景。对智能算法在生产调度中的应用做出总结。关键字：智能算法；蚁群算法；遗传算法；改进粒子群算法；生产调度 0.前言柔性作业车间调度问题(Flexible job-shop sche- duling problem, FJSP)是传统作业车间调度问题的扩展，是实际生产中迫切需要解决的一类问题。在传统的作业车间调度问题中，工件的每道工序只能在一台确定的机床上加工。而在柔性作业车间调度问题中，每道工序可以在多台机床上加工，并且在不同的机床上加工所需时间不同。柔性作业车间调度问题减少了机器约束，扩大了可行解的搜索范围，增加了问题的难度。作业车间的主要特点是：n个工件需要在m台机器上进行加工，每个工件都有其独特的加工步骤，但无明显的顺序约束，并且加工时间是已知的，调度的目标是在不允许两个工件同时在同一台机器上加工的前提下，如何安排工件在每台机器上的加工顺序使这些工件能够尽快加工完毕[1]。 1.蚁群算法在作业车间的应用[2] 以3个工件2台机器的问题作为例子，如图1。图1 三个工件两台机器的JSP问题为确定先对哪个工件进行加工，需要设置一个初始节点O0，所有的蚂蚁最初都放置在O0。图1中除与O0相连的有向弧表示同一个工件的加工顺序，工件必须按照该顺序进行加工。其它则为无向弧。每个弧与表示节点间信息素的量和启发式距离的一对值{αij, d ij}有关。d ij 通常为对节点 j 的第 i 步操作的加工时间，τij使用蚁周方式进行更新：其中，ρ是个系数，1?ρ表示在时间t和t+1之间信息素的蒸发，Q为常数，Tk为完成所有加工步骤后最短的总加工时间。初始时刻τij(0)= c（c为常数）。这个规则包含了两个方面：(1)图1中所有边缘上的信息素都要蒸发；(2)完成所有的加工后要将该解的效果加到各边缘上。蒸发可以防止搜索局限在局部最小的邻域中，另一方面又能根据已有解的效果好坏来更新信息素，进行增强学习。另一个关键的问题就是如何保证蚂蚁按照工件的工艺路线产生一组可行解。这里用到3个集合：对每个蚂蚁 k，首先要有集合G k，表示没有访问过的节点集合；S k 表示根据技术路线下一步允许访问的节点集合；还需要一个禁忌表，存放已经访问过的节点。在我们的例子中， G k ={1，2 ，3，4，5 ，6}，S k ={1，2 ，3}。转移概率是通过下式计算的： T ij 为工件i在机器j上的加工时间。每选择一个节点，该节点就被追加到禁忌表中并从G k和 S k中删除；如果被选的节点不是工件的最后一步，那该工件中紧邻的下一个节点会被加到Sk中。该过程一直重复到G k = φ。最后禁忌表中得到的节点的排列顺序就是蚂蚁 k 找到的解。参数α和β决定了算法的收敛速度并对解的性能好坏有重要影响，同时蒸发常数也需要进行适当的调整以使搜索能在好的搜索空间中进行，并防止陷入局部最优的邻域中。

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

第15卷第8期计算机集成制造系统 Vol.15No.82009年8月 Computer Integrated Manufacturing Systems Aug.2009 文章编号:1006-5911(2009)08-1592-07 收稿日期:2008207208;修订日期:2008209201。Received 08J uly 2008;accepted 01Sep.2008. 基金项目:国家863/CIMS 主题资助项目(2007AA04Z190,2008AA042301);国家自然科学基金资助项目(50835008,50875237)。Found ation i 2 tems :Project supported by t he National High 2Tech.R &D Program for CIMS ,China (No.2007AA04Z190,2008AA042301),and t he National Natural Science Foundation ,China (No.50835008,50875237). 作者简介:魏　巍(1982-),男,辽宁沈阳人,浙江大学CAD &CG 国家重点实验室博士研究生,主要从事产品配置优化、产品信息建模、多目标优化和先进制造技术等研究。E 2mail :boyweiwei @https://www.sodocs.net/doc/846917566.html, ;+通信作者E 2mail :fyxtv @https://www.sodocs.net/doc/846917566.html, 。柔性工作车间调度问题的多目标优化方法研究魏　巍1,谭建荣1,冯毅雄+1,张　蕊2 (1.浙江大学流体传动及控制国家重点实验室,浙江　杭州　310027; 2.华晨金杯汽车有限公司,辽宁　沈阳　110044) 摘　要:针对各工件目标不同的多目标柔性作业车间调度问题,构建了以加工成本、加工质量及制造工期为目标函数的柔性作业车间调度多目标优化数学模型。针对传统的加权系数遗传算法不能很好地解决柔性作业车间调度多目标优化问题,提出采用改进的强度Pareto 进化算法,对柔性作业车间调度问题进行多目标优化,从而得出柔性车间调度问题的Pareto 综合最优解。最后,结合项目实施,以某大型空分装备企业的车间调度为例,证明了文中提出的方法能很好地解决柔性工作车间调度的多目标优化问题。关键词:柔性车间调度;多目标优化;遗传算法;强度Pareto 进化算法中图分类号:TP278 文献标识码:A Multi 2objective optimization method research on flexible job shop scheduling problem W EI Wei 1 ,TA N J ian 2rong 1 ,F EN G Yi 2x iong +1 ,Z HA N G Rui 2 (1.State K ey Laboratory of Fluid Power T ransmission &C ontrol ,Zhejiang University ,Hangzhou 310027,China ; 2.Shenyang Brilliance J INB EI Automotive Corporation Limited.,Shenyang 110044,China ) Abstract :To solve the multi 2objective optimization problem in flexible job shop scheduling ,the multi 2objective sched 2uling optimization model ,namely the cost 、quality and term ,was constructed.While the traditional genetic algo 2rithm which combined random weigh could not solve the multi 2objective scheduling optimization problem commend 2ably.An improved strength Pareto evolutionary algorithm was employed to optimize the multi 2objective optimization model parallelly.As a result ,the optimal schema of flexible job shop scheduling was presented in the form of Pareto optimal sets.At last ,an instance related with the project in the air separation equip industry was given to prove that the proposed method could solve multi 2objective optimization problem in flexible job shop scheduling effectively.K ey w ords :flexible job shop scheduling ;multi 2objective optimization ;genetic algorithm ;SPEA2 0　引言柔性作业车间调度问题(Flexible Job Shop Scheduling Problem ,FJ SP )是指带有机器可选柔性的车间调度问题。相对经典作业车间调度问题,FJ SP 突破了资源唯一性限制,每个工序可由多个不同的机器完成,更加符合实际的生产环境。因此,研究FJ SP 具有重要的理论价值和应用意义。在处理FJ SP 问题上,文献[1]提出分布法,其基本思想是将机器分配问题和调度问题分开考虑,以降低FJ SP 问题的复杂性。文献[2]～文献[4]分别采用贪婪法、模拟退火算法和禁忌搜索法对FJ SP 问题进行优化求解。文献[5]在遗传算法框架的基础上,通过加权系数法将多目标问题转化为单目标

数学建模--车间作业调度问题

一、二维背包问题一维背包问题讨论的背包问题只有一种限制，即旅行者所能承受的背包的重量（亦即重量不能超过a （kg ）.但是实际上背包除受重量的限制外，还有体积的限制，这就是不但要求旅行者的背包的重量M 不能超过a （kg ），还要求旅行者背包的体积V 不能超过b （m3）,我们把这样的问题称为“二维背包问题”。它的状态变量有两个因素:一个是重量，一个是体积。二维背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i 件物品所需的两种代价分别为i a 和i b 。两种代价可付出的最大值（两种背包容量）分别为a 和b 。物品的价值为i c 。模型： 11 1 max . ,1,2,3...n i i i n i i i n i i i i c x st a x a b x b x z i n ===≤≤∈=∑∑∑

例题码头有一艘载重量为30t ，最大容为12×10m 3的船，由于运输需要,这艘船可用于装载四种货物到珠江口，它们的单位体积,重量及价值量见下表: 现求如何装载这四种货物使价值量最大。 1 1 1 max .,1,2,3...n i i i n i i i n i i i i c x st a x a b x b x z i n ===≤≤∈=∑∑∑ 可用动态规划来解决 1.设x i （i=1,2,3,4）分别表示装载这四种货物的重量， 2.阶段k ：将可装入的货物按1,2,3,…n 排序，每个阶段装一种货物，（共可分为四个阶段） 3.状态变量： 1k S +和1k R +，表示在第k 阶段开始时，允许装入的前k 种货物的重量与体积。状态转移方程： 11k k k k k k k k S S a x R R b x ++=-=- ()(){}111,max ,j k k j k k j j f S R f S R c x -++=+，表示在不超过重量和体积的前提下，装入前j 中货品的价值。（j=1,2,3,4）

作业车间调度模型

基于WSA算法的作业车间低碳调度方法研究 1.1 引言本章主要研究了以最大化完工时间和能耗指标为目标的作业车间低碳调度模型的求解方法。首先，建立了多目标作业车间低碳调度模型；然后基于Pareto 支配理论，设计了一种高效的MODWSA算法获得满意的Pareto非支配解；最后，设计了一套测试算例，将MODWSA算法与其它经典多目标算法进行比较分析，验证了MODWSA算法的优越性。在本研究中，作者完成了两项工作：首先，构建了一个新的多目标作业车间低碳数学模型；其次，设计了一种高效的MODWSA算法获得满意的Pareto非支配解。 1.2 作业车间低碳调度模型本章研究的作业车间低碳调度问题可描述如下：对给定的n个工件及k台机器，一个工件的加工需要经过m道工序，每道工序允许在特定的机器上加工，任意一台机器在任意一个时刻仅能加工某一工件的某一道工序，并且一个工件只能在其上道工序完成后下一道工序才能开始加工[插入文献]。考虑机器的准备时间，准备时间与同一机器上相邻两工件的加工顺序相关，并且机器的启动和工件的加工是相连的。对应于不同工序，机器具有不同的速率档位进行加工，并且可以进行调节。从能耗的角度来看，机器有四种不同的状态：加工状态(机器在加工工件)，启动状态（机器在准备加工一个新的工件），待机状态（机器处于空转中），以及关机状态（机器被关机）。通常情况下，当机器在较高速率运作时，工件的加工时间会被缩短，但是相应的能耗会增加。因此本问题以最大化完工时间和能耗指标为目标，由于本章所研究问题的特点，该问题要比传统的作业车间调度问题要复杂的多。在该问题中，其它设定如下： ●工件在车间里被连续加工。也就是说，加工过程不能被中断。 ●机器允许有空闲时间，并且各阶段间具有容量无限的缓冲区。 ●当有第一个工件在机器上加工时，机器开机；当在该机器上加工的所有工件加工完毕后，机器关机。 ●机器速度在工件加工过程中不能进行调整。 1.2.1 混合整数规划模型为了提出问题的数学模型，根据上面对问题的描述，我们首先定义了下面的相关数学符号。

基于文化遗传算法求解柔性作业车间调度问题

第16卷第4期计算机集成制造系统 Vol.16No.42010年4月 Computer Integrated Manufacturing Systems Apr.2010 文章编号:1006-5911(2010)04-0861-06 收稿日期:2009204220;修订日期:2009209216。Received 20Apr.2009;accepted 16Sep.2009. 基金项目:国家自然科学基金资助项目(70771008,70371057)。Found ation item :Project supported by t he National Natural Science Foundation , China (No.70771008,70371057). 作者简介:李铁克(1958-),男,吉林长春人,北京科技大学经济管理学院教授,博士生导师,主要从事先进制造管理、生产计划与调度、智能算法等的研究。E 2mail :tiekeli @https://www.sodocs.net/doc/846917566.html, 。基于文化遗传算法求解柔性作业车间调度问题李铁克,王伟玲,张文学 (北京科技大学经济管理学院,北京　100083) 摘　要:在分析柔性作业车间调度问题特性的基础上,提出了一种采用主群体空间和信仰空间的双层进化结构的调度算法。该算法采用优良调度方案的知识信息构成信仰空间;提出一种二维矩阵的集成编码;基于工序顺序编码和基于机器分配编码的两种交叉和变异算子在主群体空间进行传统的遗传操作;通过具有自学习特点的相似性选择算子,使子代更好地继承父代的优良特征。通过典型算例的计算实验,表明算法在计算效率和求解质量上均具有较好的效果。关键词:柔性作业车间调度;文化算法;遗传算法;选择算子中图分类号:TP301.6 文献标志码:A Solving flexible Job Shop scheduling problem based on cultural genetic algorithm L I Tie 2ke ,W A N G Wei 2ling ,Z HA N G Wen 2x ue (School of Economics &Management ,University of Science &Technology Beijing ,Beijing 100083,China )Abstract :Based on the analysis of the characteristics of Flexible Job Shop Scheduling (FJ SP )problem ,the double 2layer evolution scheduling algorithm with f rame population space and belief space to solve FJ SP was proposed.This algorithm adopted usef ul knowledge of excellent scheduling schemes to form belief space.A two 2dimensional matrix integrated coding was put forward.Traditional genetic operations were conducted in f rame population space among two effective crossover operators and mutation operators ,which were designed on the basis of the integration of ma 2chine assignment and operation sequence for the genetic algorithm.By selection operators with similar self 2learning char 2acteristics ,son 2generations inherited excellent characteristics from parent 2generations.Experimental results indicated that the proposed algorithm outperformed the current approaches in computation efficiency and solution quality.K ey w ords :flexible Job Shop scheduling ;cultural algorithm ;genetic algorithm ;selection operator 0　引言柔性作业车间调度问题(Flexible Job 2shop Scheduling Problem ,FJ SP )是经典作业车间调度问题(Job 2shop Scheduling Problem ,J SP )的扩展[1]。在J SP 中,仅考虑工件具有唯一确定的加工工艺路线的情况。而在FJ SP 中,每道工序可以在多台机器上加工,工件具有可选择的加工路线,并且在不同机器上加工所需的时间不同,因此FJ SP 比J SP 更接近实际制造环境,是实际生产中亟需解决的一类调度问题。 FJ SP 不仅需要确定工件的加工顺序,还要确定某道工序由哪台机器加工。因此,FJ SP 是比J SP 更为复杂的N P 2hard 问题,一般不存在有效的多项式算法[2]。现有的研究方法主要分为精确算法、启发式规则[3]和元启发式算法(如模拟退火、遗传算法(Genetic Algorit hm ,GA )等)[4]。其中精确算法无法对大规模FJ SP 进行有效求解;启发式规则求解

生产调度综述

生产调度求助编辑百科名片生产调度室生产调度就是组织执行生产进度计划的工作。生产调度以生产进度计划为依据，生产进度计划要通过生产调度来实现。生产调度的必要性是由工业企业生产活动的性质决定的。现代工业企业，生产环节多，协作关系复杂，生产连续性强，情况变化快，某一局部发生故障，或某一措施没有按期实现，往往会波及整个生产系统的运行。因此，加强生产调度工作，对于及时了解、掌握生产进度，研究分析影响生产的各种因素，根据不同情况采取相应对策，使差距缩小或恢复正常是非常重要的。目录工作作用主要内容与基本要求机构和分工调度工作制度生产调度工作的基本内容展开编辑本段工作作用综述生产计划和生产作业计划编制出来之后，还仅仅是纸上的东西，要组织计划的实施，把纸上的计划变成现实的可供销售的产品，就需要一个部门去组织实现这项任务，这就是生产调度。保证生产过程顺利运行编制生产计划和生产作业计划，无论考虑多么周密，安排如何具体，也不可能预见到实际生产过程中的一切变化。实际生产过程中，情况十分复杂，千变万化，有局部的，也有整体的；有内部的，也有外部的；有工艺方面的，也有设备方面的；有主观因素，也有客观因素。这些问题一旦出现，小则造成生产被动，大则造成生产过程中断，生产停车，计划难于完成。生产调度就是要及时了解掌握这些影响因素。组织有关部门、有关人员处理解决这些不平衡因素，消除隐患，以保证生产过程长周期安全运行，保证生产计划和生产作业计划按要求实现。如果没有生产调度夜以继日的指挥调度，要想及时解决生产过程中随时出现的矛盾，维持生产过程的正常运行，是不可能的。收集生产动态和有关数据生产调度不仅要组织实现生产计划，而且在组织生产过程中，有许多工艺、设备、

基于深度强化学习的柔性车间调度问题现代研究

基于深度强化学习的柔性车间调度问题现代研究摘要本文针对多目标柔性作业车间调度问题进行研究，分别以机器总负荷和设备利用率为性能指标，建立了多目标柔性作业车间调度模型。由于传统的企业调度算法忽略了历史数据的价值，在实时事件发生后不能快速响应支持，同时为了迎合“智慧工厂”的趋势，提出了一种适用于柔性作业车间调度的深度强化学习方法，实现了从状态输入到行为输出的直接控制。最后，通过实验案例验证了该方法在解决多目标柔性作业车间调度问题的可行性和有效性。关键词柔性作业车间调度；深度强化学习；状态编码；多智能体前言近年来，市场中定制化服务已经成为一种普遍需求，“随需应变”的理念得到了企业管理者的高度重视。柔性生产是指通过先进制造设备来实现多品种、小批量的生产方式，其主要优点是增强了制造企业的灵活性和应变能力，提高了设备利用率。柔性作业车间调度问题（Flexible job-shop problem，FJSP）是传统作业车间调度问题的重要扩展，是目前车间调度问题的研究热点。与传统的作业车间调度问题相比，柔性作业车间调度问题减少了机器能力约束，是更为复杂的NP-hard问题。目前的相关研究主要集中在算法效率改进[1-3]、问题实际化[4-7]、优化目标扩展[8-10]三个方面。在柔性作业车间调度问题上一般采用两种方法求解：启发式方法和集成方法[11]。问题实际化的研究主要通过加入更多生产相关约束，使得问题模型更加贴近实际生产。许多学者在上述三个方面进行了深入的研究，但是他们对于企業过去的生产调度历史数据并没有进行关注，忽略了其价值。随着“中国制造2025”的提出，智能制造成为推进该项战略的重要举措。智能制造包括了智能制造技术和智能制造系统。深度强化学习作为一种端对端的感知与控制系统，为构建智能化的生产调度系统提供了重要指导和有效支持。本文针对柔性作业车间调度问题，以最小化机器总负荷和最大化设备利用率为目标。通过对生产状态的编码，将每个工件构建为一个智能体。采用多智能体Actor-Critic算法，使得工件智能体学习彼此协作，为求解多目标柔性作业车间调度问题提供一种智能化的方法。 1 多目标柔性作业车间优化建模 1.1 问题描述 nm的FJSP问题可以描述为：一个拥有m台机器的加工系统，加工处理n 个工件。其中每个工件包含一道或者多道工序，每道工序可以在一台或者多台机器上进行加工处理，且相对应的加工时间取决于所分配的机器能力。对于该类问

生产调度工作内容

生产调度工作内容各位读友大家好，此文档由网络收集而来，欢迎您下载，谢谢编号生产调度工作流程工步4-1 补充内容一）、在与客户沟通时要明确如下之全部内容，保证急时、准时、准确、保质、保量的情况下，将货品安全送到目的地，避免因与客户沟通不细致，遗漏注意事项，导致货品出现误时、误工的现象，从而影响客户的正常安排。二）、在与客户沟通时要，主动向客户问清，客户所需货品的规格、型号、单价及质量要求，向客户询问清楚有无其他交代及送货注意事项，包括相关资料、资质及其它未尽事项。三）、在与客户沟通时，要主动向客户询问清楚，到货的具体时间、接货人的联系方式及接货地点的详细位置，绝对禁止出现例如：上午、中午、下午等

含糊不清的时间表达方式，时间上要具体点。四）、在与客户沟通时，主动向客户提醒，希望客户尽量提前24小时安排用货计划，以便于车辆的安排，如未提前报，客户又着急的情况下，以满足客户的要求为原则，加班加点完成任务，使客户满意。五）、生产调度在派发运输车辆时，必须做到提前安生产调度工作流程工步4-1 补充内容排切割，提前安排。六）、对待客户的无理要求，我们要做到不气、不急，以柔克刚、合理周旋，没办法处理的，可以推脱与上级沟通再做处理，避免冲突。七）、在对待客户的苛刻要求时，我们要做到不急、不气，向客户耐心解释，不允许对客户有不礼貌的现象，避免与客户争执，要耐心沟通，无法解决时向上级领导汇报，希望客户耐心等待。八）、要向司机师傅交代清楚，发货

出发前要与客户提前联系，告知客户具体的到货时间及其它事宜，在送货途中，如有特殊情况，要告知司机与客户随时联系，保证司机、客户、调度随时沟通，以便于客户安排。九）、生产调度主动在送货结束后，应急时收回相应送货单或货款，避免单据及货款不及时现象。十）、生产调度要主动告知，在我单位合作送货的车辆几司机师傅，须按如下工作流程进行送货。生产调度工作流程工步4-1 补充内容十一）、在实际工作中如有新问题出现，随时发展改进我们的工作标准，及时增加工作内容。生产调度生产调度就是组织执行生产进度计划的工作。生产调度以生产进度计划为依据，生产进度计划要通过生产调度来实现。生产调度的必要性是由工业企业生产活动的性质决定的。现代工业企业，

求解作业车间调度问题的全局邻域搜索方法

第15卷第7期计算机集成制造系统 Vol.15No.72009年7月 Computer Integrated Manufacturing Systems July 2009 文章编号:1006-5911(2009)07-1383-06 收稿日期:2008 06 18;修订日期:2008 10 13。Received 18June 2008;accepted 13Oct.2008. 基金项目:国家自然科学基金资助项目(70771008,70371057)。Fo undation item:Project supp orted by the National Natural Science Fundation, Ch ina(N o.70771008,70371057). 作者简介:崔健双(1971-),男,河北衡水人,北京科技大学经济管理学院副教授,博士,主要从事生产调度算法理论及应用、安全电子商务的研究。E mail:cuijs@manag https://www.sodocs.net/doc/846917566.html, 。求解作业车间调度问题的全局邻域搜索方法崔健双,李铁克 (北京科技大学经济管理学院,北京 100083) 摘要:采用传统的关键邻域搜索方法求解作业车间调度问题时,往往容易陷入局部极值而且难以跳出。为此,提出了一种具有动态调整能力的全局邻域交换策略,该策略有可能产生大量的不可行调度,需要一种筛选方法加以过滤。证明了一个新的邻域交换性质,利用该性质可以对所得调度方案作可行性约束判定,从而有效地过滤掉不可行调度。在此基础上,提出了一种求解作业车间调度问题的算法。最后,取不同规模的Benchmar k 问题算例对该算法进行测试,结果表明,无论从解的质量还是计算时间都取得了较好的效果。关键词:邻域结构;关键路径;作业车间调度;邻域交换;调度算法中图分类号:T P18 文献标识码:A Global neighborhood algorithm for Job Shop scheduling problem CUI J ian shuang,LI T ie ke (Scho ol of Economic M anag ement,U niversit y of Science &T echno lo gy Beijing,Beijing 100083,China)Abstract:T r aditional cr itical neighbor ho od alg or ithms fo r Jo b Shop scheduling problem w ere easily t rapped into local optimal and hardly to escape.T o deal w ith t his pro blem,a g lo bal neig hbo rhoo d swapping st rateg y wit h dynamic adapatability w as pr oposed.H ow ever,this new strateg y mig ht possibly induce infeasible so lutio ns.T hus,a new pr oposition concerning the neig hbor hood sw apping str ategy w as presented and pr ov ed,w hich could be used to v erify whether a neighbor ho od swapping w as accept able or not.Based on this g lo bal neig hbo rhoo d st rateg y,a new alg o r ithm w as develo ped and tested by a gr oup of benchmark instances.T he r esults indicated that the new algo rithm ob tained satisfactor y results both on solut ions quality and computat ion time. Key words:neig hbo rhoo d structur e;crit ical path;Job Sho p scheduling ;neighborho od sw apping;scheduling alg o rithms 0 引言自从20世纪50年代以来,调度问题相关理论及其应用技术的研究已经发展成为一门重要的学科,从经典的单机调度、并行机调度、车间调度发展到后来的多目标调度、随机调度和模糊调度等内容。调度问题成为从事运筹学、人工智能学和应用数学等学科领域的学者们关注的焦点,相应的应用领域在不断地扩大。随着问题研究的深化,人们对解决调度问题的难度有了进一步的认识,发展了关于调度算法的有效性和计算复杂性理论,并且证明出许多调度问题包括多数作业车间调度问题(Jo b Shop Scheduling Problem,JSP)都是NP 完备问题[1]。JSP 是利用一组有限资源对一批有限任务在满足给定约束条件下求解最优目标函数的一个复杂的组合优化问题,也是迄今为止人们研究最多、研究成果最丰富、但仍未得到根本解决的问题之一。事实表明,有些NP 完备问题存在有限时间内的可行解,

作业调度器综述及问题2

分布式系统Hadoop作业调度器及其问题的讨论 Hadoop是Apache基金会下的一个分布式系统基础架构，它最核心的两个部分：分布式文件系统HDFS，存储Hadoop集群中所有存储节点上的文件；由NameNode和DataNode 组成；分布式计算引擎MapReduce，由JobTracker和TaskTracker组成。 Hadoop使得用户可以在不了解分布式系统底层细节的情况下，轻松地根据自己的业务需求，开发出分布式应用程序。在Hadoop的实际应用中，往往存在多种应用共用Hadoop 的情况，例如： ?生产性应用：数据分析、统计计算等； ?批处理应用：机器学习等； ?交互式应用：SQL查询等。因此，在Hadoop集群中，可能同时运行多道作业，不同类型的作业，作业之间可能还存在依赖关系，那么，这种情况下该如何保证整个集群计算资源得到充分的利用呢？这就要求有一个作业调度器，来保证在整个集群内有效地进行作业的调度与执行过程。 Hadoop作业调度器的设计采用的是插件机制，即作业调度器是动态加载的、可插拔的，同时第三方可以开发自己的作业调度器替代Hadoop默认的调度器。目前，Hadoop的作业调度器主要有以下三个： ?FIFO Scheduler：采用一个FIFO队列进行调度，在其基础上Hadoop还提供一个扩展的调度器，可以对每个job的tasks总数作限制；优点是实现非常简单、调度过程快；缺点是资源的利用率不高。 ?Capacity Scheduler：采用多个队列，每个队列分配一定的系统容量，空闲资源可以动态分配给负荷重的队列，支持作业优先级；优点是支持多作业并行执行，提高资源利用率，动态调整资源分配，提高作业执行效率；缺点是用户需要了解大量系统信息，才能设置和选择队列。

基于改进遗传算法的柔性作业车间调度

第39卷第7期2007年7月哈尔滨工业大学学报 J OURN AL OF HARBI N I NSTI T UTE OF TECHNOL OG Y Vo l 139N o 17Ju.l 2007 基于改进遗传算法的柔性作业车间调度席卫东1,2 ,乔兵1 ,朱剑英 1 (1.南京航空航天大学民航学院,南京210016,E 2m ai:l x wdn@j 163.co m;2.远东控股集团,江苏宜兴214257) 摘要:应用遗传算法解决柔性作业车间调度问题,针对柔性作业车间问题的特点提出了一种新颖直观的双子串基因编码方法,并设计了独特的交叉和变异算子,从而取消了运用遗传算法求解作业车间问题时为使基因合法化而进行的基因修复和重建过程,仿真结果表明用该遗传算法解决柔性作业车间调度是有效的.关键词:柔性作业车间;遗传算法;作业车间调度中图分类号:TP18;TP 273 文献标识码:A 文章编号:0367-6234(2007)07-1151-03 A genetic a lgor ith m for flexi b le job shop schedu li ng based on t wo 2sub str i ng gene cod i ng m ethod XIW e i 2dong 1,2 ,Q I A O Bing 1 ,Z HU Jian 2ying 1 (1.The College of C i vil Avi atio n ,N an ji ng University of Aero nauti cs and Astronautics ,Nanji ng 210016,Ch i na ,E 2m a i:l x wdn@j 163.co m;2.F ar EastH oldi ng Gro up Co .,LTD ,Y i xi ng ,214257China) Abstr act :A novel genetic algorithm f or solvi n g flexi b le job shop scheduling prob le m is elaborated .An intui 2ti v e gene cod i n g method ,called t w o-substri n g gene cod i n g ,and a spec ial cross operator aswell as a mutation method are proposed .By doing tha,t the repa iring process to va lida te the schedu le gene is successf ully can 2ce lled .The co mputer si m u lations are carried out and the results are worked ou t to sho w the eff ecti v eness of the proposed a l g orithm.K ey w ord s :flexi b le j o b shop;genetic algorithm ;j o b shop schedu li n g 收稿日期:2005-04-29. 作者简介:席卫东(1967)),男,博士研究生; 朱剑英(1937)),男,教授博士生导师. 作业车间调度问题(JSSP :Job Shop Schedu 2li n g Prob le m )通常出现在工业制造环境中,为了完成一个作业,必须按顺序在若干台机器上处理一系列不同工序,并且同时有若干个作业需要完成,管理人员必须根据作业的生产方式和工艺要求设计一个调度表,以获得某种生产指标的最优化,如加工周期最短、设备利用率最高等. 在古典作业车间调度中约定,任一工序只能由指定的某台设备加工,而在柔性作业车间调度(FJSSP :Flexible JSSP)中,则允许工序由一个机床集合中的任意一台加工,这更符合实际的生产状况,调度的目的是将工序分配给各机床,并对各机床上的工序进行排序以使完成所有工序的时间最小化.FJSSP 比JSSP 更为复杂,因为FJSSP 不但需要确定所有工序在所有机器上的安排,而且还要确定每一台机器上工序的序列. JSSP 已被证明为NP-hard 问题 [1] .由于它的高度并行性和重要的实际意义,学者们对其进行了广泛的研究,并提出了许多算法.这些算法可以分为下面几类:启发式方法、人工智能方法、最优化方法和近似最优法 [2] .近年来,对于这类具有高度并行性和复杂性的问题,学者们提出了一些非经典、非线性的求解方法,获得了很好的效果 [3] ,如神经网络算法、模拟退火算法、遗传算法等.其中,由于遗传算法(GAs)良好的全局搜索性能、内在的并行处理能力及其在解决TSP 一类组合优化问题方面的成功应用,引起了JSS P 研究人员的重视,Gen and Cheng [4] 提供了一个很好的关于G As 应用于JSSP 研究的综述并提出了若干JSSP 遗传算法,但是对于应用G A s 解决FJSSP 却未做研究.基于上述分析,本文试图采用遗传算法来解决FJSSP .

求解柔性作业车间调度问题的两级邻域搜索混合算法

第51卷第14期2015年7月机械工程学报 JOURNAL OF MECHANICAL ENGINEERING Vol.51 No.14 Jul. 2015 DOI：10.3901/JME.2015.14.175 求解柔性作业车间调度问题的两级邻域搜索混合算法* 赵诗奎 (济南大学机械工程学院济南 250022) 摘要：针对柔性作业车间调度问题(Flexible job shop scheduling problem，FJSP)，以优化最大完工时间为目标，提出一种融合两级邻域搜索和遗传算法的混合算法。基于通过利用机器空闲时间来减小最大完工时间的想法，构造邻域结构，对关键路径上的关键工序进行移动，实现邻域搜索，以改进当前解；设计针对FJSP问题特点的两级邻域搜索方式，第一级邻域搜索为跨机器移动工序，将工序移动到除当前加工机器之外的其他可选机器上，第二级邻域搜索为同机器移动工序，将工序在当前加工机器上进行移动；给出两级邻域搜索相应的保证可行解工序移动条件；兼顾FJSP问题求解算法的全局搜索能力和局部搜索能力，利用遗传算法实现全局搜索，两级邻域搜索实现局部搜索；采用国际通用的FJSP问题基准算例进行测试，验证了所提方法的有效性。关键词：柔性作业车间调度问题；两级邻域搜索；邻域结构；遗传算法中图分类号：TP301 Bilevel Neighborhood Search Hybrid Algorithm for the Flexible Job Shop Scheduling Problem ZHAO Shikui (School of Mechanical Engineering, University of Jinan, Jinan 250022) Abstract：For the flexible job shop scheduling problem (FJSP), in order to optimize the maximum completion time, a hybrid algorithm mixed with bilevel neighborhood search and genetic algorithm is proposed. The neighborhood structure is constructed by using machine idle time to reduce the maximum completion time. In order to improve the current solution, critical operations of the critical path are moved to achieve neighborhood search. The method of bilevel neighborhood search is designed according to the characteristics of FJSP. The first level neighborhood search is the cross-machine moving operation, and the operation is moved to other optional machines in addition to current processing machine. The second level neighborhood search is the same-machine moving operation, and the operation is moved on current processing machine. Operation moving conditions corresponding to the bilevel neighborhood search are given to ensure feasible solutions. Both of global search ability and local search ability of FJSP solving algorithm are considered, and to use genetic algorithm to achieve global search, bilevel neighborhood search to achieve local search. The internationally accepted FJSP benchmark examples are adopted to test the validity of the proposed method. Key words：flexible job shop scheduling problem；bilevel neighborhood search；neighborhood structure；genetic algorithm 0 前言高效的生产调度优化技术对于提高制造系统生产率和设备资源利用率，缩短产品制造周期具有 * 国家自然科学基金(51405193)、山东省优秀中青年科学家科研奖励基金(BS2014ZZ013)和济南大学博士基金(XBS1427)资助项目。20141011收到初稿，20150420收到修改稿十分重要的意义。随着加工技术、自动化技术的发展，柔性制造系统和数控加工中心等带有一定柔性的生产系统逐渐出现，具有柔性机器选择的柔性作业车间成为企业应对动态突变市场环境和机器故障等突发事件的有力工具，柔性作业车间调度问题(Flexible job shop scheduling problem，FJSP)逐渐成为研究的焦点问题。FJSP问题是传统作业车间调度问题(Job shop scheduling problem，JSP)的延伸，它突破