基于集束搜索和银行家算法的柔性制造系统无死锁调度

本文提出了一种基于启发式规则的无死锁调度算法,该算法基于集束搜索方法,局部评价函数和全局评价函数,在无缓冲区的情况下,采用单步前瞻的银行家算法来避免死锁。该算法可以迅速解决复杂制造系统的死锁和调度问题,折衷了计算时间的消耗和调度结果的质量。     

基于Petri网的柔性制造系统无死锁遗传调度算法

对以最小化加工时间为目标的柔性制造系统无死锁调度问题, 提出了一种遗传调度算法. 算法考虑到同类工件具有预先确定的相同加工路径, 而各工序的处理时间与工件有关. 用Petri网对工序和资源分配进行逻辑建模,利用遗传算法, 采用工序自然编码方式, 基于系统的最佳避免死锁Petri网控制器, 检测染色体的可行性, 修复不可行染色体使其对应的调度满足资源约束和无死锁控制约束, 从而保证算法所利用的所有染色体都对应系统的可行调度. 仿真结果表明了算法的可行性和有效性.     

光刻机的防死锁调度

半导体生产线是目前世界上公认的最复杂的制造系统之一。光刻机是半导体晶圆制造的瓶颈设备,其费用相当昂贵。光刻机由若干个自动组合装置组成,如果调度不当,生产可能会出现死锁。死锁的发生不仅大大降低光刻机的效率,而且破坏晶圆质量。本文利用图论的算法编制软件并进行仿真可以得到无死锁的调度方案。     

柔性制造系统的改进粒子群无死锁调度算法

基于柔性制造系统的Petri网模型,以制造期最小为优化目标,将死锁避免策略嵌入粒子群算法中,提出一种无死锁改进粒子群调度算法.该算法将粒子与工件的工序序列相对应,以位置数值的大小表示对应工件工序在执行顺序中的优先级.采用一步向前看的死锁避免策略方法对序列的可行性进行验证,提出一种跳出局部极值的策略.实例仿真结果表明了粒子群调度算法的可行性和有效性,以及改进粒子群调度算法的优越性.     

可重入柔性流水车间有限缓冲区容量动态预留方法

当制造企业的生产车间缓冲区容量有限时,如果同时存在可重入工序,会产生一种严重的生产阻塞现象,即死锁现象,该现象会严重影响整个生产进程.本文首先建立具有可重入工序的柔性流水车间有限缓冲区排产(RFFLBS)问题的数学模型,在对死锁现象系统分析的基础上,提出了一种基于马尔可夫链的有限缓冲区动态容量预留方法(DBRMMC), DBRMMC通过主动为折返重入的工件预留缓冲区容量,减少工件对缓冲区资源的竞争,降低死锁现象出现的概率,并通过在DBRMMC方法中引入基于自适应阈值二值化算法的偏差补偿措施减小预测偏差,进一步抑制死锁现象的出现,并与基于高响应比优先算法(HRRN)的局部指派方法结合,给出一种改进的基于马尔可夫链的有限缓冲区容量动态预留方法(IDBRMMC-HRRN).建立多组仿真方案在不同数据规模下的进行测试,仿真结果表明IDBRMMC-HRRN方法能够有效的降低具有可重入工序的柔性流水车间有限缓冲区排产过程中死锁现象出现的概率,给出合理可行的排产结果.     

自动生产单元的无死锁调度策略

本文针对一类无中间缓冲区的自动生产单元,提出了一种基于遗传算法的调度方法;为了保证由遗传运算生成的调度策略能满足所要求的约束条件,在适应度计算中添加了惩罚项以避免搜索过程收敛于不可行解;仿真实例证明了本文中的方法不仅能够得到可行的调度策略,而且能够使得系统达到较好的性能指标.     

一种分布式计算环境下并行应用的调度算法

在网络上运行并行程序不像在并行机上那样可靠,因此对于关键应用需要在应用级保证消息传输的可靠性.人们对以异步方式进行通信的并行程序的调度问题提出了大量的启发式算法,但是它们所产生的调度结果不能用于以同步方式通信的并行程序.提出的PRGSC算法可以防止由同步通信所引起的死锁问题,而且可以降低同步通信所带来的时延的影响.形式化地证明了死锁检测算法的正确性,并通过仿真实验说明了PRGSC算法有很好的调度质量.     

知识化制造系统中动态调度的自适应策略研究

针对知识化制造系统中的动态调度问题，结合知识化制造单元的高智能特征，提出了B-Q学习算法．并基于该算法构建了一种自适应调度控制策略．针对知识化制造系统运行过程中系统状态空间较大的特点，通过提取系统状态特征，对系统状态进行合理聚类，有效地降低了系统状态空间的复杂性．根据系统当前所处的瞬时状态．选取不同的调度规则对缓冲区中工件进行有效调度．仿真结果验证了所提出调度控制策略的有效性．     

一种新型混合算法在混流装配调度中的应用

针对含有缓冲区的混流装配中同时存在的生产成本和库存成本问题,提出了一种基于遗传算法和差分进化算法的混合框架,并将其用于混流装配调度的实际问题中。通过融合遗传算法有效处理离散变量及差分进化算法有效处理连续变量的优点,在综合考虑降低生产成本和缓冲区库存的同时,兼顾了每个型号产品生产的顺序及数量。计算机仿真结果表明,与传统算法相比,该算法在混流装配调度上具有收敛速度快、优化能力强、算法可靠等优势。该混合算法可以显著改善多参数、高度非线性问题的优化结果,提高计算效率。     

JSP问题的遗传算法解决途径

针对车床作业调度问题,讨论了应用于车床作业调度的遗传算法设计,给出了主要的编码、解码、以及死锁问题的算法模型。结合应用实例．说明了设计的可行性与有效性。     

Deadlock-free scheduling strategy for automated production cell

Deadlock must be avoided in a manufacturing system. In this paper, an efficient algorithm for finding a good deadlock-free schedule in a manufacturing system with enough (sufficient) or limited buffer is presented. This algorithm is based on the effective genetic algorithm (GA) search method. A formal Petri net structure is introduced, and the token player is used to assure deadlock freeness. In order to make the scheduling strategy generated by GA meet the required deadlock-free constraint, a Petri net is involved in checking the implementation of a manufacturing system during the job-scheduling process. The effectiveness and efficiency of the proposed approach is illustrated by several examples.     

Deadlock-free scheduling for flexible manufacturing systems using Petri nets and heuristic search

Deadlock-free control and scheduling are two different problems for flexible manufacturing systems (FMSs). They are significant for improving the behaviors of the systems. Based on the Petri net models of FMSs, this paper embeds deadlock control policies into heuristic search algorithm, and proposes a deadlock-free scheduling algorithm to minimize makespan for FMSs. Scheduling is performed as heuristic search in the reachability graph of the Petri net. The searching process is guided by a heuristic function based on firing count vectors of state equation for the Petri net. By using the one-step look-ahead method in the optimal deadlock control policy, the safety of a state is checked. Experimental results are provided to show effectiveness of the proposed heuristic search approach in deadlock-free scheduling for FMSs.     

Hybrid heuristic search approach for deadlock-free scheduling of flexible manufacturing systems using Petri nets

Based on the Petri net models of flexible manufacturing systems (FMSs), this paper focuses on deadlock-free scheduling problem with the objective of minimizing the makespan. Two hybrid heuristic search algorithms for solving such scheduling problems of FMSs are proposed. To avoid deadlocks, the deadlock control policy is embedded into heuristic search strategies. The proposed algorithms combine the heuristic best-first strategy with the controlled backtracking strategy based on the execution of the Petri nets. The scheduling problem is transformed into a heuristic search problem in the reachability graph of the Petri net, and a schedule is a transition sequence from the initial marking to the final marking in the reachability graph. By using the one-step look-ahead method in the deadlock control policy, the safety of a state in the reachability graph is checked, and hence, deadlock is avoided. Experimental results are provided and indicate the effectiveness of the proposed hybrid heuristic search algorithms in solving deadlock-free scheduling problems of FMSs. Especially, the comparison against previous work shows that both new algorithms are promising in terms of solution quality and computing times.     

Petri net modeling and scheduling for cyclic job shops with blocking

Cyclic scheduling is an effective scheduling method in the repetitive discrete manufacturing environment. We investigate the scheduling problem for general cyclic job shops with blocking where each machine has an input buffer of finite capacity. We develop Petri net models for the shops. We propose a sequential buffer control policy that restricts the jobs to enter the input buffer of the next machine in a specified sequence. We show that the scheduling model of a cyclic shop with finite buffers under such a buffer control policy can be transformed into a scheduling model of a cyclic shop with no buffer that can be modeled as a timed marked graph. In addition, we characterize the structural properties for deadlock detection. Finally, we present a mixed integer programming model to find an optimal deadlock-free schedule that minimizes the cycle time.     

星形图上无死锁的路径算法

星形图具有许多良好的拓扑性质，是一种有可能替代传统的超立方体的并行计算互联网络的模型。在本文中，作者针对在星形图这样一种高度规则的网络中，可能产生死锁的问题，对星形图上无死锁的路径算法进行了研究。首先利用星形图中匹配基的性质，给出了从Ｓｎ（Ｂ）到Ｓｋ的正规映射的定义，然后提出了星形图上的两个无死锁受限条件，最后证明了一个满足无死锁受限条件的路径算法。作者还提出了星形图上路径算法的最小无死锁受限条件     

Deadlock-free genetic scheduling algorithm for automated manufacturing systems based on deadlock control policy

Deadlock-free control and scheduling are vital for optimizing the performance of automated manufacturing systems (AMSs) with shared resources and route flexibility. Based on the Petri net models of AMSs, this paper embeds the optimal deadlock avoidance policy into the genetic algorithm and develops a novel deadlock-free genetic scheduling algorithm for AMSs. A possible solution of the scheduling problem is coded as a chromosome representation that is a permutation with repetition of parts. By using the one-step look-ahead method in the optimal deadlock control policy, the feasibility of a chromosome is checked, and infeasible chromosomes are amended into feasible ones, which can be easily decoded into a feasible deadlock-free schedule. The chromosome representation and polynomial complexity of checking and amending procedures together support the cooperative aspect of genetic search for scheduling problems strongly.     

光刻设备TRACK系统的无死锁调度算法

为使半导体生产线光刻设备的TRACK系统正常运行,有效的避免死锁,提高设备利用率,提出一种无死锁调度算法,在不会引发死锁的条件下为需要调度的工件确定加工组件,同时考虑到组件发生故障的情况,及时排除故障的影响,并通过仿真证明了算法的有效性。     

星形图上最小无死锁受限条件及无死锁路径算法

针对是形图中台能产生死锁的问题，对星形图上无无线锁的路径算法进行了研究，得到了星形图上的两类最小无死锁受限条件，并给出了一个满足该两类最小无死锁受限条件的无死锁路径算法。同时还证明了文献中提出的两个死锁受限条件分别只是该文所提出的两类最小无死锁受限条件的一个特例。