On the use of the complexity index as a measure of complexity in activity networks

A large number of optimal and suboptimal procedures have been developed for solving combinatorial problems modeled as activity networks. The need to differentiate between easy and hard problem instances and the interest in isolating the fundamental factors that determine the computing effort required by these procedures, inspired a number of researchers to develop various complexity measures. In this paper we investigate the relation between the hardness of a problem instance and the topological structure of its underlying network, as measured by the complexity index. We demonstrate through a series of experiments that the complexity index, defined as the minimum number of node reductions necessary to transform a general activity network to a series-parallel network, plays an important role in predicting the computing effort needed to solve easy and hard instances of the multiple resource-constrained project scheduling problem and the discrete time/cost trade-off problem.     

Scheduling for single agile satellite,redundant targets problem using complex networks theory

Scheduling for the Earth observation satellites (EOSs) imaging mission is a complicated combinatorial optimization problem, especially for the agile EOSs (AEOSs). The increasing observation requirements and orbiting satellites have exacerbated the scheduling complexity in recent years. In this paper, the single agile satellite, redundant observation targets scheduling problem is studied. We introduce the theory of complex networks and find similarities between AEOS redundant targets scheduling problem and the node centrality ranking problem. Then we model this problem as a complex network, regarding each node as a possible observation opportunity, and define two factors, node importance factor and target importance factor, to describe the node/target importance. Based on the two factors, we propose a fast approximate scheduling algorithm (FASA) to obtain the effective scheduling results. Simulation results indicate the FASA is quite efficient and with broad suitability. Our work is helpful in the EOSs and AEOSs scheduling problems by using complex network knowledge.     

Time complexity of single- and identical parallel-machine scheduling with GERT network precedence constraints

In this paper we deal with the time complexity of single- and identical parallel-machine scheduling problems in which the durations and precedence constraints of the activities are stochastic. The stochastic precedence constraints are given by GERT networks. First, we sketch the basic concepts of GERT networks and machine scheduling with GERT network precedence constraints. Second, we discuss the time complexity of some open single-machine scheduling problems with GERT network precedence constraints. Third, we investigate the time complexity of identical parallel-machine scheduling problems with GERT network precedence constraints. Finally, we present an efficient reduction algorithm for the problem of computing the expected makespan for the latter type of scheduling problem.     

On the topologic structure of economic complex networks: Empirical evidence from large scale payment network of Estonia

This paper presents the first topological analysis of the economic structure of an entire country based on payments data obtained from Swedbank. This data set is exclusive in its kind because around 80% of Estonia's bank transactions are done through Swedbank; hence, the economic structure of the country can be reconstructed. Scale-free networks are commonly observed in a wide array of different contexts such as nature and society. In this paper, the nodes are comprised by customers of the bank (legal entities) and the links are established by payments between these nodes. We study the scaling-free and structural properties of this network. We also describe its topology, components and behaviors. We show that this network shares typical structural characteristics known in other complex networks: degree distributions follow a power law, low clustering coefficient and low average shortest path length. We identify the key nodes of the network and perform simulations of resiliency against random and targeted attacks of the nodes with two different approaches. With this, we find that by identifying and studying the links between the nodes is possible to perform vulnerability analysis of the Estonian economy with respect to economic shocks.     

Robust scheduling and robustness measures for the discrete time/cost trade-off problem

Projects are often subject to various sources of uncertainties that have a negative impact on activity durations and costs. Therefore, it is crucial to develop effective approaches to generate robust project schedules that are less vulnerable to disruptions caused by uncontrollable factors. In this paper, we investigate the robust discrete time/cost trade-off problem, which is a multi-mode project scheduling problem with important practical relevance. We introduce surrogate measures that aim at providing an accurate estimate of the schedule robustness. The pertinence of each proposed measure is assessed through computational experiments. Using the insights revealed by the computational study, we propose a two-stage robust scheduling algorithm. Finally, we provide evidence that the proposed approach can be extended to solve a complex robust problem with tardiness penalties and earliness revenues.     

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

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

A neural network model for scheduling problems

Artificial neural networks (ANNs) have been successfully applied to solve a variety of problems. This paper proposes a new neural network approach to solve the single machine mean tardiness scheduling problem and the minimum makespan job shop scheduling problem. The proposed network combines the characteristics of neural networks and algorithmic approaches. The performance of the network is compared with the existing scheduling algorithms under various experimental conditions. A comprehensive bibliography is also provided in the paper.     

Solving resource-constrained project scheduling problem with evolutionary programming

This paper presents an evolutionary programming (EP)-based approach to solving the resource-constrained project scheduling problem (RCPSP), a well-known NP-hard problem in scheduling, with minimization of project duration as the objective subject to precedence and resource constraints. The individual representation of EP for the problem is based on random keys. The serial generation scheme is used in the decoding scheme to generate the project plan. Experimental analyses are presented to investigate the performance of the proposed EP-based methodology, including comparison of the four variants of EP, namely, CEP, FEP, MCEP and IMCEP, with each other and GA to find the best variant of EP for the RCPSP, and comparison of this best variant of EP (MCEP) with other approaches using the J30 standard instances set in PSPLIB. The computational results validate the effectiveness of the proposed algorithm.     

On the optimal management of project risk

The uncertainty of project networks has been mainly considered as the randomness of duration of the activities. However, another major problem for project managers is the uncertainty due to the randomness of the amount of resources required by each activity which can be expressed by the randomness of its cost. Such randomness can seriously affect the discounted cost of the project and it may be strongly correlated with the duration of the activity.In this paper, a model considering the randomness of both the cost and the duration of each activity is introduced and the problem of project scheduling is studied in terms of the project's discounted cost and of the risk of not meeting its completion time. The adoption of the earliest (latest) starting time for each activity decreases (increases) the risk of delays but increases (decreases) the discounted cost of the project. Therefore, an optimal compromise has to be achieved. This problem of optimization is studied in terms of the probability of the duration and of the discounted cost of the project falling outside the acceptable domain (Risk function) using the concept of float factor as major decision variable. This last concept is proposed to help the manager to synthetize the large number of the decision variables representing each schedule for the studied project. Numerical results are also presented for a specific project network.     

Exploring communication networks to understand organizational crisis using exponential random graph models

In recent social network studies, exponential random graph (ERG) models have been used comprehensively to model global social network structure as a function of their local features. In this study, we describe the ERG models and demonstrate its use in modelling the changing communication network structure at Enron Corporation during the period of its disintegration. We illustrate the modelling on communication networks, and provide a new way of classifying networks and their performance based on the occurrence of their local features. Among several micro-level structures of ERG models, we find significant variation in the appearance of A2P (Alternating k-two-paths) network structure in the communication network during crisis period and non-crisis period. We also notice that the attribute of hierarchical positions of actors (i.e., high rank versus low rank staff) have impact on the evolution process of networks during crisis. These findings could be used in analyzing communication networks of dynamic project groups and their adaptation process during crisis which could lead to an improved understanding how communications network evolve and adapt during crisis.     

A solution procedure for the discrete time, cost and quality tradeoff problem using electromagnetic scatter search

Decisions concerning a project’s expedition, traditionally involved considerations regarding time and cost tradeoff. It was recently suggested that the quality of a project should also be taken into considerations. In this paper, we propose a meta-heuristic solution procedure for the discrete time, cost and quality tradeoff problem. This problem involves the scheduling of project activities in order to minimize the total cost of the project while maximizing the quality of the project and also meeting a given deadline. We apply a so called electromagnetic scatter search to solve this problem. In this process, we initially generate a population of feasible solutions. In so doing, we use frequency memory to well sample the feasible region. A number of these solutions are then selected and improved locally. The improved solutions are then combined to generate new set of solutions. The combination process utilizes attraction–repulsion mechanisms borrowed from the electromagnetism theory. The whole process is stopped when no significant improvement in the set of solutions are observed. The validity of the proposed solution procedure is demonstrated, and its applicability is tested on a randomly generated large and complex problem having 19,900 activities.     

Computational experience with a difficult mixedinteger multicommodity flow problem

The following problem arises in the study of lightwave networks. Given a demand matrix containing amounts to be routed between corresponding nodes, we wish to design a network with certain topological features, and in this network, route all the demands, so that the maximum load (total flow) on any edge is minimized. As we show, even small instances of this combined design/routing problem are extremely intractable. We describe computational experience with a cutting plane algorithm for this problem.This research was partially supported by a Presidential Young Investigator Award and the Center for Telecommunications Research, Columbia University.Corresponding author.     

Optimization architecture for joint multi-path routing and scheduling in wireless mesh networks

In Wireless Mesh Networks (WMN), the optimal routing of data depends on the link capacities which are determined by link scheduling. The optimal performance of the network, therefore, can only be achieved by joint routing and scheduling optimization. Although the joint single-path routing and scheduling optimization problem has been extensively studied, its multi-path counterpart within wireless mesh networks has not yet been fully investigated. In this paper, we present an optimization architecture for joint multi-path QoS routing and the underlying wireless link scheduling in wireless mesh networks. By employing the contention matrix to represent the wireless link interference, we formulate a utility maximization problem for the joint multi-path routing and MAC scheduling and resolve it using the primal–dual method. Since the multi-path routing usually results in the non-strict concavity of the primal objective function, we first introduce the Proximal Optimization Algorithm to get around such difficulty. We then propose an algorithm to solve the routing subproblem and the scheduling subproblem via the dual decomposition. Simulations demonstrate the efficiency and correctness of our algorithm.     

Patrol scheduling in urban rail network

This paper presents the problem of scheduling security teams to patrol a mass rapid transit rail network of a large urban city. The main objective of patrol scheduling is to deploy security teams to stations of the network at varying time periods subject to rostering as well as security-related constraints. We present several mathematical programming models for different variants of this problem. To generate randomized schedules on a regular basis, we propose injecting randomness by varying the start time and break time for each team as well as varying the visit frequency and visit time for each station according to their reported vulnerability. Finally, we present results for the case of Singapore mass rapid transit rail network and synthetic instances.     

A new method for constructing a minimal PERT network

A project is an enterprise consisting of several activities which are to be carried out in some specific order. The activities and the order in which they need to be carried out can be represented by a PERT network. The PERT technique is a traditional, well-known approach to the expert of project management. When networks are used, it often becomes necessary to draw dummy activities. Since the computation of project completion time is proportional to the number of arcs, including dummy arcs, it is desirable to draw a network with as few dummy activities as possible.In this paper, we propose a new method for constructing, for a given project scheduling problem, a PERT network having as small as possible the number of dummy arcs by using some results on line graphs. This algorithm deals with the existence of transitive arcs. The paper contains illustrative examples, proofs of some theoretical results as well as a comparative study with a similar algorithm known in the literature. Computational results showed the superiority of our algorithm.     

Project network models with discounted cash flows a guided tour through recent developments

The vast majority of the project scheduling methodologies presented in the literature have been developed with the objective of minimizing the project duration subject to precedence and other constraints. In doing so, the financial aspects of project management are largely ignored. Recent efforts have taken into account discounted cash flows and have focused on the maximization of the net present value (npv) of the project as the more appropriate objective. In this paper we offer a guided tour through the important recent developments in the expanding field of research on deterministic and stochastic project network models with discounted cash flows. Subsequent to a close examination of the rationale behind the npv objective, we offer a taxonomy of the problems studied in the literature and critically review the major contributions. Proper attention is given to npv maximization models for the unconstrained scheduling problem with known cash flows, optimal and suboptimal scheduling procedures with various types of resource constraints, and the problem of determining both the timing and amount of payments.     

不确定环境下基于时间、费用及鲁棒性权衡的多目标项目调度优化

项目调度中的时间和费用是两个重要的指标,而在不确定环境下进度计划的鲁棒性则是保证项目平稳实施的关键。本文研究不确定环境下的多目标项目调度优化问题,以优化项目的工期、鲁棒值和成本为目标安排各活动的开始时间。基于此,作者构建多目标项目调度优化模型,将模型分解为三个子模型分析目标间的权衡关系,然后设计非劣排序遗传算法进行求解,应用精英保留策略和基于子模型权衡关系的优化策略优化算法,进行算法测试和算例参数敏感性分析。最后,应用上述方法研究一个项目实例,计算得到非劣解集,实例的敏感性分析结果进一步验证了三个目标间的权衡关系,据此提出资源的有效利用策略。本文的研究可以为多目标项目调度制定进度计划提供定量化决策支持。     

On distributed scheduling with heterogeneously delayed network-state information

We study the problem of distributed scheduling in wireless networks, where each node makes individual scheduling decisions based on heterogeneously delayed network state information (NSI). This leads to inconsistency in the views of the network across nodes, which, coupled with interference, makes it challenging to schedule for high throughputs. We characterize the network throughput region for this setup, and develop optimal scheduling policies to achieve the same. Our scheduling policies have a threshold-based structure and, moreover, require the nodes to use only the “smallest critical subset” of the available delayed NSI to make decisions. In addition, using Markov chain mixing techniques, we quantify the impact of delayed NSI on the throughput region. This not only highlights the value of extra NSI for scheduling, but also characterizes the loss in throughput incurred by lower complexity scheduling policies which use homogeneously delayed NSI.     

PROGRESS: Optimally solving the generalized resource-constrained project scheduling problem

This paper deals with the generalized resource-constrained project scheduling problem (GRCPSP) which extends the well-known resource-constrained project scheduling problem (RCPSP) by considering job specific release and due dates, non-negative minimum start-to-start time lags as well as time-varying resource availabilities. The structure of the project is represented by an acyclic network diagram. Though the extensions are of high practical importance, only a few exact solution procedures have been presented in the literature so far. Therefore, a new exact procedure PROGRESS is developed which includes new dominance rules as well as enhancements of existing ones. For evaluating the efficiency experimentally, new GRCPSP instances with 30 and 60 jobs are considered which extend the standard benchmark sets for the RCPSP generated by ProGen. PROGRESS shows superior performance when applied to the GRCPSP and is also very competitive in comparison to approaches proposed for the RCPSP.     

An efficient representation of Benes networks and its applications

The most popular bounded-degree derivative network of the hypercube is the butterfly network. The Benes network consists of back-to-back butterflies. There exist a number of topological representations that are used to describe butterfly—like architectures. We identify a new topological representation of butterfly and Benes networks.The minimum metric dimension problem is to find a minimum set of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex w with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. It is NP-hard in the general sense. We show that it remains NP-hard for bipartite graphs. The algorithmic complexity status of this NP-hard problem is not known for butterfly and Benes networks, which are subclasses of bipartite graphs. By using the proposed new representations, we solve the minimum metric dimension problem for butterfly and Benes networks. The minimum metric dimension problem is important in areas such as robot navigation in space applications.