MARKOV SKELETON PROCESS IN PERT NETWORKS

In this article, we investigate Programming Evaluation and Review Technique networks with independently and generally distributed activity durations. For any path in this network, we select all the activities related to this path such that the completion time of the sub-network （only consisting of all the related activities） is equal to the completion time of this path. We use the elapsed time as the supplementary variables and model this sub-network as a Markov skeleton process, the state space is related to the subnetwork structure. Then use the backward equation to compute the distribution of the sub-network＇s completion time, which is an important rule in project management and scheduling.     

A branch and cut algorithm for the hierarchical network design problem

The Hierarchical Network Design Problem consists of locating a minimum cost bi-level network on a graph. The higher level sub-network is a path visiting two or more nodes. The lower level sub-network is a forest connecting the remaining nodes to the path. We optimally solve the problem using an ad hoc branch and cut procedure. Relaxed versions of a base model are solved using an optimization package and, if binary variables have fractional values or if some of the relaxed constraints are violated in the solution, cutting planes are added. Once no more cuts can be added, branch and bound is used. The method for finding valid cutting planes is presented. Finally, we use different available test instances to compare the procedure with the best known published optimal procedure, with good results. In none of the instances we needed to apply branch and bound, but only the cutting planes.     

A rule for slack allocation proportional to the duration in a PERT network

In this paper, we define a new rule for the resolution of the slack allocation problem in a PERT network. This problem exists of allocating existing extra time in some paths among the activities belonging to those paths. The allocation rule that we propose assigns extra time to the activities proportionally to their durations in such a way that no path duration exceeds the completion time of the whole project. This time allocation enables us to make a schedule for the PERT project under study. We give two characterizations of the rule and we compare it with others that have been previously defined in the literature.     

On path correlation and PERT bias

Most studies of project time estimation assume that (a) activity times are mutually independent random variables; many also assume that (b) path completion times are mutually independent. In this paper, we subject the impact of both these assumptions to close scrutiny. Using tools from multivariate analysis, we make a theoretical study of the direction of the error in the classical PERT method of estimating mean project completion time when correlation is ignored. We also investigate the effect of activity dependence on the normality of path length via simulation.     

Finding the critical path in an activity network with time-switch constraints

An activity network is an acyclic graph with non-negative weights and with a unique source and destination. A project consisting of a set of activities and precedence relationships can be represented by an activity network and the mathematical analysis of the network provides useful information for managing the project. In a traditional activity network, it is assumed that an activity always begins after all of its preceding activities have been completed. This assumption may not be adequate enough to describe some practical applications where some forms of time constraints are attached to an activity. In this paper, we investigate one type of time constraint called time-switch constraint which assumes that an activity begins only in a specified time interval of a cycle with some pairs of exclusive components. Polynomial time algorithms are developed to find the critical path (or longest path) and analyze the float of each arc in this time-constrained activity network. The analysis shows that the critical path and float in this context differ from those of a traditional activity network in some management perspectives and thus, consideration of the time-switch constraint leads to enhanced project management through more effective use of budgets and resource allocation.     

The Most Critical Path in a PERT Network

The classical PERT approach uses the path with the largest expected duration as the critical path to estimate the probability of completing a project by a given deadline. However, in general, such a path is not the ‘most critical’ path and does not provide the smallest estimate for the probability of completion time. This paper studies the ‘most critical path’ problem and formulates it as an optimal path problem in a deterministic network with a two-attribute fractional objective function. An exact solution approach is presented for the optimal path problem which also gives the solution to the most critical path problem. The illustrative examples as well as our computational results demonstrate that the proposed algorithm provides estimates for the probabilities of completion time that are much more accurate than those of the classical approach.     

The completable digraphs for the totally nonnegative completion problem

In this paper, we study the totally nonnegative completion problem when the partial totally nonnegative matrix is non-combinatorially symmetric. In general, this type of partial matrix does not have a totally nonnegative completion. Here, we give necessary and sufficient conditions for completion of a partial totally nonnegative matrix to a totally nonnegative matrix in the cases where the digraph of the off-diagonal specified entries takes certain forms as path, cycles, alternate paths, block graphs, etc., distinguishing between the monotonically and non-monotonically labeled case.     

A new probabilistic approach to the path criticality in stochastic PERT

The notion of critical path is a key issue in the temporal analysis of project scheduling in deterministic setting. The very essence of the CPM consists in identifying the critical path, i.e., the longest path in a project network, because this path conveys information on how long it should take to complete the project to the project manager. The problem how can a stochastic counterpart of the deterministic critical path be defined is an important question in stochastic PERT. However, in the literature of stochastic PERT this question has so far almost been ignored, and the research into the random nature of a project duration has mainly been concentrated on the completion time in stochastic PERT in which any concrete special path is not specified. In the present paper we attempt to take first steps to fill this gap. We first developed a probabilistic background theory for univariate and bivariate marginal distributions of path durations of stochastic PERT whose joint path durations are modelled by multivariate normal distribution. Then, a new probabilistic approach to the comparison of path durations is introduced, and based on this comparison we define the concept of probabilistically critical path as a stochastic counterpart of the deterministic critical path. Also, an illustrative simple example of PCP and numerical results on the established probability bounds are presented.     

Parallel machines scheduling with a deteriorating maintenance activity

In this paper, we consider parallel identical machines scheduling problems with a deteriorating maintenance activity. In this model, each machine has a deteriorating maintenance activity, that is, delaying the maintenance increases the time required to perform it. We need to make a decision on when to schedule the deteriorating maintenance activities and the sequence of jobs to minimize total completion time. We provide a polynomial time algorithm to solve the total completion time minimization problem.     

Architectures,stability and optimization for clock distribution networks

Synchronous telecommunication networks, distributed control systems and integrated circuits have its accuracy of operation dependent on the existence of a reliable time basis signal extracted from the line data stream and acquirable to each node. In this sense, the existence of a sub-network (inside the main network) dedicated to the distribution of the clock signals is crucially important. There are different solutions for the architecture of the time distribution sub-network and choosing one of them depends on cost, precision, reliability and operational security. In this work we expose: (i) the possible time distribution networks and their usual topologies and arrangements. (ii) How parameters of the network nodes can affect the reachability and stability of the synchronous state of a network. (iii) Optimizations methods for synchronous networks which can provide low cost architectures with operational precision, reliability and security.     

A linear Bayesian stochastic approximation to update project duration estimates

By relaxing the unrealistic assumption of probabilistic independence on activity durations in a project, this paper develops a hierarchical linear Bayesian estimation model. Statistical dependence is established between activity duration and the amount of resource, as well as between the amount of resource and the risk factor. Upon observation or assessment of the amount of resource required for an activity in near completion, the posterior expectation and variance of the risk factor can be directly obtained in the Bayesian scheme. Then, the expected amount of resources required for and the expected duration of upcoming activities can be predicted. We simulate an application project in which the proposed model tracks the varying critical path activities on a real time basis, and updates the expected project duration throughout the entire project. In the analysis, the proposed model improves the prediction accuracy by 38.36% compared to the basic PERT approach.     

有关单机两代理排序问题的两个结果

研究了两个单机两代理排序问题. 在第一个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化最大工件费用. 在第二个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化所有工件的最大完工时间. 证明了第一个问题是强NP-难的, 改进了已有的一般意义NP-难的结果; 对第二个问题给出了一个与现有的动态规划算法不同的动态规划算法.     

Obstructions for acyclic local tournament orientation completions

The orientation completion problem for a fixed class of oriented graphs asks whether a given partially oriented graph can be completed to an oriented graph in the class. Orientation completion problems have been studied recently for several classes of oriented graphs, including local tournaments. Local tournaments are intimately related to proper circular-arc graphs and proper interval graphs. In particular, proper interval graphs are precisely those which can be oriented as acyclic local tournaments. In this paper we determine all obstructions for acyclic local tournament orientation completions. These are in a sense minimal partially oriented graphs that cannot be completed to acyclic local tournaments. Our results imply that a polynomial time certifying algorithm exists for the acyclic local tournament orientation completion problem.     

A Multivariate Approach to Estimating the Completion Time for PERT Networks

Stochastic PERT is typically treated as a critical path problem, with the critical path having a univariate probability distribution. A method has been developed to treat the PERT problem as a multivariate problem taking into consideration correlation among paths, thereby providing a more accurate analysis of the network and its corresponding probabilities for completion time.     

The unbounded parallel-batch scheduling with rejection

In this paper, we consider the unbounded parallel-batch scheduling with rejection. A job is either rejected, in which case a certain penalty has to be paid, or accepted and processed in batches on a machine. The processing time of a batch is defined as the longest processing time of the jobs contained in it. Four problems are considered: (1) to minimize the sum of the total completion time of the accepted jobs and the total rejection penalty of the rejected jobs; (2) to minimize the total completion time of the accepted jobs subject to an upper bound on the total rejection penalty of the rejected jobs; (3) to minimize the total rejection penalty of the rejected jobs subject to an upper bound on the total completion time of the accepted jobs; (4) to find the set of all the Pareto optimal schedules. We provide a polynomial-time algorithm for the first problem. Furthermore, we show that all the other three problems are binary NP-hard and present a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for them.     

Unrelated parallel-machine scheduling with deterioration effects and deteriorating multi-maintenance activities for minimizing the total completion time

This paper investigates scheduling problems with simultaneous considerations of deterioration effects and deteriorating multi-maintenance activities on unrelated parallel machines. We examine two models of scheduling with the deterioration effect, namely the job-dependent and position-dependent deterioration model and the time-dependent deterioration model. We assume that each machine may be subject to several maintenance activities over the scheduling horizon, and the duration of maintenance on a machine depends on its running time. Moreover, due to the restriction of the budget of maintenance, the upper bound of the total maintenance frequencies on all the machines is assumed to be known in advance. The objective is to find jointly the optimal maintenance frequencies, the optimal maintenance positions, and the optimal job sequences such that the total completion time is minimized. If the number of machines is fixed, we introduce polynomial time solutions for all the versions of the problem under study.     

Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deteriorating maintenance consideration

In this paper we introduce a new model of joint start-time dependent learning and position dependent aging effects into single-machine scheduling problems. The machine may need maintenance to improve its production efficiency. The objectives are to find jointly the optimal maintenance position and the optimal sequence such that the makespan, the total completion time, and the total absolute deviation of completion times (TADC) are minimized. We also aim to determine jointly the optimal maintenance position, the optimal due-window size and location, and the optimal sequence to minimize the sum of earliness, tardiness and due-window related costs function. We show that all the studied problems can be optimally solved by polynomial time algorithms.     

Solving project scheduling problems with a heuristic learning algorithm

We have developed an approach to implement a real time admissible heuristic search algorithm to solve project scheduling problems. This algorithm is characterised by the complete heuristic learning process: state selection, heuristic learning, and search path review. This implementation approach is based on the dynamic nature of the activity status and the resource availability of a project. It consists of states, state transition operator, heuristic estimate, and the cost of transition between states. The performance analysis shows that the accumulation of heuristic learning during the search process has led to the re-scheduling of resource dominating activities, which is a major factor in controlling the overall project completion time.     

A dependent project evaluation and review technique: A Bayesian network approach

The Program Evaluation and Review Technique (PERT) dates back to 1959. This method evaluates the uncertainty distribution of a project’s completion time given the uncertain completion times of the activities/tasks comprised within it. Each activity’s uncertainty was defined originally by a unique two parameter beta PERT distribution satisfying what is known to be the PERT mean and PERT variance. In this paper, a three-parameter PERT family of bounded distributions is introduced satisfying that same mean and variance, generalizing the beta PERT distribution. Their additional flexibility allows for the modeling of statistical dependence in a continuous Bayesian network, generalizing in turn the traditional PERT procedure where statistical independence is assumed among beta PERT activity durations. Through currently available Bayesian network software and the construction of that PERT family herein, the coherent monitoring of remaining project completion time uncertainty given partial completion of a project may become more accessible to PERT analysts. An illustrative example demonstrating the benefit of monitoring of remaining project completion time uncertainty as activities complete in that Bayesian fashion shall be presented, including expressions and algorithms for the specification of the three prior parameters for each activity in the project network to adhere to classical the PERT mean and PERT variance and a degree of statistical dependence between them.     

极小化最大完工时间的单机分批加工问题

本文考虑极小化最大完工时间的单机分批加工问题．设有n个工件和一台批加工机器．每个工件有一个释放时间和一个加工时间．批加工机器可以同时加工b(b相似文献