Scheduling Markovian PERT networks to maximize the net present value: New results

We study project scheduling so as to maximize the expected net present value when task durations are exponentially distributed. Based on the structural properties of an optimal solution we show that, even if preemption is allowed, it is not necessary to do so. Next to its managerial importance, this result also allows for a new algorithm which improves on the current state of the art with several orders of magnitude, both in CPU time and in memory usage.     

Multi-objective time–cost trade-off in dynamic PERT networks using an interactive approach

We develop a multi-objective model for the time–cost trade-off problem in a dynamic PERT network using an interactive approach. The activity durations are exponentially distributed random variables and the new projects are generated according to a renewal process and share the same facilities. Thus, these projects cannot be analyzed independently. This dynamic PERT network is represented as a network of queues, where the service times represent the durations of the corresponding activities and the arrival stream to each node follows a renewal process. At the first stage, we transform the dynamic PERT network into a proper stochastic network and then compute the project completion time distribution by constructing a continuous-time Markov chain. At the second stage, the time–cost trade-off problem is formulated as a multi-objective optimal control problem that involves four conflicting objective functions. Then, the STEM method is used to solve a discrete-time approximation of the original problem. Finally, the proposed methodology is extended to the generalized Erlang activity durations.     

Lower bound for the mean project completion time in dynamic PERT networks

We apply the stochastic dynamic programming to obtain a lower bound for the mean project completion time in a PERT network, where the activity durations are exponentially distributed random variables. Moreover, these random variables are non-static in that the distributions themselves vary according to some randomness in society like strike or inflation. This social randomness is modelled as a function of a separate continuous-time Markov process over the time horizon. The results are verified by simulation.     

Approximate evaluation of multi-location inventory models with lateral transshipments and hold back levels

We consider a continuous-time, single-echelon, multi-location inventory model with Poisson demand processes. In case of a stock-out at a local warehouse, a demand can be fulfilled via a lateral transshipment (LT). Each warehouse is assigned a pre-determined sequence of other warehouses where it will request for an LT. However, a warehouse can hold its last part(s) back from such a request. This is called a hold back pooling policy, where each warehouse has hold back levels determining whether a request for an LT by another warehouse is satisfied. We are interested in the fractions of demand satisfied from stock (fill rate), via an LT, and via an emergency procedure from an external source. From these, the average costs of a policy can be determined. We present a new approximation algorithm for the evaluation of a given policy, approximating the above mentioned fractions. Whereas algorithms currently known in the literature approximate the stream of LT requests from a warehouse by a Poisson process, we use an interrupted Poisson process. This is a process that is turned alternatingly On and Off for exponentially distributed durations. This leads to the On/Off overflow algorithm. In a numerical study we show that this algorithm is significantly more accurate than the algorithm based on Poisson processes, although it requires a longer computation time. Furthermore, we show the benefits of hold back levels, and we illustrate how our algorithm can be used in a heuristic search for the setting of the hold back levels.     

Maximizing the net present value of a project under uncertainty

We address the maximization of a project’s expected net present value when the activity durations and cash flows are described by a discrete set of alternative scenarios with associated occurrence probabilities. In this setting, the choice of scenario-independent activity start times frequently leads to infeasible schedules or severe losses in revenues. We suggest to determine an optimal target processing time policy for the project activities instead. Such a policy prescribes an activity to be started as early as possible in the realized scenario, but never before its (scenario-independent) target processing time. We formulate the resulting model as a global optimization problem and present a branch-and-bound algorithm for its solution. Extensive numerical results illustrate the suitability of the proposed policy class and the runtime behavior of the algorithm.     

Gossip algorithms for heterogeneous multi-vehicle routing problems

In this paper we address a class of heterogeneous multi-vehicle task assignment and routing problems. We propose two distributed algorithms based on gossip communication: the first algorithm is based on a local exact optimization and the second is based on a local approximate greedy heuristic. We consider the case where a set of heterogeneous tasks arbitrarily distributed in a plane has to be serviced by a set of mobile robots, each with a given movement speed and task execution speed. Our goal is to minimize the maximum execution time of robots.     

Primal and dual algorithms for optimization over the efficient set

ABSTRACT

Optimization over the efficient set of a multi-objective optimization problem is a mathematical model for the problem of selecting a most preferred solution that arises in multiple criteria decision-making to account for trade-offs between objectives within the set of efficient solutions. In this paper, we consider a particular case of this problem, namely that of optimizing a linear function over the image of the efficient set in objective space of a convex multi-objective optimization problem. We present both primal and dual algorithms for this task. The algorithms are based on recent algorithms for solving convex multi-objective optimization problems in objective space with suitable modifications to exploit specific properties of the problem of optimization over the efficient set. We first present the algorithms for the case that the underlying problem is a multi-objective linear programme. We then extend them to be able to solve problems with an underlying convex multi-objective optimization problem. We compare the new algorithms with several state of the art algorithms from the literature on a set of randomly generated instances to demonstrate that they are considerably faster than the competitors.     

The complexity of generating an exponentially distributed variate

We analyze in detail an almost optimal algorithm for generating an exponentially distributed variate. The algorithm is due to Knuth and Yao and relies on a method which goes back to J. von Neumann. It is shown here that it can generate k bits of an exponentially distributed variate using an average of about k + 5.67974692 coin flippings. This solves a problem left open by Knuth and Yao.     

An adaptive,multiple restarts neural network algorithm for graph coloring

The graph coloring problem is amongst the most difficult ones in combinatorial optimization, with a diverse set of significant applications in science and industry. Previous neural network attempts at coloring graphs have not worked well. In particular, they do not scale up to large graphs. Furthermore, experimental evaluations on real-world graphs have been lacking, and so have comparisons with state of the art conventional algorithms. In this paper we address all of these issues. We develop an improved neural network algorithm for graph coloring that scales well with graph size. The algorithm employs multiple restarts, and adaptively reduces the network's size from restart as it learns bettwe ways to color a given graph. Hence it gets faster and leaner as it evolves. We evaluate this algorithm on a structurally diverse set of graphs that arise in different applications. We compare its performance with that of a state of the art conventional algorithm on identical graphs. The conventional algorithm works better overall, though ours is not far behind. Ours works better on some graphs. The inherent parallel and distributed nature of our algorithm, especially within a neural network architecture, is a potential advantage for implementation and speed up.     

Stochastic Decomposition in M/M/∞ Queues with Markov Modulated Service Rates

Motivated by the need to study transportation systems in which incidents cause traffic to slow down, we consider an M/M/∞ queueing system subject to random interruptions of exponentially distributed durations. System breakdowns, where none of the servers work, as well as partial failures, where all servers work with lower efficiency, are investigated. In both cases, it is shown that the number of customers present in the system in equilibrium is the sum of two independent random variables. One of these is the number of customers present in an ordinary M/M/∞ queue without interruptions.     

Branch and bound based solution algorithms for the budget constrained discrete time/cost trade-off problem

The time/cost trade-off models in project management aim to reduce the project completion time by putting extra resources on activity durations. The budget problem in discrete time/cost trade-off scheduling selects a time/cost mode for each activity so as to minimize the project completion time without exceeding the available budget. There may be alternative modes that solve the budget problem optimally and each solution may have a different total cost value. In this study we consider the budget problem and aim to find the minimum cost solution among the minimum project completion time solutions. We analyse the structure of the problem together with its linear programming relaxation and derive some mechanisms for reducing the problem size. We solve the reduced problem by branch and bound based optimization and heuristic algorithms. We find that our branch and bound algorithm finds optimal solutions for medium-sized problem instances in reasonable times and the heuristic algorithms produce high quality solutions very quickly.     

A new path-based cutting plane approach for the discrete time-cost tradeoff problem

Determining discrete time-cost tradeoffs in project networks allows for the control of the processing time of an activity via the amount of non-renewable resources allocated to it. Larger resource allocations with associated higher costs reduce activities’ durations. Given a set of execution modes (time-cost pairs) for each activity, the discrete time-cost tradeoff problem (DTCTP) involves selecting a mode for each activity so that either: (i) the project completion time is minimized, given a budget, or (ii) the total project cost is minimized, given a deadline, or (iii) the complete and efficient project cost curve is constructed over all feasible project durations. The DTCTP is a problem with great applicability prospects but at the same time a strongly N P{\mathcal N}\,P-hard optimization problem; solving it exactly has been a real challenge. Known optimal solution methodologies are limited to networks with no more than 50 activities and only lower bounds can be computed for larger, realistically sized, project instances. In this paper, we study a path-based approach to the DTCTP, in which a new path-based formulation in activity-on-node project networks is presented. This formulation is subsequently solved using an exact cutting plane algorithm enhanced with speed-up techniques. Extensive computational results reported for almost 5,000 benchmark test problems demonstrate the effectiveness of the proposed algorithm in solving to optimality for the first time some of the hardest and largest instances in the literature. The promising results suggest that the algorithms may be embedded into project management software and, hence, become a useful tool for practitioners in the future.     

Using Discrete and Continuous Models to Solve Nanoporous Flow Optimization Problems

We consider using a discrete network model in combination with continuous nonlinear optimization models to solve the problem of optimizing channels in nanoporous materials. The problem and the hierarchical optimization algorithm are described in [2]. A key feature of the model is the fact that we use the edges of the finite element grid as the locations of the channels. The focus here is on the use of the discrete model within that algorithm. We develop several approximations to the relevant flow and a greedy algorithm for quickly generating a "good" tree connecting all of the nodes in the finite-element mesh to a designated root node. We also consider Metropolis-Hastings (MH) improvements to the greedy result. We consider both a regular triangulation and a Delaunay triangulation of the region, and present some numerical results.     

求解CPM网络计划的最大网络时差

CPM网络计划的网络时差表示项目中各工序实际可使用的机动时间的总和(绝非理论上机动时间的简单加总),即CPM网络计划的总机动时间,它决定着在总工期不变的前提下,所有工序实际可以达到的最大工期的总和,与项目的成本管理和时间管理密切相关。网络时差是变量,取决于各工序的时间进度安排,说明可以通过调整工序的时间进度来决定该时差的取值,特别是其最大值,进而实现成本和时间优化。本文首先从新的角度分析了网络时差的含义;然后,在此基础上设计了求解最大网络时差的算法,其思路为,通过建立和分析最大网络时差模型,将其转化为特殊的“时间-费用权衡问题”,进而可运用Fulkerson算法等经典算法求解;最后,通过应用举例对该算法进行了演示。     

On mixed finite element approximations of shape gradients in shape optimization with the Navier–Stokes equation

For shape optimization of fluid flows governed by the Navier–Stokes equation, we investigate effectiveness of shape gradient algorithms by analyzing convergence and accuracy of mixed finite element approximations to both the distributed and boundary types of shape gradients. We present convergence analysis with a priori error estimates for the two approximate shape gradients. The theoretical analysis shows that the distributed formulation has superconvergence property. Numerical results with comparisons are presented to verify theory and show that the shape gradient algorithm based on the distributed formulation is highly effective and robust for shape optimization.     

随机活动工期下求解资源约束项目最大期望净现值的动态调度算法

本文研究了随机活动工期下如何调度资源约束项目使得项目的期望净现值最大。首先对问题进行了界定,建立了相应的优化模型,其次针对问题的特点设计了一种动态规划算法。在算法设计的过程中,本文通过对项目网络图结构及不同状态最优值之间关系的分析,优化了动态规划算法状态的生成过程及状态最优值的求解过程,从而加快了算法的求解。使用随机生成的540个不同规模、不同结构的仿真案例对算法的有效性进行了验证,并分析了项目网络特征对算法效率的影响。实验发现：项目的次序强度对算法所需时间有着较大的影响,随着项目次序强度的减小,生成的状态数量会增加,从而计算时间也会增加。本文的研究可以为不确定环境下的项目调度提供决策支持。     

Performance analysis of polling systems with retrials and glue periods

We consider gated polling systems with two special features: (i) retrials and (ii) glue or reservation periods. When a type-i customer arrives, or retries, during a glue period of the station i, it will be served in the following service period of that station. Customers arriving at station i in any other period join the orbit of that station and will retry after an exponentially distributed time. Such polling systems can be used to study the performance of certain switches in optical communication systems. When the glue periods are exponentially distributed, we obtain equations for the joint generating functions of the number of customers in each station. We also present an algorithm to obtain the moments of the number of customers in each station. When the glue periods are generally distributed, we consider the distribution of the total workload in the system, using it to derive a pseudo-conservation law which in turn is used to obtain accurate approximations of the individual mean waiting times. We also investigate the problem of choosing the lengths of the glue periods, under a constraint on the total glue period per cycle, so as to minimize a weighted sum of the mean waiting times.     

Performance analysis of distributed solution approaches in simulation-based optimization

Applying computationally expensive simulations in design or process optimization results in long-running solution processes even when using a state-of-the-art distributed algorithm and hardware. Within these simulation-based optimization problems the optimizer has to treat the simulation systems as black-boxes. The distributed solution of this kind of optimization problem demands efficient utilization of resources (i.e. processors) and evaluation of the solution quality. Analyzing the parallel performance is therefore an important task in the development of adequate distributed approaches taking into account the numerical algorithm, its implementation, and the used hardware architecture. In this paper, simulation-based optimization problems are characterized and a distributed solution algorithm is presented. Different performance analysis techniques (e.g. scalability analysis, computational complexity) are discussed and a new approach integrating parallel performance and solution quality is developed. This approach combines a priori and a posteriori techniques and can be applied in early stages of the solution process. The feasibility of the approach is demonstrated by applying it to three different classes of simulation-based optimization problems from groundwater management.     

Simultaneous optimization of capacity and planned lead time in a two-stage production system with different customer due dates

We consider a two-stage make-to-order manufacturing system with random demands, processing times, and distributed customer due dates. The work to each stage is released based on a planned lead time. A general approach to minimize total inventory holding and customer order tardiness cost is presented to find the optimal manufacturing capacities and planned lead times for each manufacturing stage. Expressions are derived for work-in process inventories, finished-goods-inventory and expected backorders under the assumption of a series of M/M/1 queuing systems and exponentially distributed customer required lead times. We prove that the distribution of customer required lead time has no influence on the optimal planned lead times whenever capacity is predefined but it influences the optimal capacity to invest into. For the simultaneous optimization of capacity and planned lead times we present a numerical study that shows that only marginal cost decreases can be gained by setting a planned lead time for the upstream stage and that a considerable cost penalty is incurred if capacity and planned lead time optimization are performed sequentially.     

Determination of critical chain project buffer based on information flow interactions

It has been well accepted in the literature that co-dependency between project activity durations is caused by resource tightness and network complexity. However, we show that information flow interaction between activities is the key factor for it. Based on whether there exist spliced relationships between activities, we introduce the concept of rework safety time. We propose a method to compute the rework safety time using the information output and input time factors, rework probability matrix, and rework impact matrix. We achieve the optimization of the critical chain sequencing via the design structure matrix so that the dependency between activities is reduced. The project buffer is then determined by the tail concentration method based on the optimized chain. The empirical results show that, as opposed to the traditional RSEM method, our approach improves the project buffer consumption rate, shortens project duration, reduces project cost, and increases project on-time completion rate.