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.     

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

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

Optimal Integrated Schedule of Entire Process of Dual-blade Multi-cluster Tools From Start-up to Close-down

Multi-cluster tools are widely used in majority of wafer fabrication processes in semiconductor industry. Smaller lot production, thinner circuit width in wafers, larger wafer size, and maintenance have resulted in a large quantity of their start-up and close-down transient periods. Yet, most of existing efforts have been concentrated on scheduling their steady states. Different from such efforts, this work schedules their transient and steady-state periods subject to wafer residency constraints. It gives the schedulability conditions for the steady-state scheduling of dual-blade robotic multi-cluster tools and a corresponding algorithm for finding an optimal schedule. Based on the robot synchronization conditions, a linear program is proposed to figure out an optimal schedule for a start-up period, which ensures a tool to enter the desired optimal steady state. Another linear program is proposed to find an optimal schedule for a close-down period that evolves from the steady state period. Finally, industrial cases are presented to illustrate how the provided method outperforms the existing approach in terms of system throughput improvement.      

多组合设备的调度控制研究综述

在半导体芯片制造中越来越广泛使用多组合设备.本文介绍了多组合设备的结构配置、生产运行过程、调度控制问题的一般特征条件、应该满足的约束及周期性调度策略;分析了问题的复杂性因素.从多组合设备的结构特征、运行过程特征两方面分类综述了调度问题的建模、分析方法、调度算法及存在的问题,最后指出了未来的研究方向.     

A tight flow control for job-shop fabrication lines with finite buffers

We propose a work-in-process (WIP) estimation flow control method which serves as a countermeasure against the throughput degradation problem caused by the redundant blocking time of conventional flow control. This method is based on a scheduling technique of which the most important features are: 1) breaking down the entire schedule into individual lot schedules; 2) lot scheduling to reduce redundant blocking time; and 3) WIP estimation for contiguous finite buffer scheduling. The method, first, schedules operational lots at each equipment unit in a fabrication line by using our scheduling procedure for contiguous finite buffers to satisfy the limit capacity of the buffers. Next, the method estimates the future WIP at each equipment group based on predetermined schedules for performing operations. Finally, the method improves the operation timings by continuously supplying WIP estimation to the scheduling procedure. In an actual liquid crystal display (LCD) fabrication line simulation, we have confirmed that the proposed WIP estimation method is a promising one from the standpoint of the line throughput which we obtained.     

Multi-degree cyclic scheduling of two robots in a no-wait flowshop

This paper addresses multi-degree cyclic scheduling of two robots in a no-wait flowshop, where exactly r(r > 1) identical parts with constant processing times enter and leave the production line during each cycle, and transportation of the parts between machines is performed by two robots on parallel tracks. The objective is to minimize the cycle time. The problem is transformed into enumeration of pairs of overlapping moves that cannot be performed by the same robot. This enumeration is accomplished by enumerating intervals for some linear functions of decision variables. The algorithm developed is polynomial in the number of machines for a fixed r, but exponential if r is arbitrary. Computational results with benchmark instances are reported. Note to Practitioners-This paper was motivated by the problem of cyclic scheduling of a no-wait production line, where a part must be processed without any interruption either on or between machines due to characteristics of the processing technology itself or the absences of storage capacity between operations of a part. Multi-degree schedules, in which multiple parts enter and leave the line during a cycle, usually have larger throughput rate than simple ones. This paper proposes an algorithm for multi-degree cyclic scheduling of a no-wait flowshop with two robots. Computational results show that the throughput rate can be really improved by using multi-degree schedules with two robots. However, we have not addressed the decision of the optimal value of the degree of the cycle. Furthermore, since we consider that the two robots travel along parallel tracks, the collision-avoidance constraints have been relaxed in the algorithm. In future research, we will address the two problems and generalize the algorithm to multi-robot cases.     

Optimal <Emphasis Type="Italic">K</Emphasis>-unit cycle scheduling of two-cluster tools with residency constraints and general robot moving times

The semiconductor manufacturing industry is significantly expensive both in equipment and materials. Cluster tools, a type of automated manufacturing system integrating processing modules and transport modules, are commonly used in this industry. Nowadays, multi-cluster tools, which are composed of several cluster tools connected by joint buffer modules, are often used for wafer production. This paper deals with K-unit cycle scheduling problems in single-armed two-cluster tools for processing identical wafers in deterministic settings. In a K-unit cycle, K wafers are exactly inserted into the two-cluster tool, and K completed wafers leave the two-cluster tool, usually not the same K wafers. Residency constraints and general moving times by the robot are both considered. The objective is to obtain optimal K-unit cycle schedules, which minimize cycle times. To analyze this scheduling problem in detail, a mixed integer linear programming (MILP) model is formulated and solved. Numerical examples are used to explain how the solution can be obtained from the MILP model in a K-unit cycle.     

Throughput-Optimal Sequences for Cyclically Operated Plants

In this paper, we present a method to determine globally optimal schedules for cyclically operated plants where activities have to be scheduled on limited resources. In cyclic operation, a large number of entities is processed in an identical time scheme. For strictly cyclic operation, where the time offset between entities is also identical for all entities, the objective of maximizing throughput is equivalent to the minimization of the cycle time. The resulting scheduling problem is solved by deriving a mixed integer optimization problem from a discrete event model. The model includes timing constraints as well as open sequence decisions for the activities on the resources. In an extension, hierarchical nesting of cycles is considered, which often allows for schedules with improved throughput. The method is motivated by the application to high throughput screening plants, where a specific combination of requirements has to be obeyed (e.g. revisited resources, absence of buffers, or time window constraints).     

Parametric algorithms for 2-cyclic robot scheduling with interval processing times

Consider an m-machine production line for processing identical parts served by a mobile robot. The problem is to find the minimum cycle time for 2-cyclic schedules, that is, schedules in which exactly two parts enter and two parts leave the production line during each cycle. This work treats a special case of the 2-cyclic robot scheduling problem when the robot route is given and operation durations are chosen from prescribed intervals. A strongly polynomial algorithm of time complexity O(m ⁸log m) is proposed.     

Single-machine scheduling with workload-dependent tool change durations and equal processing time jobs to minimize total completion time

We consider a single-machine tool change scheduling problem where tool change durations are workload-dependent. The processing times of all the jobs are the same. The objective is to determine the number of tool change activities, the start time and the completion time of each tool change activity jointly and schedule all the jobs to the machine such that the total completion time of the jobs is minimized. For the case where the tool change duration function is concave, we present a linear time optimal algorithm. For the case where the tool change duration function is convex, we convert it into a convex integer quadratic programming problem with fixed dimension and then propose two polynomial time algorithms for it. We also study some special cases for which optimal schedules can be obtained directly. For the case where the tool change duration function is linear, we present all the optimal schedules.     

Scheduling Time-Constrained Communication in Linear Networks

Abstract. We study the problem of centrally scheduling multiple messages in a linear network, when each message has both a release time and a deadline. We show that the problem of transmitting optimally many messages is NP-Hard, both when messages may be buffered in transit and when they may not be. For either case, we present efficient algorithms that produce approximately optimal schedules. In particular, our bufferless scheduling algorithm achieves throughput that is within a factor of 2 of optimal. We show that buffering can improve throughput in general by a logarithmic factor (but no more), but that in several significant special cases, such as when all messages can be released immediately, buffering can help by only a small constant factor. Finally, we show how to convert any of our centralized, offline bufferless schedules to a fully distributed online buffered schedule of equal throughput. Most of our results extend readily to ring-structured networks.     

A decomposition based hybrid heuristic algorithm for the joint passenger and freight train scheduling problem

We study the joint problem of scheduling passenger and freight trains for complex railway networks, where the objective is to minimize the tardiness of passenger trains at station stops and the delay of freight trains. We model the problem as a mixed integer program and propose a two-step decomposition heuristic to solve the problem. The heuristic first vertically decomposes the train schedules into a passenger train scheduling phase and then a freight train scheduling phase. In the freight train scheduling phase, we use a train-based decomposition to iteratively schedule each freight train. Experimental results show the efficiency and quality of the proposed heuristic algorithm on real world size problems.     

A scheduling method for multi-robot assembly of aircraft structures with soft task precedence constraints

The use of multiple cooperating robotic manipulators to assemble large aircraft structures entails the scheduling of many discrete tasks such as drilling holes and installing fasteners. Since the tasks have different tool requirements, it is desirable to minimize tool changes that incur significant time costs. We approach this problem as a multi-robot task allocation problem with precedence constraints, where the constraints are loosely enforced in terms of prioritizing the tasks to avoid unnecessary tool changes. To avoid the computational burden of searching over all possible task prioritization options, our main contribution is to develop a two-step, data-driven approach to automatically select suitable precedence relations. The first step is to adapt an iterative auction-based method to encode the precedence relations using scheduling heuristics. The second step is to develop a robust machine learning method to generate policies for automatically selecting efficient scheduling heuristics based on the problem characteristics. Experimental results show that the top performing heuristics yield schedules that are more efficient than those of a baseline partition-based scheduler by almost 17%–19%, depending on the robot failure profiles. The learned policies are also able to select heuristics that perform better than greedy selection without incurring additional computational costs.     

Contribution to the scheduling of trajectories in robotics

In this paper, we intend to propose a method for minimizing the cycle time of robotic tasks by using an optimal scheduling of trajectory points: we consider functional points (welding or laser-cutting points on a car-body for example) that a robot has to reach. The problem is to order these points in such a way that the global cycle time is minimum. Originally, this scheduling problem is similar to the well-known travelling salesman problem. Among the algorithms used in combinatorial optimization, we have taken an interest in an original connectionist method called “the elastic net method”, initially presented in an euclidian two-dimension space. The method described in this article is adapted for robotic purpose. It has been tested in industrial cases and compared with a classical method in combinatorial optimization: the Little’s algorithm. The elastic net method is generalized to the specific case of robotics applications. The elastic net method is generalized in the case of non-redundant and redundant robots; we develop a simultaneous research of the optimal scheduling and of the optimal choice of the configurations of the robot for each functional point. The optimal scheduling of the points of a trajectory in the case of redundant robots is presented. We consider it to be the original contribution of this work. In the case of cluttered environments, the above algorithm is adapted by introducing a repulsion potential between the obstacles and the “elastic”. This leads to the simultaneous research of the optimal scheduling and of the free path planning. The method, using a new kind of algorithm, leads to original and reliable results for minimizing cycle time in robotics.     

Decentralized multi-robot allocation of tasks with temporal and precedence constraints

Abstract

We present an auction-based method for a team of robots to allocate and execute tasks that have temporal and precedence constraints. Temporal constraints are expressed as time windows, within which a task must be executed. The robots use our priority-based iterated sequential single-item auction algorithm to allocate tasks among themselves and keep track of their individual schedules. A key innovation is in decoupling precedence constraints from temporal constraints and dealing with them separately. We demonstrate the performance of the allocation method and show how it can be extended to handle failures and delays during task execution. We leverage the power of simulation as a tool to analyze the robustness of schedules. Data collected during simulations are used to compute well-known indexes that measure the risk of delay and failure in the robots’ schedules. We demonstrate the effectiveness of our method in simulation and with real robot experiments.     

柔性制造系统的时间Petri网建模与分析

时间Petri网是描述和验证实时系统最常用的形式模型之一。建立基于时间 Petri网的典型柔性制造系统模型,利用状态类分析方法,定量计算所有可行调度及其执行时间,进而获得最优调度,为复杂柔性制造系统的建模与调度提供有效的模型支持。     

Scheduling with timed automata

In this work, we present timed automata as a natural tool for posing and solving scheduling problems. We show how efficient shortest path algorithms for timed automata can find optimal schedules for the classical job-shop problem. We then extend these results to synthesize adaptive scheduling strategies for problems with uncertainty in task durations.     

FEADS: A Framework for Exploring the Application Design Space on Network Processors

Network processors are designed to handle the inherently parallel nature of network processing applications. However, partitioning and scheduling of application tasks and data allocation to reduce memory contention remain as major challenges in realizing the full performance potential of a given network processor. The large variety of processor architectures in use and the increasing complexity of network applications further aggravate the problem. This work proposes a novel framework, called FEADS, for automating the task of application partitioning and scheduling for network processors. FEADS uses the simulated annealing approach to perform design space exploration of application mapping onto processor resources. Further, it uses cyclic and r-periodic scheduling to achieve higher throughput schedules. To evaluate dynamic performance metrics such as throughput and resource utilization under realistic workloads, FEADS automatically generates a Petri net (PN) which models the application, architectural resources, mapping and the constructed schedule and their interaction. The throughput obtained by schedules constructed by FEADS is comparable to that obtained by manual scheduling for linear task flow graphs; for more complicated task graphs, FEADS’ schedules have a throughput which is upto 2.5 times higher compared to the manual schedules. Further, static scheduling of tasks results in an increase in throughput by upto 30% compared to an implementation of the same mapping without task scheduling.     

Post-Processing Time-Aware Optimal Scheduling of Single Robotic Cluster Tools

Integrated circuit chips are produced on silicon wafers. Robotic cluster tools are widely used since they provide a reconfigurable and efficient environment for most wafer fabrication processes. Recent advances in new semiconductor materials bring about new functionality for integrated circuits. After a wafer is processed in a processing chamber, the wafer should be removed from there as fast as possible to guarantee its high-quality integrated circuits. Meanwhile, maximization of the throughput of robotic cluster tools is desired. This work aims to perform post-processing time-aware scheduling for such tools subject to wafer residency time constraints. To do so, closed-form expression algorithms are derived to compute robot waiting time accurately upon the analysis of particular events of robot waiting for single-arm cluster tools. Examples are given to show the application and effectiveness of the proposed algorithms.