单波长光缓存的研究与分析

对异步光突发交换网络中单波长光缓存进行仿真建模并辅以分析,介绍了当前已有的理论并用其验证仿真结果。用不同的信道资源分配算法进行仿真并比较结果,指出光缓存中缓存粒度最佳值的设置不仅和突发包的平均长度以及负载有关,而且与核心结点所采用的调度算法有关。     

Simple bounds for closed queueing networks

Consider a closed Jackson type network in which each queue has a single exponential server. Assume that N customers are moving among k queues. We establish simple closed form bounds on the network throughput (both lower and upper), which are sharper than those that are currently available. Numerical evaluation indicates that the improvements are significant.     

Periodic maintenance and repair rate control in stochastic manufacturing systems

In this paper, we consider a periodic preventive maintenance, repair, and production model of a flexible manufacturing system with failure-prone machines, where the control variables are the repair rate and production rate. We use periodic preventive maintenance to reduce the machine failure rates and improve the productivity of the system. One of the distinct features of the model is that the repair rate is adjustable. Our objective is to choose a control process that minimizes the total cost of inventory/shortage, production, repair, and maintenance. Under suitable conditions, we show that the value function is locally Lipschitz and satisfies an Hamilton-Jacobi-Bellman equation. A sufficient condition for optimal control is obtained. Since analytic solutions are rarely available, we design an algorithm to approximate the optimal control problem. To demonstrate the performance of the numerical method, an example is presented.Research of this author was supported by the Natural Sciences and Engineering Research Council of Canada, Grant OGP0036444.Research of this author was supported in part by the University of Georgia.Research of this author was supported in part by the National Science Foundation, Grant DMS-92-24372.     

A dynamic production planning and scheduling algorithm for two products processed on one line

This paper presents a dynamic production planning and scheduling algorithm for two products processed on one line over a fixed time horizon. Production rates are assumed fixed, and restrictions are placed or inventory levels and production run lengths. The resulting problem is a nonlinear binary program, which is solved using an implicit enumeration strategy. The algorithm focuses on the run changeover period while developing tighter bounds on the length of the upcoming run to improve computational efficiency. About 99% pf 297 randomly generated problems with varying demand patterns are solved in less than 15 seconds of CPU time on a CDC Cyber 172 Computer. A mixed integer programming formulation of the generalized multi-product case under no-backlogging of demand is also given.     

Optimum load scheduling of nuclear-hydro-thermal power systems

This paper considers the problem of short-term optimal operation of nuclear-hydro-thermal electric power systems. The solution is obtained by use of a functional analytic optimization technique that employs the minimum norm formulation.A power system with an arbitrary number of generating stations is considered. The limited flexibility exhibited by the thermal nuclear reactors, when operating in a load-following mode, is accounted for by means of a model of the xenon concentration in their cores. The nonlinear effects induced by trapezoidal water reservoirs and the time delay of the water flow between upstream and downstream hydroplants is taken into consideration as well.A two-level iterative scheme of the feasible type is proposed for implementing the optimal solution.This work was supported in part by the National Research Council of Canada, Grant No. A-4146.     

实现测试复用的SOC设计中的测试结构

在系统芯片SOC(system on a chip)设计中实现IP核测试复用的芯片测试结构一般包含两个部分：1)用于传送测试激励和测试响应的片上测试访问机制TAM;2)实现测试控制的芯片测试控制器。文章分析了基于测试总线的芯片测试结构,详细阐述了SOC设计中测试调度的概念,给出了一种能够灵活实现各种测试调度结果的芯片测试控制器的设计。     

Opportunistic Multi-Access: Multiuser Diversity, Relay-Aided Opportunistic Scheduling, and Traffic-Aided Smooth Admission Control

We study multi-access control in opportunistic communication systems, and propose two new schemes to address channel asymmetry and throughput-guaranteed admission control, respectively. We first devise a relay-aided opportunistic scheduling (RAOS) scheme, in which a user can choose to communicate with the base station either directly or using multiple hops (relay transmissions). We develop relay/direct link construction algorithms using either a channel-capacity-based criterion or a throughput-based criterion, and devise opportunistic scheduling schemes accordingly. Our results show that in the presence of channel asymmetry across users, the RAOS scheme performs significantly better than Qualcomm's HDR scheme. Next, we propose a traffic-aided smooth admission control (SAC) scheme that aims to guarantee throughput provisioning. Simply put, in the SAC scheme, the admission decision is spread over a trial period, by increasing gradually the amount of the time resource allocated to incoming users. Specifically, using the modified weighted proportional fair (WPF) scheduling, we devise a QoS driven weight adaptation algorithm, and the weights assigned to new users are increased in a guarded manner. Then an admission decision is made based on the measured throughput within a time-out window. A key feature is that we exploit explicitly the traffic information and throughput requirements in devising the back-off time. Our results show that the proposed SAC scheme works well in opportunistic communication systems.     

Designing routes to minimize fleet operating costs

A route-planner must try to schedule the delivaries by a fleet of vehicles such that customer requirements are met and management objectives are satisfied. In most cases, the number of feasible arrangements is legion, and calculations relating to individual vehicle loads, mileages, delivery times, etc. are tedious, allowing only a small fraction of possible route plans to be established and compared. The problem presents an ideal opportunity for computer application, not least to ensure that solutions are timely and error free.Several algorithms have been developed to improve the quality of vehicle routes, but in practice only those that rely on simple selection rules have found widespread acceptance, due to the innate complexity of the calculations that follow from a more rigorous approach and to the great variety of customer, vehicle, and operational characteristics that distinguish transport systems and which must be accomodated.The method presented here is based upon the well-known ‘savings’ criterion, but avoids many of its deficiencies by employing a random selection mode and producing (efficiently) a large sample of schedules from which to choose the most suitable. In particular, this allows greater flexibility in defining management objectives, and has led to substantial reductions in both fleet sizes and distances travelled, compared to published results, for a set of nine test cases each involving more than 200 customer locations.     

Counting and enumeration complexity with application to multicriteria scheduling

In this paper we tackle an important point of combinatorial optimisation: that of complexity theory when dealing with the counting or enumeration of optimal solutions. Complexity theory has been initially designed for decision problems and evolved over the years, for instance, to tackle particular features in optimisation problems. It has also evolved, more or less recently, towards the complexity of counting and enumeration problems and several complexity classes, which we review in this paper, have emerged in the literature. This kind of problems makes sense, notably, in the case of multicriteria optimisation where the aim is often to enumerate the set of the so-called Pareto optima. In the second part of this paper we review the complexity of multicriteria scheduling problems in the light of the previous complexity results.Received: November 2004 / Received version: March 2005MSC classification: 90B40, 90C29, 68Q15     

Solving problems of discrete tomography

This is a summary of the most important results presented in the author's PhD thesis. This thesis, written in French, was defended on 24 November 2004 and supervised by Marie-Christine Costa and Christophe Picouleau. This thesis consists in developing the study of discrete tomography problems. It aims at reconstructing discrete objects (matrices, images, discrete sets, etc) that are accessible only through few projections. A copy of the thesis is available on "http: //cedric.cnam.fr/AfficheArticle.php?id = 698". Received: April 2005 AMS classification: 90B70, 68Q17, 52C15, 05B50