基于Petri网的组合设备建模与调度综述

组合设备是半导体晶圆制造的核心装备,其调度与控制优化是半导体制造领域极具挑战性的课题. Petri网因其强大的建模能力和简约的图形化表达优势,被广泛地应用于组合设备的建模与调度.对基于Petri网的组合设备建模与调度方法进行综述,归纳总结了组合设备的结构类型、晶圆流模式、调度策略及Petri网建模方法,并系统阐述组合设备的7类典型调度问题,包括驻留时间约束、作业时间波动、晶圆重入加工、多品种晶圆加工、加工模块(Process module, PM)故障、PM清洗和组合设备群.最后,讨论了当前组合设备调度存在的挑战及后续可能的研究方向.     

稳态调度下单臂组合设备时间延迟分析与优化

在半导体晶圆制造过程中,驻留时间延迟过长对晶圆质量具有消极影响.本文研究单臂组合设备稳态调度中如何合理地分配机械手等待时间,抵消驻留时间延迟的问题.首先,采用Petri网模型描述晶圆制造过程,分析了单臂组合设备稳态调度的时间特性,获得了稳态下工序驻留时间延迟计算表达式.其次,通过解构机械手等待时间对驻留时间延迟的影响机理,提出了一种机械手等待时间分配优先级规则.进一步,将虚拟瓶颈工序用于辅助分配机械手等待时间,结合优先级规则,提出了一种单臂组合设备稳态调度启发式算法.最后,通过例子验证了算法的可行性与有效性.与传统拉式策略和尽早加工策略对比,该算法能有效地减少单臂组合设备稳态调度下的驻留时间延迟并能满足晶圆制造的严格要求.     

基于蚁群算法的电梯群控调度优化策略研究

为了研究多台电梯的群控调度问题,并根据现有电梯调度策略的不足,建立以服务间和运行能耗为优化目标函数的调度模型,提出将电梯群控调度问题转化为离散组合优化问题,并利用蚁群优化算法求解。算法在接受众多乘客的随机请求下,能根据各电梯的运行现状,将不同层的乘客请求组合分配到相应电梯进行服务的最优调度方案,优化了群控电梯的运行模式,仿真实验证明算法能大幅度减少乘客的平均侯梯时间及缩短运行路径,证明了算法的有效性。     

自适应蚁群优化算法在物流调度中的应用研究

供应链中的物流过程可作为一个调度问题进行研究,物流过程的调度是一个组合优化问题.首先对物流过程进行分析,建立物流调度的数学模型,提出了基于自适应蚁群优化的物件调度算法,实现供应链物流过程中物件的动态分配.最后试验结果表明,使用自适应蚁群优化策略测试不同的订单组合,得到一个优化解决方案,该方案能使尽可能多的定单按时交付,同时也能将订单的延迟减小.     

应用离散事件系统控制理论求解生产调度的新方法

众所周知, 生产调度问题属组合优化问题, 一般来说不存在求得精确最优解的多项式算法. 因此, 对于大规 模调度问题, 人们应用启发式算法和元启发式算法以企求得满意解. 在实际的应用中, 许多工业过程需要满足严格 的工艺约束. 对于这类过程的调度问题, 很难应用启发式算法和元启发式算法, 因为这些方法难于保证所求得调度 的可行性. 为了解决这一问题, 本文以半导体芯片制造中组合设备的调度问题作为例子, 介绍了一种基于离散事件 系统控制理论的生产调度新方法. 利用Petri网建模, 任何违反约束的状态均被描述为非法状态, 而使非法状态出现 的调度则是不可行调度. 通过可行调度的存在性分析, 该方法获得可行解空间并将调度问题转化为连续优化问题, 从而可以有效求解. 并且指出, 该方法可以应用于其他应用领域.     

罩式退火炉生产优化调度方法及其应用

罩式退火炉的生产调度过程是一个典型的多工序.多约束、有重入的多机并行调度 问题,难于解析建模.对此问题,将离散事件仿真技术与改进的遗传算法相结合,提出罩式退 火炉生产的优化调度方法.生产现场的实际应用表明所提方法大大提高了生产设备的利用率 和生产效率.     

表面贴装过程调度问题的粒子群优化算法

表面贴装机是大型电路板表面贴装中最重要的设备之一,实现表面贴装过程的优化调度对提高其加工效率有着重要作用;该类调度问题由物料摆放优化问题和加工路径优化问题两部分组成.在分析了表面贴装过程调度问题特征的基础上,提出了一种离散粒子群优化算法.针对问题特征,构造了相应的编码方法,提出了一种基于启发式的粒子群初始化方法,以及适用于该调度问题编码特征的粒子更新机制,并设计了用于优化物料摆放顺序的再调度算法.通过对某大型表面贴装企业的实际数据所进行的数值计算,其结果表明了该算法的有效性.     

并行仿真多样本任务分发与调度工具的设计

并行离散事件仿真具有更高的运行效率,已在分析仿真领域得到了广泛的关注.分析仿真往往要对多组参数组合进行比较,要求仿真应用运行多次才能得到所需的结果数据.针对目前并行仿真应用进行多样本多次运行时需要进行大量手工配置、仿真运行效率低下这一问题,论文在对并行仿真应用多次连续运行控制技术进行深入研究的基础上,提出了一种多样本任务分发与调度框架,并设计了多样本任务分发与调度工具.该工具能够将样本运行信息自动部署到局域网内多个节点上,并调度各节点上的样本并行运行.应用表明工具减少了仿真试验人员仿真运行配置工作量,大大缩短了仿真任务运行所需时间.     

基于强化学习的多技能项目调度算法

多技能项目调度存在组合爆炸的现象, 其问题复杂度远超传统的单技能项目调度, 启发式算法和元启发式 算法在求解多技能项目调度问题时也各有缺陷. 为此, 根据项目调度的特点和强化学习的算法逻辑, 本文设计了基 于强化学习的多技能项目调度算法. 首先, 将多技能项目调度过程建模为符合马尔科夫性质的序贯决策过程, 并依 据决策过程设计了双智能体机制. 而后, 通过状态整合和行动分解, 降低了价值函数的学习难度. 最后, 为进一步提 高算法性能, 针对资源的多技能特性, 设计了技能归并法, 显著降低了资源分配算法的时间复杂度. 与启发式算法的 对比实验显示, 本文所设计的强化学习算法求解性能更高, 与元启发式算法的对比实验表明, 该算法稳定性更强, 且 求解速度更快.     

炼钢-连铸生产启发式调度方法

实际炼钢–连铸生产存在着多阶段、多并行机,以及在精炼阶段具有多重精炼方式,从而大大增加了炼钢–连铸生产调度难度.目前已有的炼钢–连铸生产调度研究由于仅仅针对简单生产方式而难以应用于目前大型炼钢–连铸生产调度.而实际生产过程中的以人工为主的调度方法速度慢、优化程度低,极易造成炉次在设备间的冗余等待时间过长,导致钢水温度下降,甚至造成连铸断浇事故.本文针对中国宝钢某大型炼钢厂的多重精炼方式且存在着可重入调度下的炼钢–连铸生产调度问题进行研究,提出了多种调度顺序方法和设备指派方法,通过仿真实验对多种调度顺序方法和多种设备指派方法组合而成的各种启发式方法进行了研究.最后将本文提出的性能最好的启发式方法应用于该大型炼钢厂的炼钢–连铸生产调度,钢水平均日冗余等待时间得到显著降低.     

Steady-State Throughput and Scheduling Analysis of Multicluster Tools: A Decomposition Approach

Cluster tools are widely used as semiconductor manufacturing equipment. While throughput analysis and scheduling of single-cluster tools have been well-studied, research work on multicluster tools is still at an early stage. In this paper, we analyze steady-state throughput and scheduling of multicluster tools. We consider the case where all wafers follow the same visit flow within a multicluster tool. We propose a decomposition method that reduces a multicluster tool problem to multiple independent single-cluster tool problems. We then apply the existing and extended results of throughput and scheduling analysis for each single-cluster tool. Computation of lower-bound cycle time (fundamental period) is presented. Optimality conditions and robot schedules that realize such lower-bound values are then provided using ldquopullrdquo and ldquoswaprdquo strategies for single-blade and double-blade robots, respectively. For an -cluster tool, we present lower-bound cycle time computation and robot scheduling algorithms. The impact of buffer/process modules on throughput and robot schedules is also studied. A chemical vapor deposition tool is used as an example of multicluster tools to illustrate the decomposition method and algorithms. The numerical and experimental results demonstrate that the proposed decomposition approach provides a powerful method to analyze the throughput and robot schedules of multicluster tools.     

Scheduling DAG-based applications in multicluster environments with background workload using task duplication

Grids or multicluster computing environments are becoming increasingly popular to both scientific and commercial applications. Process scheduling remains a central issue to be effectively resolved in order to exploit the full potential that the grid or multicluster environment can offer. We use a directed acyclic graph (DAG) to model a process or an application where the nodes of the DAG represent the tasks of the process. Prior to the execution of a process in a multicluster environment, the tasks are required to be mapped onto the clusters. In this article, it is shown that the algorithm developed by He et al. [L. He, S.A. Jarvis, D.P. Spooner, D. Bacigalupo, G. Tan, and G.R. Nudd, Mapping DAG-based applications to multiclusters with background workload, Proceedings of the 2005 IEEE International Symposium on Cluster Computing and the Grid, Cardiff, 2005, pp 855–862.] for the multicluster DAG mapping problem can be significantly improved by incorporating the task duplication strategy. The proposed process scheduling algorithm has a time complexity O(| V|²(r+d+1)), where |V| represents the number of tasks; r, the number of clusters; and d, the maximum in-degree of tasks.     

The Multicluster Architecture: Reducing Processor Cycle Time Through Partitioning

The multicluster architecture that we introduce offers a decentralized, dynamically-scheduled architecture, in which the register files, dispatch queue, and functional units of the architecture are distributed across multiple clusters, and each cluster is assigned a subset of the architectural registers. The motivation for the multicluster architecture is to reduce the clock cycle time, relative to a single-cluster architecture with the same number of hardware resources, by reducing the size and complexity of components on critical timing paths. Resource partitioning, however, introduces instruction-execution overhead and may reduce the number of concurrently executing instructions. To counter these two negative by-products of partitioning, we developed a static instruction scheduling algorithm. We describe this algorithm, and using trace-driven simulations of SPEC92 benchmarks, evaluate its effectiveness. This evaluation indicates that for the configurations considered, the multicluster architecture may have significant performance advantages at feature sizes below 0.35 m, and warrants further investigation.     

To Schedule or to Execute: Decision Support and Performance Implications

This paper addresses a fundamental trade-off in dynamic scheduling between the cost of scheduling and the quality of the resulting schedules. The time allocated to scheduling must be controlled explicitly, in order to obtain good-quality schedules in reasonable times. As task constraints are relaxed, the algorithms proposed in this paper increase scheduling complexity to optimize longer and obtain high-quality schedules. When task constraints are tightened, the algorithms adjust scheduling complexity to reduce the adverse effect of long scheduling times on the schedule quality. We show that taking into account the scheduling time is crucial for honoring the deadlines of scheduled tasks. We investigate the performance of our algorithms in two scheduling models: one that allows idle-time intervals to exist in the schedule and another that does not. The model with idle-time intervals has important implications for dynamic scheduling which are discussed in the paper. Experimental evaluation of the proposed algorithms shows that our algorithms outperform other candidate algorithms in several parameter configurations.     

Three practical workflow schedulers for easy maximum parallelism

Runtime scheduling and workflow systems are an increasingly popular algorithmic component in HPC because they allow full system utilization with relaxed synchronization requirements. There are so many special-purpose tools for task scheduling, one might wonder why more are needed. Use cases seen on the Summit supercomputer needed better integration with MPI and greater flexibility in job launch configurations. Preparation, execution, and analysis of computational chemistry simulations at the scale of tens of thousands of processors revealed three distinct workflow patterns. A separate job scheduler was implemented for each one using extremely simple and robust designs: file-based, task-list based, and bulk-synchronous. Comparing to existing methods shows unique benefits of this work, including simplicity of design, suitability for HPC centers, short startup time, and well-understood per-task overhead. All three new tools have been shown to scale to full utilization of Summit, and have been made publicly available with tests and documentation. This work presents a complete characterization of the minimum effective task granularity for efficient scheduler usage scenarios. These schedulers have the same bottlenecks, and hence similar task granularities as those reported for existing tools following comparable paradigms.     

RuleSIM: a toolkit for simulating the operation and improving throughput of rule‐based spam filters

This paper introduces RuleSIM, a toolkit comprising different simulation tools specifically designed to aid researchers concerned about spam‐filtering throughput. RuleSIM allows easily designing, developing, simulating and comparing new scheduling heuristics using different filters and sets of e‐mails. Simulation results can be both graphically analysed, by using different complementary views, and quantitatively compared through several measures. Moreover, the underlying RuleSIM API can be easily integrated with third‐party Java optimization platforms to facilitate debugging and achieve better configurations for rule scheduling. RuleSIM is free software distributed under the terms of GNU Lesser General Public License, and both source code and documentation are publicly available at https://github.com/rulesim/v2.0 . Copyright © 2015 John Wiley & Sons, Ltd.     

基于数据的复杂制造过程调度

现代制造企业规模庞大、过程复杂等特征给制造过程的调度决策带来了极大的挑战. 一方面, 使用传统方法建立指导生产过程调度的精确数学模型变得越来越困难; 另一方面, 因缺乏准确、及时的模型参数而往往导致低下的模型使用效果. 在此情况下, 基于数据--信息--知识--决策的信息提炼轨迹, 有必要探寻新的基于数据的复杂制造过程的调度理论与方法. 在综述国内外相关研究的基础上, 提出了由数据层与模型层构成的基于数据的复杂制造过程调度架构, 并对该结构框架下的相关理论、方法及实施技术进行了探讨.     

基于时间约束集的集束型设备群调度方法

随着300mm晶圆的加工技术问世,工业界开始采用一种全新的晶圆制造设备——集束型设备群(Multi-cluster tools).对于单个集束型设备(Single-cluster tools)调度研究已比较成熟,并提出了多种调度方法,然而对于集束型设备群调度研究尚处在一个起步阶段. 本文对带有驻留约束且具有多种晶圆类型的集束型设备群的调度问题进行了研究,在引入时间约束集概念的基础上建立了调度模型, 同时,提出了一种逐级回溯的调度方法,并对调度算法进行了仿真实验分析. 仿真结果表明本文提出的算法是有效且可行的.