Integrated Resource Allocation and Scheduling in a Bidirectional Flowshop With Multimachine and COS Constraints

An integer programming (IP) model is proposed for integrated resource allocation and operation scheduling for a multiple job--agents system. Each agent handles a specific job-list in a bidirectional flowshop. For the individual agent scheduling problem, a formulation is proposed in continuous time domain and compared with an IP formulation in discrete time domain. Of particular interest is the formulation of the machine utilization function---both in continuous time and discrete time. Fast heuristic methods are proposed with the relaxation of the machine capacity. For the integrated resource allocation and scheduling problem, a linear programming relaxation approach is applied to solve the global resource allocation and a fast heuristic method is applied to solve each scheduling subproblem. The proposed solution is compared experimentally with that from the integer programming solver by CPLEX.      

A Petri Net Method for Schedulability and Scheduling Problems in Single-Arm Cluster Tools With Wafer Residency Time Constraints

With wafer residency time constraints for some wafer fabrication processes, such as low pressure chemical–vapor deposition, the schedulability and scheduling problems are still open. This paper aims to solve both problems. A Petri net (PN) model is developed for the system. This model describes when the robot should wait and a robot wait is modeled as an event in an explicit way. Thus, to schedule a single-arm cluster tool with wafer residency time constraint is to decide how long a robot wait should be. Based on this model, for the first time, we present the necessary and sufficient conditions under which a single-arm cluster tool with residency time constraints is schedulable, which can be checked analytically. Meanwhile, a closed form scheduling algorithm is developed to find an optimal periodic schedule if it is schedulable. Also, a simple method is presented for the implementation of the periodic schedule for steady state, which is not seen in any previous work.      

一种工业无线网络中受时间约束的消息调度方法

为了优化工业无线网络通信链路上的传输性能,降低消息队列排队延迟的发生。在考虑消息的发布时间、截止时间及端到端的截止时间约束下,通过计算消息的处理时延及传输时延,得到调度任务的开始时间矢量图,完成消息的调度。仿真结果表明,受时间约束的消息调度算法,降低了消息队列的排队延迟时间及调度的完成时间。     

Wireless Link Scheduling With Power Control and SINR Constraints

The problem of determining a minimal length schedule to satisfy given link demands in a wireless network is considered. Links are allowed to be simultaneously active if no node can simultaneously transmit and receive, no node can transmit to or receive from more than one node at a time, and a given signal-to-interference and noise ratio (SINR) is exceeded at each receiver when transmitters use optimally chosen transmit powers. We show that a) the general problem is at least as hard as the MAX-SIR-MATCHING problem, which is easier to describe and b) when the demands have a superincreasing property the problem is tractable     

存在设备时间限制的两个企业协同的综合调度算法

针对自有加工企业设备使用时间存在限制无法满足产品交货期的综合调度问题,该文提出存在设备时间限制的两个企业协同的综合调度算法。为了保证自有加工企业能够获得更多的收益,需要将加工任务尽可能多地分配给自有加工企业进行加工。因此,需要将加工任务进行有效分解,首先逆向遍历加工树,将自有加工企业设备使用时间上限作为阈值,设计加工任务分配策略对加工树进行拆分并生成自有加工企业加工的拆分加工树,其余部分为协同加工企业加工的协同加工树。然后设计协同选择策略,在考虑到运输问题并满足交货期的前提下,选取使自有加工企业收益最大的企业为协同加工企业。最后实例分析,该算法可以更好地解决加工企业设备使用时间存在限制并带有交货期和收益的企业车间协同综合调度问题。     

A Multiagent-Based Decision-Making System for Semiconductor Wafer Fabrication With Hard Temporal Constraints

This paper presents a decision-making system for semiconductor wafer fabrication facilities, or wafer fabs, with hard interoperation temporal constraints. The decision-making system is developed based on a multiagent architecture that is composed of scheduling agents, workcell agents, machine agents, and product agents. The decision-making problem is to allocate lots into each workcell to satisfy both logical and temporal constraints. A dynamic planning-based approach is adopted for the decision-making mechanism so that the dynamic behaviors of the wafer fab such as aperiodic lot arrivals and reconfiguration can be taken into consideration. The scheduling agents compute quasi-optimal schedules through a bidding mechanism with the workcell agents. The proposed decision-making mechanism uses a concept of temporal constraint sets to obtain a feasible schedule in polynomial steps. The computational complexity of the decision-making mechanism is proven to be, where is the number of operations of a lot and is the cardinality of the temporal constraint set.     

Operations Management in Automated Semiconductor Manufacturing With Integrated Targeting, Near Real-Time Scheduling, and Dispatching

To help address the need for manufacturing cycle time reduction, Intel has adopted an integrated operations management approach that consists of three key components: targeting, near real-time scheduling, and dispatching. These components work in conjunction to maximize fab efficiency. Combined with fully automated execution, this approach allows Intel to implement a coordinated operational management philosophy at its fabrication facilities. OPSched was developed at Intel to fulfill the requirements of the integrated approach. We look at why this approach is suitable for automated semiconductor manufacturing based on the implementation of the OPSched system at Intel's high-volume manufacturing facilities and the results achieved.      

时态约束下的数据挖掘问题及算法

对于一个大型数据库而言,为了提高挖掘效率,必须考虑减少数据库的扫描次数,同时使内存需求量保持在一个适当的水平上.把时态约束应用到事务数据库的挖掘中,可以获得更好的效率.本文首先利用时态区间代数操作实现原始数据库的过滤和挖掘时态区间的合并;然后在定义项目序列集操作的基础上,提出一个称为TISS-DM的发现频繁项目序列集的高效算法;最后讨论了这个算法的效率.     

Processor Speed Control With Thermal Constraints

We consider the problem of adjusting speeds of multiple computer processors, sharing the same thermal environment, such as a chip or multichip package. We assume that the speed of each processor (and associated variables such as power supply voltage) can be controlled, and we model the dissipated power of a processor as a positive and strictly increasing convex function of the speed. We show that the problem of processor speed control subject to thermal constraints for the environment is a convex optimization problem. We present an efficient infeasible-start primal-dual interior-point method for solving the problem. We also present a distributed method, using dual decomposition. Both of these approaches can be interpreted as nonlinear static control laws, which adjust the processor speeds based on the measured temperatures in the system. We give numerical examples to illustrate performance of the algorithms.     

一种改进的强分区约束的实时调度算法

研究了实时操作系统在强分区约束下的两级分区的调度问题,建立了基于时钟触发的两级分区调度算法的模型.重点论述了调度开销和分区分配方法对系统可调度性的影响,并进一步改进了算法.仿真分析证实,改进的算法能够更好地保障系统的可调度性.     

复杂约束对地观测卫星成像调度技术研究

 对地观测卫星成像调度需要考虑卫星动作时间切换、存储容量、星上能量等复杂约束,确定要观测的观测目标序列,是一个具有强NP-Hard特性的组合优化问题,一般研究者都对问题约束进行了不同程度的简化.针对一类可见光对地观测卫星小问题规模下的应用,考虑上述多种约束,建立顶点和边都带权的无环路有向图模型,并基于标记更新最短路径算法,采用分层支配和分治思想,提出了复杂约束成像卫星调度算法(SISACC)进行完全路径搜索,得到问题精确解;在此基础上,给出了算法改进措施,分析了完全算法和改进方法的性质;最后通过大量实验验证了算法的适用条件和可行性.该方法已成功应用于某在轨卫星的日常成像调度任务中.     

数字阵列雷达在线交错调度算法

传统相控阵雷达中的调度算法难以充分发挥数字阵列雷达的多功能优势.针对这一问题,结合数字阵列雷达的任务结构,提出一种在线交错调度算法.通过将交错调度分析分解为时间资源约束分析和能量资源约束分析,算法能够对所有满足约束的任务进行交错调度：利用任务中的等待期来交错执行其它任务的发射期或接收期,并且不同任务的接收期可实现相互交叠.仿真结果表明,由于雷达任务中等待期和接收期得到充分利用,相比于三种传统的调度算法,所提算法的调度成功率、实现价值率和时间利用率均得到有效提升.     

集束型半导体制造设备的预防维修计划优化

研究了生产200mm以上晶圆的半导体制造企业中的主要设备--集束型设备(cluster tools)的预防维修计划优化问题.基于半导体集成电路生产线的复杂性及集束型设备的特点,建立了基于系统观的集束型设备预防维修计划实时优化模型,设计了用遗传算法求解模型的方法,最后以一个实例及运行结果说明了研究的实用性.     

基于资源调度的远程在线实验室设计

远程在线教育实验室和基于Web的远程学习课程一样迅速地部署在世界各地传统的校园里.本文介绍了远程在线实验室资源调度系统,以用来为地理上分散的多用户协调共享实验室资源,避免用户在时间上的资源冲突,并为不同用户请求提供三种不同优先级处理的功能.     

一体化信号处理与先进处理架构展望

多功能一体化系统是电子信息技术领域的重要发展方向之一,一体化信号处理是其中的关键技术,对实现各种功能之间资源共享与高效协同具有重大意义,同时也从算法到处理架构提出了新的要求。本文首先对一体化信号处理的研究现状进行了归纳总结,给出一种基于一体化信号的多功能系统模型,指出进一步开发空域资源是当前一体化信号设计的主要研究方向之一,并且给出相关信号处理的典型算法;然后,针对上述算法进行了核心算子提炼,指出该类算法以大规模矩阵运算为主要特征,对处理架构提出高算力、高能效的需求;最后,针对上述算法的核心算子设计了基于存内计算和光子计算的处理架构,由于避免了数据搬移并采用高性能模拟计算模式,因此可以大幅提升算力和能效,为一体化信号处理先进架构设计提供了新的技术途径。     

Opportunistic Scheduling with QoS Constraints for Multiclass Services HSUPA System

This paper focuses on the scheduling problem with the objective of maximizing system throughput, while guaranteeing long‐term quality of service (QoS) constraints for non‐realtime data users and short‐term QoS constraints for realtime multimedia users in multiclass service high‐speed uplink packet access (HSUPA) systems. After studying the feasible rate region for multiclass service HSUPA systems, we formulate this scheduling problem and propose a multi‐constraints HSUPA opportunistic scheduling (MHOS) algorithm to solve this problem. The MHOS algorithm selects the optimal subset of users for transmission at each time slot to maximize system throughput, while guaranteeing the different constraints. The selection is made according to channel condition, feasible rate region, and user weights, which are adjusted by stochastic approximation algorithms to guarantee the different QoS constraints at different time scales. Simulation results show that the proposed MHOS algorithm guarantees QoS constraints, and achieves high system throughput.     

Scheduling Tests for 3D Stacked Chips under Power Constraints

This paper addresses Test Application Time (TAT) reduction under power constraints for core-based 3D Stacked ICs (SICs) connected by Through Silicon Vias (TSVs). Unlike non-stacked chips, where the test flow is well defined by applying the same test schedule both at wafer sort and at package test, the test flow for 3D TSV-SICs is yet undefined. In this paper we present a cost model to find the optimal test flow. For the optimal test flow, we propose test scheduling algorithms that take the particulars of 3D TSV-SICs into account. A key challenge in testing 3D TSV-SICs is to reduce the TAT by co-optimizing the wafer sort and the package test while meeting power constraints. We consider a system of chips with cores that are accessed through an on-chip JTAG infrastructure and propose a test scheduling approach to reduce TAT while considering resource conflicts and meeting the power constraints. Depending on the test schedule, the JTAG interconnect lines that are required can be shared to test several cores. This is taken into account in experiments with an implementation of the proposed scheduling approach. The results show significant savings in TAT.     

Failure-Aware Task Scheduling of Synchronous Data Flow Graphs Under Real-Time Constraints

As more processors are integrated into Multiprocessor System-on-Chips (MPSoCs) via relentless technology scaling, the mean-time-to-failure (MTTF) is reduced to the extent that unexpected processor failures are considered during design time. A popular approach to tolerate processor failures is to migrate tasks on the faulty processor to live processors. This approach, however, is not suitable for real-time digital signal processing (DSP) applications since it may not guarantee real-time constraints. In this paper, we propose the re-scheduling of the entire application to minimize throughput degradation under a latency constraint, given that the application is specified by a Synchronous Data Flow (SDF) graph. We obtain sub-optimal re-scheduling results using a genetic algorithm for each scenario of processor failures at compile-time. If a failure is detected at run-time, the live processors obtain the saved schedule, perform task transfer, and execute the remaining tasks of the current iteration. We compare preemptive and non-preemptive migration policies and propose a hybrid policy to obtain better performance. We demonstrate the viability of the proposed technique through experiments with real-life DSP applications as well as randomly generated graphs under timing constraints and random fault scenarios.     

Scheduling Integrated Circuit Assembly Operations on Die Bonder

Solving the integrated circuit (IC) assembly scheduling problem (ICASP) is a very challenging task in the IC manufacturing industry. In the IC assembly factories, the jobs are assigned processing priorities and are clustered by their product types, which must be processed on groups of identical parallel machines. Furthermore, the job processing time depends on the product type, and the machine setup time is sequentially dependent on the orders of jobs processed. Therefore, the ICASP is more difficult to solve than the classical parallel machine scheduling problem. In this paper, we describe the ICASP in detail and formulate the ICASP as in integer programing problem to minimize the total machine workload. An efficient heuristic algorithm is also proposed for solving large-scale problems.