Computing latest starting times of activities in interval-valued networks with minimal time lags

This paper deals with problems of determining possible values of earliest and latest starting times of an activity in networks with minimal time lags and imprecise durations that are represented by means of interval or fuzzy numbers. Although minimal time lags are practical in different projects, former researchers have not considered these problems.After proposing propositions which reduce the search space, a novel polynomial algorithm is presented to compute intervals of possible values of latest starting times in interval-valued networks with minimal time lags. Then, the results are extended to networks with fuzzy durations.     

On the hardness of evaluating criticality of activities in a planar network with duration intervals

Complexity results for problems of evaluating the criticality of activities in planar networks with duration time intervals are presented. We show that the problems of asserting whether an activity is possibly critical, and of computing bounds on the float of an activity in these networks are NP-complete and NP-hard, respectively.     

Analysis of critical paths in a project network with fuzzy activity times

This paper proposes an approach to critical path analysis for a project network with activity times being fuzzy numbers, in that the membership function of the fuzzy total duration time is constructed. The basic idea is based on the extension principle and linear programming formulation. A pair of linear programs parameterized by possibility level α is formulated to calculate the lower and upper bounds of the fuzzy total duration time at α. By enumerating different values of α, the membership function of the fuzzy total duration time is constructed, and the fuzzy critical paths are identified at the same time. Moreover, by applying the Yager ranking method, definitions of the most critical path and the relative degree of criticality of paths are developed; and these definitions are theoretically sound and easy to use in practice. Two examples with activity times being fuzzy numbers of L-R and L-L types discussed in previous studies are solved successfully to demonstrate the validity of the proposed approach. Since the total duration time is completely expressed by a membership function rather than by a crisp value, the fuzziness of activity times is conserved completely, and more information is provided for critical path analysis.     

A heuristic method for RCPSP with fuzzy activity times

In this paper, we propose a heuristic method for resource constrained project scheduling problem with fuzzy activity times. This method is based on priority rule for parallel schedule generation scheme. Calculation of critical path in this case requires comparison of fuzzy numbers. Distance based ranking of fuzzy number is used for finding the critical path length and concept of shifting criticality is proposed for some of the special cases. We also propose a measure for finding the non-integer power of a fuzzy number. We discuss some properties of the proposed method. We use an example to illustrate the method.     

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.     

Modeling activity times by the Parkinson distribution with a lognormal core: Theory and validation

Based on theoretical arguments and empirical evidence we advocate the use of the lognormal distribution as a model for activity times. However, raw data on activity times are often subject to rounding and to the Parkinson effect. We address those factors in our statistical tests by using a generalized version of the Parkinson distribution with random censoring of earliness, ultimately validating our model with field data from several sources. We also confirm that project activities exhibit stochastic dependence that can be modeled by linear association.     

The computational complexity of the criticality problems in a network with interval activity times

The paper analyzes the criticality in a network with interval activities duration times. A natural generalization of the criticality notion (for a path, an activity and an event) for the case of network with interval activity duration times is given. The computation complexity of five problems linked to the introduced criticality notion is presented.     

Predictive–reactive scheduling on a single resource with uncertain future jobs

We consider a scheduling problem where the firm must compete with other firms to win future jobs. Uncertainty arises as a result of incomplete information about whether the firm will win future jobs at the time the firm must create a predictive (planned) schedule. In the predictive schedule, the firm must determine the amount of planned idle time for uncertain jobs and their positions in the schedule. When the planned idle time does not match the actual requirements, certain schedule disruptions occur. The firm seeks to minimize the sum of expected tardiness cost, schedule disruption cost, and wasted idle time cost. For the special case of a single uncertain job, we provide a simple algorithm for the optimal planned idle time and the best reactive method for schedule disruptions. For the case of multiple uncertain jobs, a heuristic dynamic programming approach is presented.     

An evaluation of the adequacy of project network generators with systematically sampled networks

This paper evaluates and compares different network generators to generate project scheduling problem instances based on indicators measuring the topological network structure. We review six topological network indicators in order to describe the detailed structure of a project network. These indicators were originally developed by [L.V. Tavares, J.A. Ferreira and J.S. Coelho, The risk of delay of a project in terms of the morphology of its network, European Journal of Operational Research 119 (1999), 510–537] and have been modified, or sometimes completely replaced, by alternative indicators to describe the network topology. The contribution of this paper is twofold. Firstly, we generate a large amount of different networks with four project network generators. Our general conclusions are that none of the network generators are able to capture the complete feasible domain of all networks. Additionally, each network generator covers its own network-specific domain and, consequently, contributes to the generation of data sets. Secondly, we perform computational results on the well-known resource-constrained project scheduling problem to prove that our indicators are reliable and have significant, predictive power to serve as complexity indicators.     

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.     

Minimizing the total completion time in a unit-time open shop with release times

We consider the problem of minimizing the total completion time in a unit-time open shop with release times where the number of machines is constant. Brucker and Krämer (1994) proved that this problem is solvable in polynomial time. However, the time complexity of the algorithm presented there is a polynom of a very high degree and, thus, the algorithm is not practicable even for a small number of machines. We give an O(n²) algorithm for the considered problem which is based on dynamic programming. The result is applied to solve a previously open problem with a special resource constraint raised by De Werra et al. (1991).     

广义活动网络ETI支付进度计划问题的研究

优化ETI支付进度安排是消除承包商和业主由于进度安排原因而产生经济纠纷,实现双赢的最有效方法.本文分析了活动间广义时序关系的类型,建立了广义时序关系下活动间的约束关系;在考虑承包商和业主双方联合收益要求的基础上,提出了双方的净现值按同比例减小的折衷原则,构建了广义活动网络在ETI支付方式下的支付进度计划模型;最后通过一个算例进行了分析,验证表明该优化模型具有较好的有效性和实用性.     

A branch and bound method for the job-shop problem with sequence-dependent setup times

This paper deals with the job-shop scheduling problem with sequence-dependent setup times. We propose a new method to solve the makespan minimization problem to optimality. The method is based on iterative solving via branch and bound decisional versions of the problem. At each node of the branch and bound tree, constraint propagation algorithms adapted to setup times are performed for domain filtering and feasibility check. Relaxations based on the traveling salesman problem with time windows are also solved to perform additional pruning. The traveling salesman problem is formulated as an elementary shortest path problem with resource constraints and solved through dynamic programming. This method allows to close previously unsolved benchmark instances of the literature and also provides new lower and upper bounds.     

Scheduling in a multi-class series of queues with deterministic service times

We consider a problem of scheduling in a multi-class network of single-server queues in series, in which service times at the nodes are constant and equal. Such a model has potential application to automated manufacturing systems or packet-switched communication networks, where a message is divided into packets (or cells) of fixed lengths. The network is a series-type assembly or transfer line, with the exception that there is an additional class of jobs that requires processing only at the first node (class 0). There is a holding cost per unit time that is proportional to the total number of customers in the system. The objective is to minimize the (expected) total discounted holding cost over a finite or an infinite horizon. We show that an optimal policy gives priority to class-0 jobs at node 1 when at least one of a set ofm–1 inequalities on partial sums of the components of the state vector is satisfied. We solve the problem by two methods. The first involves formulating the problem as a (discrete-time) Markov decision process and using induction on the horizon length. The second is a sample-path approach using an interchange argument to establish optimality.The research of this author was supported by the National Science Foundation under Grant No. DDM-8719825. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.     

On the resolution and optimization of a system of fuzzy relational equations with sup-T composition

This paper provides a thorough investigation on the resolution of a finite system of fuzzy relational equations with sup-T composition, where T is a continuous triangular norm. When such a system is consistent, although we know that the solution set can be characterized by a maximum solution and finitely many minimal solutions, it is still a challenging task to find all minimal solutions in an efficient manner. Using the representation theorem of continuous triangular norms, we show that the systems of sup-T equations can be divided into two categories depending on the involved triangular norm. When the triangular norm is Archimedean, the minimal solutions correspond one-to-one to the irredundant coverings of a set covering problem. When it is non-Archimedean, they only correspond to a subset of constrained irredundant coverings of a set covering problem. We then show that the problem of minimizing a linear objective function subject to a system of sup-T equations can be reduced into a 0–1 integer programming problem in polynomial time. This work generalizes most, if not all, known results and provides a unified framework to deal with the problem of resolution and optimization of a system of sup-T equations. Further generalizations and related issues are also included for discussion.     

On the generation of circuits and minimal forbidden sets

We present several complexity results related to generation and counting of all circuits of an independence system. Our motivation to study these problems is their relevance in the solution of resource constrained scheduling problems, where an independence system arises as the subsets of jobs that may be scheduled simultaneously. We are interested in the circuits of this system, the so-called minimal forbidden sets, which are minimal subsets of jobs that must not be scheduled simultaneously. As a consequence of the complexity results for general independence systems, we obtain several complexity results in the context of resource constrained scheduling. On that account, we propose and analyze a simple backtracking algorithm that generates all minimal forbidden sets for such problems. The performance of this algorithm, in comparison to a previously suggested divide-and-conquer approach, is evaluated empirically using instances from the project scheduling library PSPLIB.Acknowledgement We appreciate the input of two anonymous referees. Particularly the deep remarks of one of them greatly improved our understanding of several issues; he also suggested the simplified Example 1. We thank Marc Pfetsch and Alexander Grigoriev for several enlightening discussions. Marc Pfetsch also pointed us to the paper [15]. Parts of this work were done while the authors were PhD students at the Technische Universität Berlin, Germany, where Frederik Stork was supported by DFG grant Mo 446/3-3, and Marc Uetz was supported by bmb+f grant 03-MO7TU1-3 and GIF grant I 246-304.02/97.     

On the efficiency of multiplier methods for nonlinear network problems with nonlinear constraints

The minimization of network flow problems with linear/nonlinearside constraints can be performed by minimizing an augmentedLagrangian function, including only the side constraints. Thismethod gives rise to an algorithm that combines first- and superlinear-orderestimators of the multipliers of the side constraints. The codePFNRN03 is the implementation of this algorithm in Fortran 77.The main aim of this work is to compare the efficiency of thiscode on two sets of (industrial, artificial) test problems withthat of the general-purpose solvers MINOS, SNOPT, LANCELOT andLOQO. Numerical results of these four codes are obtained bythe NEOS server with AMPL input. The comparison indicates thatPFNRN03 may be effective on current large-scale network flowproblems with nonlinear side constraints.     

A branch and bound algorithm for scheduling trains in a railway network

The paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits.     

全空间上一类带Hardy项的半线性椭圆方程

本文讨论如下一类半线性椭圆方程非平凡解的存在性.-Δu-μu/(|x|2)+u=|u|2*-2u+k(x)f(u),x∈RN,u∈H1(R~N),其中N≥3,0<μ<[(N-2)/2]2,2*=2N/(N-2),k(x)∈C(RN,R),函数f(u)关于自变量u在无穷远处渐近线性或者超线性.