紧密衔接工序组联动的综合调度算法

由于现有的工序间存在紧密衔接条件的复杂产品综合调度问题, 采用的移动交换算法不易于软件实现且没有考虑移动工序后产生的连锁反应引起较高算法复杂度的问题, 提出将具有紧密衔接约束条件的工序组进行统一联动的综合调度算法.该算法利用将具有紧密衔接约束条件的工序分组的扩展加工工艺树模型, 按路径上属于工序组的工序个数多少确定所在路径工序组调度的次序, 通过降低对工序组的限制要求降低算法复杂度; 对于被调度工序组中各工序的前序工序, 按工序组中工序的加工顺序确定调度次序, 对某个工序的前序工序采用复杂度较低的拟关键路径法确定工序的调度次序; 调度完所有紧密衔接工序组后, 剩余的标准工序按拟关键路径法确定调度顺序; 采取工序首次适应调度算法调度标准工序和工序组, 由于工序组中工序采取按序紧密衔接的联动调度方式确定工序组的开始时间, 避免了二次调整, 进一步降低了算法复杂度. 分析和实例表明, 所提出的综合算法比以往算法复杂度更低, 调度结果更优且更易于实现.     

基于调度长路径的复杂产品综合调度算法

针对目前复杂产品加工和装配综合调度算法中考虑纵横双向调度优化时以横向为主,而忽略产品工序内在纵向约束对制造效率产生主要影响的问题,提出了以关键路径为主的纵横双向调度优化算法——基于调度长路径的复杂产品调度算法。该算法考虑了复杂产品树状工艺结构,根据优先级策略并结合调度长路径和长用时等策略来确定工序的调度次序。采用优先级策略可以兼顾其他分支上的同层工序;采用调度长路径策略是在兼顾其他分支的同时优先考虑了关键路径上工序对总加工时间的影响;采用长用时策略可以优先调度对加工时间影响大的工序。对已定调度次序的工序采用工序尽早加工的原则确定开始加工时间。实例表明,提出的调度策略简便可行且调度结果更优。     

工序间存在零等待约束的复杂产品调度研究

针对实际装配生产中工序之间存在零等待约束的复杂产品的调度问题, 提出了一种把存在零等待约束的工序虚拟成一个工序的方法. 该方法在提出复杂产品、标准工序、虚拟工序、零等待和扩展加工工艺树的概念基础上, 对扩展加工工艺树中的标准工序采用拟关键路径法和最佳适应调度的车间调度算法进行调度, 对虚拟工序采用移动交换算法在相应设备上分离调度, 将存在零等待约束的调度问题转化为存在虚拟工序的无零等待约束的调度问题. 实例表明, 所提出的调度算法能够较好地解决具有实际意义的工序间存在零等待约束的复杂产品的调度问题, 且易于实现.     

考虑后续工序的择时综合调度算法

针对目前综合调度算法不能兼顾产品工艺树中并行工序的并行性和串行工序之间紧密度，影响调度结果的问题，提出考虑后续工序的择时综合调度算法.该算法提出工序序列排序策略，从工艺树的整体结构出发，将其划分成若干内部工序只具有串行关系的工序序列，并按路径长度从长到短的顺序确定其调度次序；提出择时调度策略和考虑后续工序策略，根据工艺树自身特点，从来自不同工序序列的并行工序的不同组合方案中，选择最接近调度目标的方案作为工序调度方案，若该工序调度方案不唯一，则在其中选择该工序加工开始时间最早的调度方案.该算法既保证了工序的并行处理，又提高了串行工序的紧密度，优化了综合调度的结果.最后通过实例说明本文算法对解决综合调试问题具有普遍意义.     

基于剪枝分层的柔性加工车间调度算法

针对柔性作业车间调度中工序间存在的冗余调度次序约束关系问题和工序-设备间存在的多加工模式情况,提出基于剪枝分层的柔性加工车间调度算法.该算法首先用有向无环图表示工序及工序间的调度次序关系,采用剪枝法消除图中的冗余弧,采用分层法对图中结点分层;其次对加工模式进行分类,制定工序-设备预约策略和工序-设备预分配策略;最后,采用事件驱动策略,驱动时刻按所提出的柔性加工策略调度工序加工.理论分析和实例表明,所提出的算法具有较好的调度效果.     

基于工序集的动态关键路径多产品制造调度算法

针对已有的树状结构多产品加工和装配综合调度方法,不能兼顾树状结构纵横双向、影响调度结果的问题,提出基于工序集的动态关键路径多产品制造调度算法.该算法首先采用根对齐的方法,将多个树状结构的产品转化成一个虚拟加工树,使多产品调度问题简化为单产品调度问题;在调度过程中,根据虚拟加工树动态生成可调度的备选工序集合,按提出的动态...     

可回退抢占的设备驱动综合调度算法

针对基于拟关键路径法的综合调度算法按路径长度确定工序的调度次序,形成工序组间的并行处理, 使设备产生较多空闲时间的问题,提出可回退抢占的设备驱动综合调度算法. 该算法以每次工序加工结束作为一次可调度工序的寻找事件,若此时新出现的可调度工序具备抢占能力,则产生回退事 件进行重调度;若不产生回退事件,如果可调度工序唯一,则调度此工序;如果可调度工序不唯一, 选择父结点路径长的工序;如果父结点最长路径相同,选择用时长的工序. 由于该算法在调度工序时形成工序间的并行处理,缩小基于拟关键路径的综合调度算法形成的并行处理单位,进而减少加工过程中产生较多的设备空闲时间,提高设备利用率;同时,由于采用抢占式的回退调度策略,优先调度对调度结果有重要影响的长路径工序,达到对拟关键路径法的扬长避短,进一步提高设备利用率.     

可动态生成具有优先级工序集的动态Job-Shop调度算法

为了在满足约束条件的前提下使不同时刻加入到作业集合中的全部作业所用的加工总时间尽可能地少,提出算法:根据动态的作业集合构造虚拟加工树,虚拟加工树上的叶结点代表最先加工的工序,虚拟根节点代表最后一道工序,边代表偏序关系;以层优先为虚拟加工树上的工序设置优先级,工序的优先级可作为调度过程中考虑的一个因素;除了在工序需要动态调整的情况下,在调度过程中始终遵循着机器忙原则.在调度过程中,首先根据虚拟加工树动态地生成备选工序集合,然后根据工序的优先级并且结合其它的调度策略从备选集合中调度工序,直到备选集合为空,即所有作业加工完毕.这里提到的调度策略包括短用时策略、长路径策略和动态调整策略.通过实例验证,该算法对于动态Job-Shop问题可以获得比较好的解.     

两车间可调度工序均衡处理的综合调度算法

在两车间具备相同设备资源的生产条件时,需要考虑产品完成时间和车间之间工序移动次数尽可能少的问题。为此,提出两车间可调度工序均衡处理的综合调度算法。为减少单件复杂产品的完成时间,针对可调度工序的灵活性、并行性和两车间设备相同的条件,采用可调度工序车间均衡策略进行分组。为减少工序移动次数,按分组工序车间确定策略分配工序所在车间,并进行调度。实例结果表明,该算法可实现两车间综合调度,且产品完成时间和车间之间的工序移动次数较少。     

基于逆序信号驱动的紧密衔接综合调度算法

针对以往综合调度中紧密衔接调度算法只能处理单一紧前工序的情况,使算法具有局限性问题,提出基于逆序信号驱动的紧密衔接综合调度算法.该算法先建立设备和调度2个子系统,并通过相互间传递的信号驱动逆序调度;对于紧密衔接工序组包含非单一紧前工序的情况,将紧密衔接工序组定义为一棵特殊的紧密衔接子树,采用逆序调度的方式自顶向下对紧密衔接问题求解;当信号驱动时刻存在多个可调度工序(组)时,按最大可并行性选择策略选择子节点关键路径长的工序(组)调度;对于可调度工序直接锁定该工序的加工时间段;对于可调度工序组,则按锁定紧密衔接工序组的前沿贪心策略锁定工序组的加工时间段.由于采用逆序调度和锁定紧密衔接工序组的前沿贪心策略,可使各紧密衔接工序组独立调度,实现紧密衔接紧前工序数无限制的综合调度.     

Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm

Most flexible job shop scheduling models assume that the machines are available all of the time. However, in most realistic situations, machines may be unavailable due to maintenances, pre-schedules and so on. In this paper, we study the flexible job shop scheduling problem with availability constraints. The availability constraints are non-fixed in that the completion time of the maintenance tasks is not fixed and has to be determined during the scheduling procedure. We then propose a hybrid genetic algorithm to solve the flexible job shop scheduling problem with non-fixed availability constraints (fJSP-nfa). The genetic algorithm uses an innovative representation method and applies genetic operations in phenotype space in order to enhance the inheritability. We also define two kinds of neighbourhood for the problem based on the concept of critical path. A local search procedure is then integrated under the framework of the genetic algorithm. Representative flexible job shop scheduling benchmark problems and fJSP-nfa problems are solved in order to test the effectiveness and efficiency of the suggested methodology. Received: June 2005 /Accepted: December 2005     

An optimal dynamic threat evaluation and weapon scheduling technique

Real time scheduling problems demand high level of flexibility and robustness under complex dynamic scenarios. Threat Evaluation (TE) and Weapon Assignment (WA), together TEWA is one such complex dynamic system that has optimal or near optimal utilization of scarce defensive resources, a supreme priority. Several static solutions of TEWA have been proposed. This paper discusses an optimal dynamic multi-air threat evaluation and weapon allocation algorithm using a variant of Stable Marriage Algorithm (SMA). WA uses a new dynamic weapon scheduling algorithm, allowing multiple engagements using shoot-look-shoot strategy, to compute near-optimal solution. For optimality different types of constraints are identified and defined. Testing part of this paper shows feasibility of this approach for a range of scenarios.     

Greedy randomized adaptive search for dynamic flexible job-shop scheduling

Dynamic flexible job shop scheduling problem is studied under the events such as new order arrivals, changes in due dates, machine breakdowns, order cancellations, and appearance of urgent orders. This paper presents a constructive algorithm which can solve FJSP and DFJSP with machine capacity constraints and sequence-dependent setup times, and employs greedy randomized adaptive search procedure (GRASP). Besides, Order Review Release (ORR) mechanism and order acceptance/rejection decisions are also incorporated into the proposed method in order to adjust capacity execution considering customer due date requirements. The lexicographic method is utilized to assess the objectives: schedule instability, makespan, mean tardiness and mean flow time. A group of experiments is also carried out in order to verify the suitability of the GRASP in solving the flexible job shop scheduling problem. Benchmark problems are formed for different problem scales with dynamic events. The event-driven rescheduling strategy is also compared with periodical rescheduling strategy. Results of the extensive computational experiment presents that proposed approach is very effective and can provide reasonable schedules under event-driven and periodic scheduling scenarios.     

知识化制造环境下航空发动机装配线调度及自重构

航空发动机装配工序数量多、工序间装配约束复杂. 当产品需求变化时, 人工调整存在响应速度慢、装配效率低等问题. 以最小化产品完工成本、工序提前期惩罚成本及班组重构成本加权和为目标, 建立了航空发动机装配线调度和装配班组自重构优化模型. 提出一种新的基于工序局部最优排序的分解算法, 将调度问题分解为单个装配组上工序顺序优化问题. 设计了一种工序后向插入搜索策略. 最后提出装配线调度及自重构集成优化算法. 通过数值试验,验证了模型与算法的有效性.     

基于AFDX自适应优先调度算法的实时性分析

通过分析AFDX终端系统关键技术,在AFDX网络虚拟链路的调度策略中提出采用自适应优先调度算法;并分析数据包在终端系统中的处理过程,进行网络演算建模,进而确定出AFDX网络针对不同类型数据的传输速率和服务时延.结果证明该算法较好地满足了航空电子网络数据传输实时性需求,并为AFDX智能网络管理模型中的参数模型和调度策略提...     

计及混合潮流约束的热-电互联综合能源系统 多目标优化调度

为满足多样化能源需求并提高能源网络的可靠性,研究多能源系统优化管理和混合潮流问题.针对多能源的网络约束及其耦合特性,构建整合分布式发电、热电联产、电力网络和区域供热网络的热-电互联综合能源系统模型.基于梯形模糊隶属函数构建模糊化软约束,量化电力网络节点电压和区域供热网络节点供给温度的技术不满意度.考虑系统的经济运行和网络节点的能源供给质量,提出一种计及混合潮流约束的热-电互联综合能源系统多目标优化调度策略,以最小化运行成本和网络节点状态变量的技术不满意度.采用epsilon约束算法精确求解该多目标优化问题的Pareto前沿.算例分析结果表明,所构建的模型和提出的算法可以有效提高系统能源供给质量和优化决策的准确性.研究成果进一步体现了所提出的多目标优化方案在兼顾经济性、能源供给质量以及复杂的运行约束,保证系统经济稳定运行等方面的效益.