基于拟关键路径的二车间综合调度算法

针对如何将复杂产品工序有效地分配到具有相同设备资源的二车间加工的问题,提出了基于拟关键路径法的二车间综合调度算法。为了让二车间负载平衡并进行充分的并行处理, 尽早结束产品加工,该算法按拟关键路径法(ACPM)对工序排序,再采取二车间加工结束时间接近的预调度策略进行调度。为了减少二车间工序的迁移次数,该算法将入度不小于2的工序放入其紧前工序分配较多的车间;将入度小于2且其紧后工序的入度不小于2的工序分配到能让其尽早结束的车间;对于其他唯一紧前紧后工序与其叶子节点所形成的工序串按预调度策略进行整串调度。实例表明,该算法可以在二次复杂度内较优地实现具有相同设备资源的二车间分布式综合调度。     

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

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

工件工序可并行的作业车间调度模型与求解

针对传统作业车间调度模型没有考虑工件工序存在并行性的不足,提出一种以最小化完工时间为目标的工件工序可并行作业车间调度模型,且在模型中考虑了工序加工设备柔性;设计了基于遗传算法的调度算法,其中染色体编码采用分段编码方式,并提出一种适用于工件工序存在并行性的染色体解码方法.实验结果表明,文中算法能够有效地解决工件工序可并行的作业车间调度问题.     

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

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

基于机床超低待机状态的流水车间能耗调度

为降低流水车间能源消耗,引入一种数控机床的超低待机状态,相比于将数控机床待机状态切换为停机状态的节能研究,可在不停机情况下降低数控机床加工间隔状态的功率,避免数控机床频繁启停.针对流水车间加工状态、待机状态及超低待机状态三元调度问题,提出基于工序平移的混合遗传算法,分别定义了不同的工序邻域移动操作,实现数控机床待机状态向超低待机状态和停机状态的转化,形成主动节能调度策略,提升遗传算法求解考虑超低待机状态的流水车间调度问题的优化能力.实验研究表明,启用超低待机状态能够降低流水车间10%以上的能耗,且基于工序平移的混合遗传算法求解考虑超低待机状态的流水车间调度问题性能优于遗传算法.     

求解柔性机器人车间调度问题的混合蚁群算法

在柔性作业车间调度问题的基础上,考虑多台搬运机器人执行不同工序在不同机床之间的搬运,形成柔性机器人作业车间调度问题,提出混合蚁群算法。用改进析取图对问题进行描述,使用混合选择策略、自适应伪随机比例规则和改进信息素更新规则优化蚁群算法,结合遗传算子完成机床选择和工序排序。使用一种多机器人排序算法完成搬运机器人分配和搬运工序排序。通过多组算例仿真测试并与其他算法进行比较,验证了算法的有效性和可靠性。     

相关工件车间调度问题的拓扑算法

针对加工装配型离散制造企业实际生产的特点,提出了一类用于表示工序之间偏序关系的相关工件车间调度问题。为了利用已有的求解表示工序之间的线序关系的传统车间调度算法求解相关工件车间调度问题,设计了一种拓扑算法,该算法能够将工序之间的偏序关系转化为线序关系,将相关工件车间调度问题转化为传统的车间调度问题,通过实证研究,结果表明了拓扑算法是可行和高效的。     

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

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

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

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

混合流水车间提前/拖期调度问题的DE优化解

针对JIT生产模式下的混合流水车间调度问题特点,提出了采用DE算法与指派规则联合调度策略求解流水车间提前/拖期调度问题。构建了混合流水车间的提前/拖期调度模型。详细论述了DE算法的实施流程和关键问题。在算法实施过程中,首先,采用DE算法进行全局寻优,完成生产任务指派,确定某个工件在某个工序在哪个工位加工;然后采用局部指派规则来确定工件在该工序的开工时间。在满足目标完成时间(交货期)的前提下,使提前惩罚费用与拖期惩罚费用之和最小。数值计算结果证明了该算法的有效性。     

Hadoop集群环境下集成抢占式调度策略的本地性调度算法设计

在Hadoop集群环境下本地性调度算法是提高数据本地性的算法。本地性调度算法的调度策略的本质是提高数据本地性,减少网络传输开销,避免阻塞。但是由于Map任务的完成时间不同,Reduce任务存在的等待现象影响了作业的平均完成时间,使得作业的完成时间增加,进而引起系统的性能参数不佳。因此提出在保留原算法数据本地性要求的基础上集成可抢占式的调度方法。在Reduce任务等待时,挂起该任务并释放资源给其他Map任务,当Map任务完成到一定程度后,重新调度Reduce任务。基于上述调度策略设计了集成抢占式策略的本地性调度。为了对改进的算法进行验证,通过实验对本地性调度算法和集成抢占式本地性调度算法进行比较。实验结果表明,在相同数据上,集成抢占式本地性调度算法的平均完成时间有明显的降低。     

A Case Study on Integrated Production Planning and Scheduling in a Three-Stage Manufacturing System

This paper presents an integrated optimization model of production planning and scheduling for a three-stage manufacturing system, which is composed of a forward chain of three kinds of workshops: a job shop, a parallel flow shop consisting of parallel production lines, and a single machine shop. As the products at the second stage are assembled from the parts produced in its upstream workshop, a complicated production process is involved. On the basis of the analysis of the batch production, a dynamic batch splitting and amalgamating algorithm is proposed. Then, a heuristic algorithm based on a genetic algorithm (known as the integrated optimization algorithm) is proposed for solving the problem. Note to Practitioners-This paper presents a method for integrated production planning and scheduling in a three-stage manufacturing system consisting of a forward chain of three kinds of workshops, which is common in such enterprises as producers of automobiles and household electric appliances, as in the case of an autobody plant usually with the stamping workshop, the welding and assembling workshop, and the painting workshop. Herein, the production planning and scheduling problems are simultaneously addressed in the way that a feasible production plan can be obtained and the inventory reduced. A batch splitting and amalgamating algorithm is proposed for balancing the production time of the production lines. And a case study of the integrated planning and scheduling problem in a real autobody plant verifies the effectiveness of our method     

异构分布式实时系统的容错优化调度算法

针对分布式实时系统,在分析了单处理调度算法的基础上,结合版本复制技术和首次适应方法,给出了一种容错调度算法。分析了算法的可调度性,给出任务的可调度性条件。在满足任务容错可调度的情况下,以提高处理器的利用率为目标,对基版本时限进行了优化,给出了基版本优化时限的求取算法。仿真结果表明,本文算法将可以得到比FTEDFFF和FTRMFF更高的处理器利用率。     

一个新的相关任务调度算法

现已有许多调度算法在某些特定条件下能产生最优调度。Darbha和Agrawal提出的TDS算法能产生最优调度，其最优条件比较苛刻，实用性不强。Park和Choe提出一种扩展调度算法（Extended TDS），虽然其最优条件比TDS算法的约束条件宽松些，但在任务数较多时难以满足，并且形式过于复杂。因此，本文提出一种能产生最优调度的新算法，该算法既考虑合并其它父任务以减少通讯时间，同时尽可能少地合并其它任务，从而尽量减小任务的启动时间。该算法不仅最优条件简单、宽松，而且具有与TDS算法相同的时间复杂度O（v^2）。     

基于窗口的印刷车间作业动态调度研究

为了解决实际印刷车间突发设备故障和紧急插单问题,采用滚动窗口技术结合遗传算法的方法,建立适合实际印刷车间生产的动态再调度模型;设定若干印品订单、机器设备的加工工序以及各工序加工时间、工序约束条件等,以订单的最大最小加工时间和再调度的偏离度为多目标优化,采用周期与事件混合驱动策略,将滚动窗口再调度机制和遗传算法相结合进行流程设计和编码,构建印刷车间再调度模型;采用标准问题FT06和FT01验证了文章设计的模型算法的有效性和可行性;运行程序,模拟正常加工时紧急插单和机器故障突发时,系统生产新的调度计划即调度甘特图,仿真结果表明该动态调度模型可以用于印刷作业的正常排产调度,在遇突发状况时可生成稳定、符合交货日期的再调度方案。     

单调速率及其扩展算法的可调度性判定

任务可调度性判定是实时系统调度理论研究的核心问题.单调速率(RM)算法是实时调度的重要算法,自其提出以来已被广泛研究.然而到目前为止,尚缺乏专题性的文章来系统而深入地探讨RM及其扩展算法的可调度性判定,以及各种现实条件和实现方式(包括任务调度的时间开销和任务同步问题等)对可调度性的影响.围绕RM算法下的可调度性判定问题,由浅入深,系统性地讨论各种不同假设和实现方式对可调度性的影响,具体为下述3大类问题：（1）理想的RM算法下的可调度性判定的CPU利用率最小上界最小及可调度的充分必要条件;（2）考虑调度时间开销情况下的可调度性判定条件;（3）优先级反转协议及其对可调度性的影响.给除了具体实例来叙述上述问题,并从算法复杂度和可检测率两方面比较各种算法的优劣。     

A new algorithm for complex product flexible scheduling with constraint between jobs

In order to simplify the complex product flexible scheduling problem with constraint between jobs, a new hierarchical scheduling algorithm based on improved processing operation tree is presented. Aiming at the routing problem, short-time strategy and machine-balance strategy are adopted to assign each operation to a machine out of a set of machines. And in order to solve the sequencing problem, the allied critical path method is first adopted to confirm the scheduling sequence of operations, and then operations are divided into dependent operations and independent ones according to their characteristics. For the dependent operations, forward greedy rule is adopted in order to make the completion time of operation as soon as possible and the scheduling algorithm of shortening idle time is adopted by analyzing the characteristics of the independent operations. Experiment shows that the proposed algorithm solves for the first time the complex product flexible scheduling problem with constraint between jobs.     

求解柔性作业车间调度问题的两段式狼群算法

针对以最小化最大完工时间为目标函数的柔性作业车间调度问题,建立其数学模型并提出了一种两段式狼群算法加以求解。采用两段式（two-vector code）的编码方式,设计初始化种群的方式,保证初始解的质量及多样性;通过对原始狼群算法中游走行为、召唤行为、围攻行为的重新设计,解决了原始狼群算法易陷入局部最优的问题;舍弃原始狼群算法中的距离判定因子,来降低算法的复杂度。对车间两个实例进行仿真测试和算法比较,验证了所提算法求解该问题的有效性,为其解决柔性作业车间调度问题提供了一种更加有效的方法。     

Intelligent scheduling of a feature-process-machine tool supernetwork based on digital twin workshop

Modern manufacturing enterprises are shifting toward multi-variety and small-batch production. By optimizing scheduling, both transit and waiting times within the production process can be shortened. This study integrates the advantages of a digital twin and supernetwork to develop an intelligent scheduling method for workshops to rapidly and efficiently generate process plans. By establishing the supernetwork model of a feature-process-machine tool in the digital twin workshop, the centralized and classified management of multiple data types can be realized. A feature similarity matrix is used to cluster similar attribute data in the feature layer subnetwork to realize rapid correspondence of multi-source association information among feature-process-machine tools. Through similarity calculations of decomposed features and the mapping relationships of the supernetwork, production scheduling schemes can be rapidly and efficiently formulated. A virtual workshop is also used to simulate and optimize the scheduling scheme to realize intelligent workshop scheduling. Finally, the efficiency of the proposed intelligent scheduling strategy is verified by using a case study of an aeroengine gear production workshop.