Search

Many real-world networks such as freight, power and long distance transportation networks are represented as multi-source multi-sink stochastic flow network. The objective is to transmit flow successfully between the source and the sink nodes. The reliability of the capacity vector of the assigned components is used an indicator to find the best flow strategy on the network. The Components Assignment Problem (CAP) deals with searching the optimal components to a given network subject to one or more constraints. The CAP in multi-source multi-sink stochastic flow networks with multiple commodities has not yet been discussed, so our paper investigates this scenario to maximize the reliability of the capacity vector subject to an assignment budget. The mathematical formulation of the problem is defined, and a proposed solution based on genetic algorithms is developed consisting of two steps. The first searches the set of components with the minimum cost and the second searches the flow vector of this set of components with maximum reliability. We apply the solution approach to three commonly used examples from the literature with two sets of available components to demonstrate its strong performance.

Introduction. The article considers the problem of distribution of available and leased vehicles for servicing the stochastic flow of long-distance freight orders. The content of the problem is that the total amount of jobs should be divided between the available vehicles and those that can be rented from partners, so that the overall efficiency of transport processes and the total profit of the enterprise are maximum. The problem is relevant today because the requirements for carriers are growing, their operational management tasks are becoming more complicated, and effective methods that provide guaranteed accurate optimal solutions are unknown. The purpose of research is to determine the signs of organizational and technological compatibility of transport process tasks, the implementation of which in united flow is effective. The use of such features should lead to a guaranteed accurate solution of the problem of distribution of vehicles with a random nature of input flows. Results. The vehicles ordering that arise stochastically is NP-difficult task of strong sense. Additional classification features of orders are offered, which allow us to find a guaranteed stable solution. This solution is possible due to the fact that compatible or partially compatible orders are pre-combined into sets that are intended to be executed in a single flow, and single vehicle. The model of nonlinear programming is applied. To distribute the dynamic input flow of orders the distribution problem was solved with a stable result. The solution criterion is the total profit that the road carrier can receive with the proposed sequence of orders. Optimization at linear approximation of total profit on signs of compatibility of orders is executed. Conclusions. Structural modeling of the integrated transport process should be carried out for specific signs of compatibility of the incoming flow of orders. A sign of compatibility of orders is the coefficient of time unevenness, has a positive effect on the ability to obtain a higher maximum total profit. Linear approximation of the model gives more than 100% error of results.

In a stochastic-flow network with budget constraint, the network reliability for level (d, b), i.e., R(d,b), where d is a given demand value and b is a budget limit, is the probability of transmitt...

A network with multi-state arcs or nodes is commonly called a multi-state network. In the real world, the system reliability of a multi-state network can vary over time. Hence, a critical issue emerges to characterize the time attribute in a stochastic flow network. To solve this issue, this study bridges conventional reliability theory and the reliability of multi-state network. This study utilizes exponential distribution as a possible reliability function to quantify the time attribute in a multi-state network. First, the reliability of every single component is modeled by exponential distribution, where such components comprise a multi-state element. Once the time constraint is given, the capacity probability distribution of arcs can be derived. Second, an algorithm to generate minimal capacity vectors for given demand is provided. Finally, the system reliability can be calculated in terms of the derived capacity probability distribution and the generated minimal capacity vectors. A maintenance issue is further discussed according to the result of system reliability.

In the case of an existing limited capacity of the system called required system capacity, in this study a new method is presented to determine the disjoint paths to send data from the source to the sink. System reliability is evaluated as the probability that a specified amount of data can be transmitted from a source to a sink through two disjoint paths, subject to a time threshold and a required capacity. In addition, we study the effect of using the proposed method on the reliability evaluation in comparison with other previous methods.

Since 1954, the maximal flow problems have gained much attention in the world. They are also extended to many other fields for applications. For example, the definition of a network reliability is just to evaluate the probability of a live connection between the source node and the sink node such that the maximal flow of the network is no less than the demand d . The popular methods in the literature to evaluate the network reliability are mostly through minimal paths (MP) or minimal cuts (MC) of the network. One of them is the three-stages method: (a) searching for all MPs/MCs; (b) searching for all d -MPs (the minimal system states for d via MP)/ d -MCs (the maximal system states for d via MC); (c) calculating union probability from these d -MPs/ d -MCs. We found that a creative innovation in solving the maximal flow problems may have benefits in the evaluation of network reliability. Based on this idea, this paper proposes a new approach to tackle the problem of searching for all d -MPs by given MPs. The comparisons with the well known algorithm are made for benchmarking. More complicated examples are also examined for illustrative purposes.

Computer and telecommunication networks are stochastic in nature, as each node and arc may have multiple capacity states besides complete failure. Various two-terminal reliability estimation algorithms for such stochastic flow networks are available in literature. These algorithms generate d-minimal cuts from minimal cut-sets of the network, where d is required demand. Different techniques are available in literature to evaluate exact reliability from such d-minimal cuts such as the recursive inclusion–exclusion method. The recursive inclusion–exclusion method has certain redundant computations while evaluating network reliability. This paper proposes a sum of disjoint products technique to minimize redundant computations in exact reliability computation from flow vectors. MATLAB simulation is performed to evaluate the performance of the proposed method and compare it with the existing methods for benchmark networks available in literature. Simulation results show that the proposed method require lesser computational efforts and memory.

In this paper, we investigate system reliability optimization of multi-source multi-sink flow networks subject to transmission budget constraints. More specifically, we present a mathematical model of the optimization problem and a genetic algorithm (GA) to solve it. The GA is based on determining the optimal set of lower boundary points that maximize system reliability such that transmission cost does not exceed a specified upper bound. Finally, to ensure the efficiency of our approach, we apply our proposed algorithm to various network examples.

In this paper, a new heuristic algorithm is constructed for four machines stochastic flow shop scheduling problem to utilized stochastic processing times and stochastic sequence dependent setup times of the jobs on the machines simultaneously. The main objective to construct this heuristic algorithm is to find the optimal or near optimal sequence to minimize the makespan, total utilization time of the machines and total rental cost of all the hired machines. A numerical example is provided to verify the effectiveness of the developed heuristic algorithm.

We extend Stochastic Flow Models (SFMs), used for a large class of discrete event and hybrid systems, by including the delays which typically arise in flow movement. We apply this framework to the multi-intersection traffic light control problem by including transit delays for vehicles moving from one intersection to the next. Using Infinitesimal Perturbation Analysis (IPA) for this SFM with delays, we derive new on-line gradient estimates of several congestion cost metrics with respect to the controllable green and red cycle lengths. The IPA estimators are used to iteratively adjust light cycle lengths to improve performance and, in conjunction with a standard gradient-based algorithm, to obtain optimal values which adapt to changing traffic conditions. We introduce two new cost metrics to better capture congestion and show that the inclusion of delays in our analysis leads to improved performance relative to models that ignore delays.

The system reliability (Rd,c) calculation is based on the generation of all the lower boundary points for the given demand, d, such that the total transmission cost is less than or equal to c (budget). This generation of the lower boundary points is based on finding all feasible solutions to the flow vector, F. The number of feasible solutions cannot be anticipated. Thus, a genetic algorithm is useful for solving this problem. Therefore, this paper presents a genetic algorithm to generate all feasible solutions to the flow vector, F, and then calculate Rd,c. The algorithm is applied to two problem models. In the first, each arc of a flow network has several capacities and may fail. In the second, both the arc and node have several capacities and may fail. The results show that the algorithm is efficient at solving a flow problem and is useful for calculating Rd,c.

In this paper, we investigate the relevance of the stochastic nature of water demand for backtracing of contaminations in drinking water distribution networks. We present an approach to deal with the uncertainty introduced by stochastic demand, which is applied to a full detail part (all pipes) of a hydraulic model of a distribution network in the Netherlands. It is demonstrated that stochastic water demand can introduce significant amounts of uncertainty for backtracing in some parts of tertiary (reticulation) networks in specific, looped configurations. In other parts, the additional uncertainty introduced by stochastic water demand can be limited.

A flow shop scheduling problem with uncertain processing times and machine break down is considered in this paper. The objective is to minimise the maximum completion time (makespan). As the problem is non-deterministic polynomial-time hard (NP-hard), a hybrid algorithm (HA) is proposed to solve the problem. The firefly algorithm (FA) is hybridised with the variable neighbourhood search (VNS) algorithm in the proposed HA. Extensive computational experiments are carried out with random problem instances to validate the performance of the proposed algorithm.

In this research, minimizing the expected number of tardy jobs in a dynamic m machine flow-shop scheduling problem, i.e., $$ {F_m}\left| {{r_j}\left| {{\text{E}}\left[ {\sum {{U_j}} } \right]} \right.} \right. $$ is investigated. It is assumed that the jobs with deterministic processing times and stochastic due dates arrive randomly to the flow-shop cell. The due date of each job is assumed to be normally distributed with known mean and variance. A dynamic method is proposed for this problem by which the m machine stochastic flow-shop problem is decomposed into m stochastic single-machine sub-problems. Then, each sub-problem is solved as an independent stochastic single-machine scheduling problem by a mathematical programming model. Comparison of the proposed method with the most effective rule of thumb for the proposed problem, i.e., shortest processing time first rule shows that the proposed method performs 23.9 % better than the SPT rule on average for industry-size scheduling problems.

Reducing the transmission time for a flow network is an essential task. The quickest path problem thus arises to find a path with minimum transmission time. More specifically, the capacity of each arc in the network is assumed to be deterministic. Nevertheless, the capacity of each arc is stochastic due to failure, maintenance, etc. Such a network is named as a stochastic-flow network. Hence, the minimum transmission time is not a fixed number. We extend the quickest path problem to a system reliability problem that d units of data are required to be sent from the source to the sink under the time threshold T. The possibility to fulfill such requirements is named as the system reliability. In particular, the data can be transmitted through two disjoint minimal paths simultaneously. A simple algorithm is proposed to generate all lower boundary points for (d,T) and the system reliability can be subsequently computed in terms of such points. Moreover, the optimal pair of paths with highest system reliability can be further obtained.

This paper constructs a revised stochastic flow network to model a realistic computer network in which each arc has a lead time and a stochastic capacity. The minimum time to send a specified amount of data through the network is thus uncertain. Hence, this paper mainly proposes an approach for evaluating the system reliability that d units of data can be transmitted through k minimal paths simultaneously within the time threshold T . The idea of lower boundary points for ( d , T ), the minimal system states satisfying the demand d within the time threshold T , is proposed firstly. All system states meeting the time and demand requirements can be represented as the union of subsets generated from all lower boundary points for ( d , T ), and thus the system reliability is computed quickly.

We present a stochastic hybrid system framework for Stochastic Flow Models (SFMs) with multiple classes and class-dependent performance objectives. Using Infinitesimal Perturbation Analysis (IPA) estimators for the derivatives of such objectives, we formulate and solve resource contention games that contrast system-centric and user-centric optimization in such SFMs.

Consideration was given to estimation of the parameters of the synchronous twofold-stochastic flow of events which makes up a mathematical model of the information flow of demands circulating in the queuing systems and networks. Two variants were studied. For the first variant, the problem of optimal estimation of the parameters of a synchronous flow of events with a finite arbitrary number of states was solved. The second variant differs in that the event flow operates in the environment where part of events is lost during the so-called dead time. Consideration was given to a synchronous flow with two states. The problem of estimating the length of the dead time in the conditions of continued dead time was solved. The results of numerical estimation based on the simulation model of the synchronous flow were presented for both variants.

The flow shop scheduling with the no-wait constraint is a typical NP-hard combinatorial optimization problem and represents an important area in production scheduling. In this paper, a class of particle swarm optimization (PSO) approach with simulated annealing (SA) and hypothesis test (HT), namely PSOSAHT is proposed for the stochastic flow shop scheduling with no-wait constraint to minimize the maximum completion time (makespan). The developed algorithm not only applies evolutionary search guided by the mechanism of PSO, but it also applies the local search guided by the jumping mechanism of SA. Thus, both global exploration and local exploitation are balanced. Meanwhile, it applies HT to perform a statistical comparison to avoid some repeated search to some extent. Simulation results and comparisons demonstrate the feasibility, effectiveness and robustness of the proposed hybrid PSO-based algorithm.

Solving d-MC problem is often a tedious process. Three ways are suggested to improve the efficiency of solving d-MC problem. The first way is to make the best use of some special properties of network. A property of Network with Joint Parallel Part, which is more common than series–parallel network, is illustrated. The second way is to reduce the number of d-MC candidates and then to reduce the cost of testing. Two theorems on how to find the d-MCs with only one element unsaturated and on how to set the Lower Capacity Limits (LCLs) of elements to some values higher than zero are proved. These two theorems will be helpful to reduce d-MC candidates without any loss of real d-MC. The third way is to efficiently remove the duplicated d-MCs. A theorem, elucidating which Minimal Cuts (MCs) the duplicated d-MCs will be generated from, is proved. Finally, an algorithm is proposed by adding a pre-numerating step to the algorithm presented in Yeh [A new approach to the d-MC problem. Reliab Eng Syst Safety 2002;77(2):201–6], and two examples are employed to illustrate the proposed algorithm, especially the pre-numerating step.

© 2015 Elsevier Inc. We characterize the revenue-maximizing mechanism for time separable allocation problems in continuous time. The willingness-to-pay of each agent is private information and changes over time.We derive the dynamic revenue-maximizing mechanism, analyze its qualitative structure and frequently derive its closed form solution. In the leading example of repeat sales of a good or service, we establish that commonly observed contract features such as flat rates, free consumption units and two-part tariffs emerge as part of the optimal contract. We investigate in detail the environments in which the type of each agent follows an arithmetic or geometric Brownian motion or a mean-reverting process. We analyze the allocative distortions and show that depending on the nature of the private information the distortion might increase or decrease over time.

Both minimal paths and minimal cuts are important media to evaluate the performance indexes, the system reliability or unreliability, for a single-commodity stochastic-flow network. This paper concentrates on a multicommodity stochastic-flow network in which each arc has both the capacity and cost attributes. Different from the single-commodity case, the system capacity is a pattern for multicommodity case. Since the traditional performance indexes are not suitable for multicommodity case, we propose a new performance index, the probability that the system capacity is less than or equal to a given pattern under the budget constraint. A simple algorithm based on minimal cuts is presented to generate all (d,B)-MCs that are the maximal capacity vectors meeting the demand d and budget B. The proposed performance index can be evaluated in terms of (d,B)-MCs.

Stochastic flow shop scheduling is a typical and widely studied NP-hard stochastic optimisation problem with strong industrial roots. However, due to inaccurate estimation of objective values, NP-hardness and a limited computing budget, it is generally hard to solve such stochastic optimisation problems effectively and efficiently. Based on the idea of order comparison and goal softening, ordinal optimisation (OO) has been widely applied for stochastic optimisation. In this paper, OO and optimal computing budget allocation (OCBA) as well as a genetic algorithm (GA) are reasonably hybridised to propose an effective genetic ordinal optimisation (GOO) approach for flow shop scheduling with stochastic processing times. In GOO, limited computing effort can be intelligently allocated by OCBA to provide reliable and robust evaluation and identification of good solutions in a population, and the solution space can be well explored by an order-based evolutionary genetic search with the good solutions identified by OCBA. Simulation results based on benchmarks demonstrate the effectiveness of the GOO by comparison with traditional methods. Moreover, the effects of some parameters on the optimisation performance are discussed.

Estimation of the states of a synchronous double stochastic flow of events with an arbitrary (finite) number of states was considered. The flow is a mathematical model of the information flows of the customers circulating in the queuing systems and networks. An explicit form of the a posteriori probabilities representing the total characteristics of the flow of event was determined. Decision about the state of flow is made using the criterion for maximum of the a posteriori probability. Numerical calculations of the a posteriori probabilities and statistical experiments with a simulation model are illustrated.

System reliability evaluation for flow networks is an important issue in quality management. This paper concentrates on a stochastic-flow network in which nodes as well as branches have several possible capacities, and can fail. The possibility is evaluated that a given amount of messages can be transmitted through the stochastic-flow network under the budget constraint. Such a possibility, system reliability, is a performance index for a stochastic-flow network. A minimal path, an order sequence of nodes & branches from the source to the sink without cycles, is used to assign the flow to each component (branch or node). A lower boundary point for (d, C) is a minimal capacity vector, which enables the system to transmit d messages under the budget C. Based on minimal paths, an efficient algorithm is proposed to generate all lower boundary points for (d, C). The system reliability can then be calculated in terms of all lower boundary points for (d, C) by applying the inclusion-exclusion rule. Simulation shows that the implicit enumeration (step 1) of the proposed algorithm can be executed efficiently.

From the point of view of quality management, it is an important issue to reduce the transmission time in the network. The quickest path problem is to find the path in the network to send a given amount of data from the source to the sink such that the transmission time is minimized. Traditionally, this problem assumed that the capacity of each arc in the network is deterministic. However, the capacity of each arc is stochastic due to failure, maintenance, etc. in many real-life networks. This paper proposes a simple algorithm to evaluate the probability that d units of data can be sent from the source to the sink through the stochastic-flow network within T units of time. Such a probability is called the system reliability. The proposed algorithm firstly generates all lower boundary points for (d, T) and the system reliability can then be computed in terms of such points.

System reliability evaluation for flow networks is an important issue for quality performance. This paper studies the system reliability that a given amount of multicommodity can be transmitted through a stochastic-flow network under the budget constraint, where each node and each arc has several possible capacities. Such reliability is named multicommodity reliability throughout this paper. A simple algorithm is proposed to generate all lower boundary points for (d^1, d^2,…,d(superscript p);C) where d(superscript i) is the demand of commodity i and C is the budget. The multicommodity reliability can then be calculated in terms of such points.

This paper considers a stochastic-flow network, in which each node as well as each arc has several capacities and may fail, which allows each commodity to be transmitted from the source to the sink. Given the demand for each commodity, the evaluation of the system reliability to fulfill the demand is performed. At first, a simple algorithm is proposed to generate all lower boundary points for the demand, and then the system reliability can be calculated in terms of such points. An example is shown to illustrate the solution procedure. Scope and purpose Assuming that the arcs of a flow network are deterministic, the multicommodity maximum flow (MMF) problem is a standard one in network analysis and operations research. The purpose of this paper is to extend the MMF problem to a stochastic-flow network in which arcs and nodes all have several capacities and may fail. We evaluate the probability (named system reliability here) that the system satisfies the demand for each commodity simultaneously. Such a probability can be treated as a performance index for many supply–demand systems such as computer systems, telecommunication systems, logistics systems, etc.

For a deterministic flow network, the system capacity in single-commodity case is the maximum value of flow from the source node to the sink node. In a multicommodity stochastic-flow network with node failure (arcs and nodes all have several possible capacities and may fail), different types of commodities are transmitted through the same network simultaneously and compete the capacities. This paper defines the system capacity as a pattern for a multicommodity stochastic-flow network with node failure. And we propose a performance index, the probability that the upper bound of the system capacity is a given pattern, to evaluate the performance for a system. An algorithm based on the properties of minimal cuts is proposed to evaluate such a performance index.

A problem is solved (by the method of instants) for the estimation of the parameters of a double-stochastic flow of events when each recorded event gives rise to the period of a dead time over which other events of the flow are inaccessible for the observation.

This paper is mainly to extend the multi‐commodity minimum cost flow problem from deterministic cases to stochastic cases. Under budget constraint, we propose an approach to calculate the probability that the required amount of multiple commodities can be transported simultaneously through a stochastic flow network. Such a probability is called system reliability. An algorithm is proposed first to find out all lower boundary points for the requirement in terms of minimal paths. The system reliability can then be calculated in terms of such lower boundary points.

From the point of view of quality management, it is an important issue to develop some performance indexes for a flow network. This paper studies the performance indexes for a stochastic-flow network in which each arc has several possible capacities. For the case that multiple types of commodity are transmitted through the same stochastic-flow network, this paper defines the system capacity as a vector and then proposes a new performance index. An algorithm in terms of minimal cuts is proposed to evaluate such a performance index.

Large deviations for stochastic flow solutions to SDEs containing a small parameter are studied. The obtained results are applied to establish a C p,r -large deviation principle for stochastic flows and for solutions to anticipating SDEs. The recent results of Millet-Nualart-Sans and Yoshida are improved and refined.

This paper defines the problem of buffer space allocation in flow lines as an investment problem. A model is developed and solution techniques are described that can be used to determine buffer allocations that maximize the expected net present value of the investment, including machines, buffers and inventory. Production rates and inventory levels are explicitly linked to projected cash flow to assess the economic consequences of the buffer allocation. Several examples of linear flow lines as well as assembly/disassembly systems and flow lines with rework loops are analysed numerically. These examples demonstrate the importance of the buffer allocation problem and provide intuition with respect to the structure of optimized solutions. A result is that as product quality in a system with a rework loop improves, an optimally designed system can receive more buffer spaces and may use more inventory. This possibly counterintuitive result is due to the economic perspective on the buffer allocation problem.

In a stochastic-flow network, each arc has several capacity levels. Given the system demand d, the reliability of such a network for demand d (i.e., the probability that the maximum flow is not less than d) can be computed in terms of d-MCs. Jane, Lin and Yuan have presented an algorithm to generate all d-MCs in terms of minimal cuts. This article proposes another algorithm, which is based on the more publicly accepted “comparison” method, to evaluate the reliability. To compare such two algorithms, one example is illustrated to show how d-MCs are generated differently. Also, the computational complexity is analyzed.

The problem of estimating the drift of a stochastic flow given Lagrangian observations is an estimation problem for a multidimensional diffusion with a degenerate diffusion matrix. The maximum-likelihood estimator of the constant drift is considered. A long-time asymptotic of its mean-square error (MSE) is computed. It is shown that the time-space average of the observed Lagrangian velocities has the same asymptotic. These estimators are compared to the least-squares estimator based on Eulerian data. In the most important, for applications, two-dimensional case the Lagrangian estimator is typically preferable for incompressible flows, while for flows close to potential the Eulerian estimator is better.

Quickest path problems (QPPs) have gained considerable attention of researchers in the last two decades due to their enormous applications in a variety of networks such as communication and transportation networks. Most of such networks are classified as stochastic flow network due to their changing states with time. Algorithms have been proposed in the literature to evaluate the probability that a specified amount of data could be transmitted from a source to the sink through a stochastic flow network within a given amount of time. In order to reduce the transmission time while maintaining system reliability, Lin [27, 28] has proposed using multiple disjoint paths for transmission of data/items by distributing the load into two or more segments. The algorithm presented in [26] efficiently solves the problem of finding the most reliable pair of paths among all available pairs from a source to the sink. However, the process of determining the most reliable pair of disjoint paths consumes considerable amount of time and it is practically non-feasible to wait for pair of disjoint paths with highest probability in order to transmit the data/items. In view of this, we have proposed a threshold of probability and pairs of paths that cross the threshold are considered for communication of data. Instead of a globally optimized solution, we focus on minimizing the time to compute the system reliability. We have also presented a comparison of the performance of the proposed method with the method presented in [27] for different graphs. The results show marked improvement in the system overhead for reliability computation without much compromise on the quality of service, since the pair satisfies a minimum reliability constraint. The method is particularly useful for applications involving large networks.

Existing analysis approaches to flow networks are discussed. A common failure of the classical methods for maximising the throughput flow is identified – the presence of undesirable directed loops of parasitic flows in the optimised networks. It is also shown that approaches related to stochastic flow networks are invariably based on minimal cut sets or paths sets. Although for small-size networks, an approach based on minimal cut sets or paths sets is feasible; for medium-size and large-size networks this approach is unacceptable. With increasing network size, the number of minimum cut sets and path sets increases exponentially.

When job parameters are uncertain or unpredictable, new types of policies become possible. Besides static policies, we now should consider dynamic policies, with or without preemption. Objectives too have more variety. The makespan, for example, is now random; we usually choose to minimize its expectation.

We consider a m machine stochastic flow-shop and a set of n jobs, with known release dates, to be processed. In this paper, we distinguish two types of random events: processing times (job processing times are random variables which follow a probability distribution function) and breakdowns (time between failure and repair time are random variables). The main purpose of this paper is to review and to propose a classification for some developments about the static stochastic flow-shop scheduling problem. We propose also an extension of the notation of Graham, Lawler, Lenstra, and Rinnooy Kan in order to take into account random events.

Birth and Death on a flow refers to a particle system on a stochastic flow. Particles are born in a point process and move on the flow subject to position-dependent killing. They die eventually and leave the flow. The particle process is a measure-valued, Markov process tracking these motions. Its law depends on the distribution of births, the coefficients of the flow, and the rate of killing. We parametrize the system and derive a quasi-likelihood for chronicles of integral data on the particle process.

In this paper, a class of non-cooperative games termed resource contention games is studied, modeled through multi-class Stochastic Flow Models (SFMs). We contrast the solutions between system-centric and user-centric optimization in this game setting, and illustrate the gap between the two solutions, which is commonly referred to as the “price of anarchy.”

We revisit, in the context of Stochastic Flow Models (SFMs), a classic scheduling problem for optimally allocating a resource to multiple competing users. For the two-user case, we establish the optimality of the well-known cμ-rule for arbitrary stochastic processes using calculus of variations arguments as well as an Infinitesimal Perturbation Analysis (IPA) approach. The latter allows us to derive an explicit sensitivity estimate of the cost function with respect to a controllable parameter and to further study the problem when the cost function is nonlinear, deriving simple distribution-free cost sensitivity estimates and analyzing why the cμ-rule may fail in this case.

The integrand, when a martingale under an equivalent measure is represented as a stochastic integral, is determined by elementary methods in the Markov situation. Applications to hedging portfolios in finance are described.

In this paper we consider stochastic flow-shop scheduling with reference to certain lateness-related performance measures. We show that for various assumptions on the distribution of job-processing times of a flow shop, certain scheduling policies following the stochastic analogy of the Earliest Due Date (EDD) rule yield optimal results.

A model and an algorithm for reliability optimization in generalized stochastic-flow networks are given. This algorithm uses the relationship of the k-weak-link sets and sets of failure events to the parameters of the generalized stochastic flow networks. This facilitates a fast location of the optimal capacity expansion for a system from the information obtained by the latest iteration and alleviates the dimension calamity on computation. Consequently, this reliability optimization method is powerful for large systems. As an example, the IEEE Reliability Test System with 24 nodes and 70 components was tested, revealing the components and their capacity values which should be enhanced. The computation results show that the algorithm can be applied to practical problems. >