Resource allocation in dynamic PERT networks with finite capacity

This article models the resource allocation problem in dynamic PERT networks with finite capacity of concurrent projects (COnstant Number of Projects In Process (CONPIP)), where activity durations are independent random variables with exponential distributions, and the new projects are generated according to a Poisson process. The system is represented as a queuing network with finite concurrent projects, where each activity of a project is performed at a devoted service station with one server located in a node of the network. For modeling dynamic PERT networks with CONPIP, we first convert the network of queues into a stochastic network. Then, by constructing a proper finite-state continuous-time Markov model, a system of differential equations is created to solve and find the completion time distribution for any particular project. Finally, we propose a multi-objective model with three conflict objectives to optimally control the resources allocated to the servers, and apply the goal attainment method to solve a discrete-time approximation of the original multi-objective problem.     

Multi-objective evacuation routing in transportation networks

In this paper, the optimal design and analysis of evacuation routes in transportation networks is examined. An methodology for optimal egress route assignment is suggested. An integer programming (IP) formulation for optimal route assignment is presented, which utilizes M/G/c/c state dependent queueing models to cope with congestion and time delays on road links. M/G/c/c simulation software is used to evaluate performance measures of the evacuation plan: clearance time, total travelled distance and blocking probabilities. Extensive experimental results are included.     

A simulation model for emergency evacuation

This paper describes the development of a prototype spatial decision support system for use by emergency planners in developing contingency plans for evacuations from disaster areas. It links together a geographical information system (ARC/INFO) with a specially written object-oriented micro-simulator via a windowing computer operating system. The details of the system are described, its limitations are discussed and potential enhancements are identified.     

Assessing systems for offshore emergency evacuation

Emergency evacuation is a rare event in the offshore oil industry. Nonetheless, emergency procedures must be practiced routinely for the benefit of the work force and the emergency services. These practices typically take place in good weather conditions where there is little threat to those involved. However, in reality an emergency could occur in adverse weather conditions which can affect the capabilities of vessels and helicopters. This paper describes a study in which the data from various sources are synthesised in order to estimate the effectiveness of emergency evacuation and rescue systems in a stochastic environment. The study employed a discrete event simulation incorporating a model of the evacuation and rescue operations interfaced with a file of weather data. This approach provided a measure, the probability of completing the evacuation within N hours, for the comparison of alternative systems.     

Numerical simulation of building evacuation in emergency conditions

In the present work, pedestrian behaviour in crowds is assumed to be a coupled phenomena. Therefore, the use of continuousand individual-models in different regions according to its local density is suggested. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Bandwidth allocation in ATM networks

In an ATM network, bandwidth is allocated at different levels and in different stages. At the physical level, the ATM topology can be dynamically reconfigured by adding/removing truns between ATM switches. This allocation of bandwidth is made possible by the SONET Synchronous Transfer Mode (STM) infrastructure equipped with Digital Cross Connect Systems (DCSs). We will refer to this allocation asSTM allocation. At the ATM level, we can allocate bandwidth to individual Virtual Circuits (ATM-VC allocation) as well as to Virtual Paths (ATM-VP allocation). For example, in order to implement the Connectionless Network Access layer functions we find it convenient to organize the Virtual Paths in a Connectionless Overlay Network. This introduces another type of bandwidth allocation (CLS allocation). In this paper, we address and formulate the above bandwidth allocation problems, and propose efficient techniques for their solution. We illustrate these techniques with examples based on STM and CLS allocation, respectively.This work was jointly supported by the Brazilian National Science Council (CNPq) and NSF.     

Resource allocation for performance improvement

In this paper the problem of allocating resources among Decision Making Units is considered. This study covers the case in which several homogeneous units are operating under the supervision of a central unit. The resource allocation is carried out by the DM (central unit) in such a way that the overall performance of the system is improved. Performance is defined by means of a convex combination of the ratio of the efficiencies before and after the resource allocation. It is assumed that each unit is allowed to modify its resources within the current production possibility set. A novel model is proposed which aims at achieving the best performance of the system. The method is capable of dealing with some additional constraints, imposed by the DM. The model is illustrated by a simple numerical example and a real application.     

Individual customer’s behaviour in networks with state-dependent arrival rates

We consider Jackson networks with state-dependent arrival and service rates which show product form or nearly product form steady-states and come up with examples of load-dependent admission control. For these networks we prove an arrival theorem for external as well as for internal arrivals. In case of open tandem systems with state-independent service rates we compute the joint distribution of the sojourn times of a customer in the nodes and the distribution of the customer’s end-to-end-delay. This revised version was published online in June 2006 with corrections to the Cover Date.     

Decision support for hospital evacuation and emergency response

Evacuation planning is an important part of a hospital’s emergency management plan. In an evacuation the safety and health of patients is the fundamental success parameter. Thus, in this paper we introduce an evacuation model, appropriate for planning and operations, that has the objective of minimizing expected risk, both the threat risk that is forcing the evacuation, and the risk inherent in transporting patients, some in critical condition. Specifically, we study the allocation of patients, categorized by criticality and care requirements, to a limited fleet of vehicles of various capacities and medical capabilities, to be transported to appropriate receiving hospitals considering the current available space in each hospital for each category of patient. The model is an integer program, where the non-linear expected risks are calculated a-priori. This model has a structure that has excellent solution characteristics that permit us to solve large problems in a reasonable time, enabling the model to potentially be used for both planning and operations. To illustrate the solvability of this model and demonstrate its characteristics, we apply it to a realistic case study based on the evacuation of a large regional hospital.     

Resource allocation in a large decentralized enterprise

We present a model of an enterprise comprising several operating units pursuing their production goals with a fair degree of autonomy, but under resource constraints imposed by a headquarters function. Specifically, each operating unit is assumed to seek a maximization of a perceived market value of its product output, subject to constraints on resources such as capital for plants and equipment, headcount, etc. imposed by headquarters. The headquarters function pursues a global optimization problem which takes into account the market values of all the products of the operating units, but also the cost of the resources and their regulation. Under suitable assumptions of linearity, the operation of the enterprise is formulated as a novel hierarchical structure of linear programming problems. An algorithm is presented for the solution of a class of such problems.     

无预警紧急疏散中公交车辆路径的确定方法

针对无预警式紧急疏散中公交救援车辆的最佳路径确定问题,提出了一个非线性混合整数规划模型.模型不仅考虑了有接收能力限制的多避难所系统,还对如何处理具有不同载客上限的公交救援车进行了分析.利用添加了虚拟路段和节点的时空网络,在以加权的综合疏散时间最小为目标的同时实现了疏散伤亡最小化.通过分析实际疏散的实施过程,得到了一种产生模型可行解的有效方法.通过将时间滚动式的流量加载模式与经典遗传算法相结合,给出了新模型的实用解法.最后,通过算例验证了模型和算法的有效性.     

Resource allocation based on cost efficiency

In this paper, we consider a resource allocation (RA) problem and develop an approach based on cost (overall) efficiency. The aim is to allocate some inputs among decision making units (DMUs) in such way that their cost efficiencies improve or stay unchanged after RA. We formulate a multi-objective linear programming problem using two different strategies. First, we propose an RA model which keeps the cost efficiencies of units unchanged. This is done assuming fixed technical and allocative efficiencies. The approach is based on the assumption that the decision maker (DM) may not have big changes in the structure of DMUs within a short term. The second strategy does not impose any restrictions on technical and allocative efficiencies. It guarantees that none of the cost efficiencies of DMUs get worse after RA, and the improvement for units is possible if it is feasible and beneficial. Two numerical examples and an empirical illustration are also provided.     

Resource allocation in rooted trees for VLSI applications

ABSTRACT

Several optimization problems of modifying the weight of vertices in rooted trees, some of which are special cases of the inverse 1-median problem, are solved. Such problems arise in Very Large Scale Integration (VLSI) design of hardware security circuits, circuit synchronization, and analog-to-digital converters. These problems require assigning costly hardware (demands) to the leaves of rooted trees. One common property of these problems is that a resource allocated to an internal node can be shared by the entire sub-tree emanated at the node. Two types of problems are studied here. (1) A tree node employs an addition operation and the demands at the leaves are obtained by summing the resources allocated to nodes along the root-to-leaf paths. A linear-time bottom-up algorithm is shown to minimize the total resources allocated to tree nodes. (2) A tree’s node employs a multiplication operation and the demands at the leaves are obtained by multiplying the resources allocated to nodes along the root-to-leaf paths. A bottom-up dynamic programming algorithm is shown to minimize the total resources allocated to the tree’s nodes. While the above problems are usually solved by design engineers heuristically, this paper offers optimal solutions that can be easily programmed in CAD tools.     

Optimal and suboptimal capacity allocation in communication networks

Gomory and Hu (Ref. 1) formulated the optimal allocation of capacities to the links of a communication networks as a problem in linear programming. The application of this formulation to the solution of problems of realistic size does, however, require an excessive amount of computation. In the present paper, a slightly different formulation is given. The resulting optimality conditions readily lend themselves to the construction of problems with known optimal solutions, thereby providing suitable examples for the assessment of the efficiencies of approximate methods. An approximate method that has been found highly efficient in many cases is illustrated by an example.     

Deadlock free buffer allocation in closed queueing networks

Blocking queueing networks are of much interest in performance analysis due to their realistic modeling capability. One important feature of such networks is that they may have deadlocks which can occur if the node capacities are not sufficiently large. A necessary and sufficient condition for the node capacities is presented such that the network is deadlock free. An algorithm is given for buffer allocation in blocking queueing networks such that no deadlocks will occur assuming that the network has the special structure called cacti-graph. Additional algorithm which takes linear time in the number of nodes, is presented to find cycles in cacti networks.Akyildiz's work was supported in part by School of Information and Computer Science, ICS, of Georgia Tech and by the Air Force Office of the Scientific Research (AFOSR) under Grant AFOSR-88-0028.     

Bandwidth allocation and access control in high-speed networks

The problem of bandwidth allocation and access regulation arises in the congestion control of Broadband ISDN networks. This paper assumes that a single user, described by an on-off fluid model, is connected to the network via a leaky bucket access control mechanism. The bandwidth allocated to this user and the leaky bucket parameters are to be selected so as to guarantee a negotiated level of delay probability at the access point and packet loss probability in the network which is modelled as an output buffer. The design problem is to minimize the allocated bandwidth subject to service guarantees and stability conditions for the input and output buffers. We provide a desirable feasible solution to the design problem. The paper studies the effect of non-conforming users on the network performance using the leaky bucket access control corresponding to this feasible solution. We provide expressions that quantify the impact of the leaky bucket parameters in access regulation and the worst-case queueing behavior at the output buffer. Finally, we discuss the extension of this methodology to the multiple leaky buckets case.This research was supported in part by IBM Research Contract No. 1374.     

Resource allocation based on the DEA model

The purpose of this paper is to develop an approach to a resource-allocation problem that typically appears in organizations with a centralized decision-making environment, for example, police stations, banks, and universities. The central unit is assumed to be interested in maximizing both the total efficiency and the efficiency of the individual unit by allocating available resources to them. Building upon this, we present a data envelopment analysis-based model for allocating input resources to DMUs (the decision-making units) under the framework of multiple objective programming. Numerical examples are used to illustrate the approach.     

Resource allocation with stochastic optimal control approach

A control-theoretic decision making system is proposed for an agent (decision maker) to “optimally” allocate and deploy his/her resources over time among a dynamically changing list of opportunities (e.g., financial assets), in an uncertain market environment. The solution is a sequence of actions with the objective of optimizing total reward function. This control-theoretic approach is unique in a sense that it solves the problem at distinct time epochs over a finite time horizon and strategies are discovered directly. Rather than basing a decision making system on forecasts or training via a reinforcement learning algorithm using current state data, we train our system via a Q-learning algorithm using Geometric Brownian Motion as an asset price function. While the above problem is quite general, we focus solely on the problem of dynamic financial portfolio management with the objective of maximizing the expected utility for a given risk level. The performance functions that we consider for our system are realized mean return, drawdown and standard deviation. We find that our model achieves a better return and drawdown compared to a known market index as a benchmark.