考虑串行工序紧密度的择时综合调度算法

针对目前综合调度算法在处理一般综合调度问题时为了兼顾加工工艺树中工序的并行处理,忽略串行工序之间紧密度,影响调度结果的问题,提出考虑串行工序紧密度的择时综合调度算法。该算法提出工序序列排序策略,从工艺树的整体结构出发,将其划分成内部工序只具有串行关系的工序序列,根据工序序列的长短确定其调度顺序;提出择时调度策略,结合工艺树自身特点,为调度工序选择若干合法加工时间点,分别在每个时间点调度工序,得到该工序的试调度方案集合,从其中选择加工总用时最小的方案作为工序调度方案,若不唯一,则选择工序加工时间最早的方案。实例表明,该算法既保证并行工序的并行处理,又有效提高串行工序的紧密度,优化了综合调度的结果。     

基于交货期紧迫度的综合调度算法

为解决开始时间与交货期都不相同的多品种小批量复杂产品综合调度问题,提出基于交货期紧迫度的综合调度算法。该算法根据产品加工的开始时间由前到后排序调度;当存在多产品开始时间相同时,根据产品优先加工的紧迫度,确定它们的调度次序;如果存在紧迫度相同的产品,将按交货期由早到晚排序调度;若交货期也相同,则将它们虚拟成一个产品统一调度;对被调度产品采用长路径策略和短用时策略确定其各工序的调度次序,并结合设备工序紧凑法确定工序的开始时间。该算法结合产品紧迫度和设备工序紧凑法的优点,使开始时间不同的多产品在尽量减少设备空闲时间的情况下,按交货期完工。理论分析和实例表明,该算法可在二次复杂度内给出较合理的综合调度方案。     

柔性作业车间动态调度方法研究

针对一类复杂工序的柔性作业车间的动态调度问题,提出了一种基于工序树的调度方案及算法。调度算法中采用多叉树形式的工序树,工序树是一种适用于作业车间调度的柔性工艺规划描述方法,工序树经过泛化和变形可以涵盖多种具体的工序样式。调度算法通过通信网络实时地获取加工车间中设备的工作状态,结合加工任务中所有产品的状态变迁,依据由加工任务的约束条件预先确定的优先调度规则,动态地生成加工任务作业进程表。算法实例的结果验证了调度方案及算法的有效性。     

存在设备无关延迟约束的综合柔性调度算法

针对加工和装配综合的柔性调度中忽略工序间存在设备无关延迟约束导致调度结果不精确的问题,提出存在设备无关延迟约束的综合柔性调度算法。该算法通过将设备无关延迟时间转换为设备无关延迟工序,提出存在设备无关延迟约束的综合柔性调度工艺模型;通过将设备无关延迟约束工序转换为顺序约束工序的策略,将存在设备无关延迟约束的柔性加工问题转换为一般柔性加工问题;对一般柔性加工问题采用短用时策略和设备均衡策略确定标准工序的加工设备,将一般柔性加工问题简化为一般综合调度问题并用长路径优先策略调度;对于路径长度相等且在同一设备上加工的标准工序,提出调度前续短路径策略选择调度工序。实例表明,该算法通过考虑设备无关延迟约束时间使综合柔性调度的结果更精确并且能减少产品总的加工时间。     

加工工序非紧密衔接的车间调度策略

针对以往车间调度算法忽略非紧密衔接工序调度,从而导致调度结果不精确这一情况,提出了一种考虑工序间空闲时间延迟约束的调度策略,即解决加工工序非紧密衔接调度问题的方法。该方法在对由延迟约束造成的工序非紧密衔接型调度问题进行定义和研究的基础上,提出了标准工序、延迟工序和扩展加工工艺树概念。设计了一种将延迟约束转换为顺序约束的转换策略,使得转换后的非紧密衔接工序变为虚拟紧密衔接工序,并可采用经典车间调度算法调度。实例验证表明,该调度策略可有效地解决非紧密衔接工序调度问题,可在不增加算法复杂度的情况下,得到更为实用的调度方案。     

基于设备空闲事件驱动的综合调度算法

针对基于拟关键路径法(Allied criticai path method,ACPM)的综合调度算法按路径长度确定工序的调度次序,形成工序组间的并行处理,使设备产生较多空闲时间的问题,提出基于设备空闲事件驱动的综合调度算法.该算法主要是根据空闲设备选择加工工序,思路是以每次工序加工结束作为一次设备空闲事件,驱动空闲设备进行一次可调度工序的寻找:如果可调度工序唯一,则调度此工序;如果可调度工序不唯一,选择父结点路径长的工序;如果父结点最长路径相同,选择用时短的工序.由于该算法在调度工序时不考虑工序序列且以设备空闲驱动,使得该算法按工序并行处理且能充分利用设备空闲时间,避免基于ACPM法产生较多设备空闲时间的问题.另外,由于该算法无需判断空闲时间段的大小、相同设备间的使用均衡和无需空闲设备频繁检测可调度工序,可节约大量的判断操作.实例表明所提出的算法不仅比系列ACPM法设备利用率都高,而且简便可行.     

前移存在调整时间综合调度工序的算法

针对目前存在调整时间的综合调度算法只考虑快速插入调整时间实现调度方案,没有考虑调整时间会随工序次序改变影响调度结果的问题,提出通过改变工序调度次序前移存在调整时间综合调度工序的算法。该算法在保证相关工序不后移的条件下,通过改变相同加工设备上具有相同工艺紧后工序的工序调度次序,从而改变工序之间的调整时间,使调整工序最晚结束时间提前,使其工艺紧后工序开始时间有可能提前,从而实现提高设备利用率,提前产品最终完工时间。实例表明该算法可获得存在调整时间的综合调度问题的更优解。     

非紧密衔接工序动态车间调度算法

对于实际生产中经常出现的非紧密衔接工序调度问题,提出一种将非紧密衔接工序变为紧密衔接工序的转换策略,用该策略在对工序间延迟约束进一步研究的基础上,提出标准工序、延迟工序和扩展加工工艺树概念.通过对拟关键路径法和最佳适应调度法算法进一步完善,设计一种通过优先调度延迟工序,对标准工序分批采用拟关键路径法和最佳适应调度法,同时考虑关键设备上标准工序尽量紧凑的具有非紧密衔接工序的动态调度算法.实例验证表明,所提出的调度算法不仅能够较好地解决更具实际意义的动态非紧密衔接工序调度问题,而且能够扩展解决动态紧密衔接工序调度问题.     

基于零件虚拟工序队列的FMS动态调度研究

提出虚拟工序队列的概念,并在此基础上提出一种基于静态零件分批（静态调度）的ＦＭＳ动态生产调度方法,该算法充分考虑到ＦＭＳ的系统资源限制及零件运输等环节,能较好地解决生产调度中的设备负荷平衡,系统紧急事件发生（如机床故障,新零件加工等）,可替代加工工序等问题,且易于实现,具有较广泛的适应性。     

基于择时的二车间综合调度算法

针对现有二车间综合调度算法在处理具有相同设备资源的二车间综合调度问题时,注重工艺树的横向并行处理,忽略纵向串行工序之间的紧密度,将二车间均衡处理或减少工序迁移次数一并做为调度目标导致不必要时间开销的问题,提出了基于择时的二车间综合调度算法。同时,提出了工序序列排序策略,将加工工艺树划分为若干工序序列,并根据其路径长度确定调度次序;提出了二车间择时调度策略,为工序寻找加工开始时间和加工车间,生成使当前部分产品加工总用时最小的工序调度方案。若该方案不唯一,则选择在二车间中该工序加工结束时间最早的工序调度方案。所提算法既保证了并行工序的并行处理,又有效地提高了串行工序的紧密度,避免了无效工序迁移带来的时间开销。通过实例说明了所提算法的有效性。     

2个加工时间不同工序组批的嵌套批综合调度算法

针对已有的批加工工序数为2的批综合调度算法,没有考虑组批工序不同和后续工序中存在组批工序的情况,不能适用于更复杂的批综合调度问题,提出求解2个加工时间不同工序组批的嵌套批综合调度算法。该算法根据批处理工序加工时间不同的特点,定义串行衔接时间和并行衔接时间;提出判断组批的余差比较策略;当可与等待工序一同批处理的工序不唯一时,采用组批前移最大化策略确定组批处理工序;当准备组批处理工序的后续工序中存在组批工序时,在余差比较策略中加入嵌套优化策略确定该工序是否组批;由于组批工序的后续工序较多且对调度结果影响较大,采用前续工序优先策略使组批工序尽早加工。理论分析和实例表明,提出的算法可解决2个加工时间不同工序组批的嵌套批综合调度问题。     

NEW NONSTANDARD JOB SHOP SCHEDULING ALGORITHM

Considering the complex constraint between operations in nonstandard job shop scheduling problem （NJSSP）, critical path of job manufacturing tree is determined according to priority scheduling function constructed. Operations are divided into dependent operations and independent operations with the idea of subsection, and corresponding scheduling strategy is put forward according to operation characteristic in the segment and the complementarities of identical function machines. Forward greedy rule is adopted mainly for dependent operations to make operations arranged in the right position of machine selected, then each operation can be processed as early as possible, and the total processing time of job can be shortened as much as possible. For independent operations optimum scheduling rule is adopted mainly, the inserting position of operations will be determined according to the gap that the processing time of operations is subtracted from idle time of machine, and the operation will be inserted in the position with minimal gap. Experiments show, under the same conditions, the result that operations are scheduled according to the object function constructed, and the scheduling strategy adopted is better than the result that operations are scheduled according to efficiency scheduling algorithm.     

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

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

A Genetic Algorithm Approach to the Scheduling of FMSs with Multiple Routes

Usually, most of the typical job shop scheduling approaches deal with the processing sequence of parts in a fixed routing condition. In this paper, we suggest a genetic algorithm (GA) to solve the job-sequencing problem for a production shop that is characterized by flexible routing and flexible machines. This means that all parts, of all part types, can be processed through alternative routings. Also, there can be several machines for each machine type. To solve these general scheduling problems, a genetic algorithm approach is proposed and the concepts of virtual and real operations are introduced. Chromosome coding and genetic operators of GAs are defined during the problem solving. A minimum weighted tardiness objective function is used to define code fitness, which is used for selecting species and producing a new generation of codes. Finally, several experimental results are given.     

可调加工时间炼钢-连铸的灰狼优化调度算法

炼钢-连铸(SCC)是钢铁生产中的瓶颈,SCC生产过程中最后一个阶段的加工时间可调。可调加工时间SCC调度问题是NP难组合优化问题,高质量的SCC调度算法可以较大地提高生产效率。基于问题特征,研制了求解该问题的高效灰狼优化(GWO)算法。首先设计了新的解码方法对解进行解码。同时提出了种群初始化方法,以得到具有一定质量和多样性的初始种群。其次,研制了一种基于多操作的搜索算子,该算子包含3种不同操作,在一定程度上实现了GWO算法的集中性和多样性的平衡。此外,设计了重启操作,以提高GWO算法的多样性。对比实验说明了基于多操作的搜索算子的有效性。此外,与4种有效调度方法的对比说明了GWO算法的高性能和优越性。     

基于数字孪生的多自动导引小车系统集中式调度

针对具有多辆自动导引小车的多机器人存取系统在分布式调度时系统性能不明确、优化程度低的难题,提出一种基于数字孪生的集中式调度方法.建立了以物理系统、虚拟系统、孪生数据中心和系统支撑服务为核心的数字孪生模型,提出物理系统接收指令和采集数据机制、虚拟系统方案生成与仿真机制、孪生数据中心数据处理和对比机制,并基于系统支撑服务确...     

Heuristics for assembly operation scheduling problem in flexible assembly systems

In this paper we address the problem of scheduling n assembly operations with in-tree constraints on m unrelated parallel workstations in flexible assembly systems, which we call the assembly operation scheduling problem (AOSP). No preemption of assembly operations is allowed and the primary objective is to minimize the maximum completion time. This problem is equivalent to R|tree|C_max. For this notorious NP-hard problem, four heuristic algorithms including decomposition (DECOMP), earliest completion time (ECT), shortest processing time (SPT), and earliest starting time(EST) heuristic are proposed and their performances are comparatively investigated. DECOMP uses a decomposition technique to practically solve this problem. The assembly operation tree is decomposed and then AOSP is reduced to a set of subproblems of R||C_max and R,r_j|r_i|C_max. Two efficient heuristics were proposed for the reduced subproblems. The other three heuristics basically use the machine selection rules to determine the machine for processing the current operation. Of these heuristics, DECOMP showed the best performance in terms of quality of schedule. Computational results show that all the proposed algorithms except the EST heuristic perform quite well in terms of both quality of solution and computation time.     

Production planning in virtual cell of reconfiguration manufacturing system using genetic algorithm

This paper focuses on the scheduling problem of the reconfiguration manufacturing system (RMS) for execution level, where the final objective is to output a production plan. The practical situation in Chinese factory is analyzed, and the characteristics are summarized into the contradiction between flow and job shop production. In order to handle this problem, a new production planning algorithm in virtual cells is proposed for RMS using an improved genetic algorithm. The advantages of this algorithm have three parts: (1) the virtual cell reconfiguration is formed to assist making production plans through providing relationship among task families and machines from cell formation; (2) The operation buffer algorithm is developed for flow style production in cells, which can realize the nonstop processing for flow style jobs; and (3) The multicell sharing method is proposed to schedule job shop jobs in order to fully utilize manufacturing capability among machines in multicells. Based on the above advantages, an improved genetic algorithm is developed to output scheduling plan. At last, the algorithm is tested in different instances with LINGO and the other genetic algorithm, and then the scheduling solution comparison shows the proposed algorithm can get a better optimum result with the same time using the comparison algorithm.