The payment scheduling problem

Large complicated projects with interdependent activities can be described by project networks. Arcs represent activities, nodes represent events, and the network's structure defines the relation between activities and events. A schedule associates an occurrence time with each event: the project can be scheduled in several different ways. We assume that a known amount of cash changes hands at each event. Given any schedule the present value of all cash transactions can be calculated. The payment scheduling problem looks for a schedule that maximizes the present value of all transactions. This problem was first introduced by Russell [2]; it is a nonlinear program with linear constraints and a nonconcave objective. This paper demonstrates that the payment scheduling problem can be transformed into an equivalent linear program. The linear program has the structure of a weighted distribution problem and an efficient procedure is presented for its solution. The algorithm requires the solution of triangular systems of equations with all matrix coefficients equal to ± or 0.     

Maximizing project cash availability

Consider a project during the life cycle of which there are cash payouts and in‐flows. To better meet his financial commitments, the project owner would like to meet all deadlines without running out of cash. We show that the cash availability objective is similar to the total weighted flowtime used to measure work‐in‐progress performance in the scheduling and inventory control literatures. In this article we provide several specialized solution methods for the problem of minimizing total weighted flowtime in an arbitrary acyclic project network, subject to activity release times and due dates, where the activity weights may be positive or negative and represent cash in‐ and out‐flows. We describe the structure of an optimal solution and provide several efficient algorithms and their complexity based on mincost and maxflow formulations. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

A genetic algorithm with neighborhood search for the resource‐constrained project scheduling problem

The resource‐constrained project scheduling problem (RCPSP) consists of a set of non‐preemptive activities that follow precedence relationship and consume resources. Under the limited amount of the resources, the objective of RCPSP is to find a schedule of the activities to minimize the project makespan. This article presents a new genetic algorithm (GA) by incorporating a local search strategy in GA operators. The local search strategy improves the efficiency of searching the solution space while keeping the randomness of the GA approach. Extensive numerical experiments show that the proposed GA with neighborhood search works well regarding solution quality and computational time compared with existing algorithms in the RCPSP literature, especially for the instances with a large number of activities. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Scheduling recurrent construction

A problem we call recurrent construction involves manufacturing large, complex, expensive products such as airplanes, houses, and ships. Customers order configurations of these products well in advance of due dates for delivery. Early delivery may not be permitted. How should the manufacturer determine when to purchase and release materials before fabrication, assembly, and delivery? Major material expenses, significant penalties for deliveries beyond due dates, and long product makespans in recurrent construction motivate choosing a release timetable that maximizes the net present value of cash flows. Our heuristic first projects an initial schedule that dispatches worker teams to tasks for the backlogged products, and then solves a series of maximal closure problems to find material release times that maximize NPV. This method compares favorably with other well‐known work release heuristics in solution quality for large problems over a wide range of operating conditions, including order strength, cost structure, utilization level, batch policy, and uncertainty level. Computation times exhibit near linear growth in problem size. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Partial equilibrium in risk‐based production decisions

Characteristically, a small subset of operational problems admit risk neutrality when contingent claims methodology were used in their analysis. That is, for the majority of manufacturing and production problems, operating cash flows are not directly linked to prices of traded assets. However, to the extent that correlations can be estimated, the methodology's applicability to a broader set of operational problems is supported. Our article addresses this issue with the objective of extending the use of contingent claims techniques to a larger set of operational problems. In broad terms, this objective entails a partial equilibrium approach to the problem of valuing uncertain cash flows. To this end, we assume risk aversion and cast our approach within Merton's intertemporal capital asset pricing model. In this context, we formulate a “generic” production valuation model that is framed as an exercise in stochastic optimal control. The model is versatile in its characterization and can easily be adapted to accommodate a wide‐ranging set of risk‐based operational problems where the underlying sources of uncertainty are not traded. To obtain results, the model is recast as a stochastic dynamic program to be solved numerically. The article addresses a number of fundamental issues in the analysis risk based decision problems in operations. First, in the approach provided, decisions are analyzed under a properly defined risk structure. Second, the process of analysis leads to suitably adjusted probability distributions through which, appropriately discounted expectations are derived. Third, through consolidating existing concepts into a standard and adaptable framework, we extend the applicability of contingent claims methodology to a broader set of operational problems. The approach is advantageous as it obviates the need for exogenously specifying utility functions or discount rates.© 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Client‐contractor bargaining on net present value in project scheduling with limited resources

The client‐contractor bargaining problem addressed here is in the context of a multi‐mode resource constrained project scheduling problem with discounted cash flows, which is formulated as a progress payments model. In this model, the contractor receives payments from the client at predetermined regular time intervals. The last payment is paid at the first predetermined payment point right after project completion. The second payment model considered in this paper is the one with payments at activity completions. The project is represented on an Activity‐on‐Node (AON) project network. Activity durations are assumed to be deterministic. The project duration is bounded from above by a deadline imposed by the client, which constitutes a hard constraint. The bargaining objective is to maximize the bargaining objective function comprised of the objectives of both the client and the contractor. The bargaining objective function is expected to reflect the two‐party nature of the problem environment and seeks a compromise between the client and the contractor. The bargaining power concept is introduced into the problem by the bargaining power weights used in the bargaining objective function. Simulated annealing algorithm and genetic algorithm approaches are proposed as solution procedures. The proposed solution methods are tested with respect to solution quality and solution times. Sensitivity analyses are conducted among different parameters used in the model, namely the profit margin, the discount rate, and the bargaining power weights. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Non‐greedy heuristics and augmented neural networks for the open‐shop scheduling problem

In this paper we propose some non‐greedy heuristics and develop an Augmented‐Neural‐Network (AugNN) formulation for solving the classical open‐shop scheduling problem (OSSP). AugNN is a neural network based meta‐heuristic approach that allows integration of domain‐specific knowledge. The OSSP is framed as a neural network with multiple layers of jobs and machines. Input, output and activation functions are designed to enforce the problem constraints and embed known heuristics to generate a good feasible solution fast. Suitable learning strategies are applied to obtain better neighborhood solutions iteratively. The new heuristics and the AugNN formulation are tested on several benchmark problem instances in the literature and on some new problem instances generated in this study. The results are very competitive with other meta‐heuristic approaches, both in terms of solution quality and computational times. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Rank‐Cluster‐and‐Prune: An algorithm for generating clusters in complex set partitioning problems

Clustering problems are often difficult to solve due to nonlinear cost functions and complicating constraints. Set partitioning formulations can help overcome these challenges, but at the cost of a very large number of variables. Therefore, techniques such as delayed column generation must be used to solve these large integer programs. The underlying pricing problem can suffer from the same challenges (non‐linear cost, complicating constraints) as the original problem, however, making a mathematical programming approach intractable. Motivated by a real‐world problem in printed circuit board (PCB) manufacturing, we develop a search‐based algorithm (Rank‐Cluster‐and‐Prune) as an alternative, present computational results for the PCB problem to demonstrate the tractability of our approach, and identify a broader class of clustering problems for which this approach can be used. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

A self‐adapting genetic algorithm for project scheduling under resource constraints

This papers deals with the classical resource‐constrained project scheduling problem (RCPSP). There, the activities of a project have to be scheduled subject to precedence and resource constraints. The objective is to minimize the makespan of the project. We propose a new heuristic called self‐adapting genetic algorithm to solve the RCPSP. The heuristic employs the well‐known activity list representation and considers two different decoding procedures. An additional gene in the representation determines which of the two decoding procedures is actually used to compute a schedule for an individual. This allows the genetic algorithm to adapt itself to the problem instance actually solved. That is, the genetic algorithm learns which of the alternative decoding procedures is the more successful one for this instance. In other words, not only the solution for the problem, but also the algorithm itself is subject to genetic optimization. Computational experiments show that the mechanism of self‐adaptation is capable to exploit the benefits of both decoding procedures. Moreover, the tests show that the proposed heuristic is among the best ones currently available for the RCPSP. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 433–448, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10029     

论读写能力和整体发展的关系研究

儿童教育一直是国际上热烈探讨的话题。目前，中国的小学教育中存在着严重的应试教育倾向。本研究基于Huitt教授创立的启明星模式理论，讨论了教师通过应用提前开发好的教学概要，不仅能达到启明星模式中的整体目标，还可以使阅读活动与其它学业目标相联。     

Sensitivity curves for effective project management

A key problem in project management is to decide which activities are the most important to manage and how best to manage them. A considerable amount of literature has been devoted to assigning “importance” measures to activities to help with this important task. When activity times are modeled as random variables, these activity importance measures are more complex and difficult to use. A key problem with all existing measures is that they summarize the importance in a single number. The result is that it is difficult for managers to determine a range of times for an activity that might be acceptable or unacceptable. In this paper, we develop sensitivity curves that display the most useful measures of project performance (in terms of schedule) as a function of an activity's time. The structure of the networks allows us to efficiently estimate these curves for all desired activities, all desired time ranges, and all desired measures in a single set of simulation runs. The resulting curves provide insights that are not available when considering summarized measures alone. Chief among these insights is the ability to identify an acceptable range of times for an activity that will not lead to negative scheduling consequences. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 481–497, 2003     

Timely exposure of a secret project: Which activities to monitor?

A defender wants to detect as quickly as possible whether some attacker is secretly conducting a project that could harm the defender. Security services, for example, need to expose a terrorist plot in time to prevent it. The attacker, in turn, schedules his activities so as to remain undiscovered as long as possible. One pressing question for the defender is: which of the project's activities to focus intelligence efforts on? We model the situation as a zero‐sum game, establish that a late‐start schedule defines a dominant attacker strategy, and describe a dynamic program that yields a Nash equilibrium for the zero‐sum game. Through an innovative use of cooperative game theory, we measure the harm reduction thanks to each activity's intelligence effort, obtain insight into what makes intelligence effort more effective, and show how to identify opportunities for further harm reduction. We use a detailed example of a nuclear weapons development project to demonstrate how a careful trade‐off between time and ease of detection can reduce the harm significantly.     

Reformulating linear programs with transportation constraints—With applications to workforce scheduling

We study linear programming models that contain transportation constraints in their formulation. Typically, these models have a multistage nature and the transportation constraints together with the associated flow variables are used to achieve consistency between consecutive stages. We describe how to reformulate these models by projecting out the flow variables. The reformulation can be more desirable since it has fewer variables and can be solved faster. We apply these ideas to reformulate two well‐known workforce staffing and scheduling problems: the shift scheduling problem and the tour scheduling problem. We also present computational results. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Optimal multicommodity network flows with resource allocation

The problem of determining multicommodity flows over a capacitated network subject to resource constraints may be solved by linear programming; however, the number of potential vectors in most applications is such that the standard arc-chain formulation becomes impractical. This paper describes an approach—an extension of the column generation technique used in the multicommodity network flow problem—that simultaneously considers network chain selection and resource allocation, thus making the problem both manageable and optimal. The flow attained is constrained by resource availability and network capacity. A minimum-cost formulation is described and an extension to permit the substitution of resources is developed. Computational experience with the model is discussed.     

Project scheduling under competition

We introduce and investigate the problem of scheduling activities of a project by a firm that competes with another firm (the competitor) that has to perform the same project. The profit that the firm gets from each activity depends on whether the firm finishes the activity before or after its competitor. The objective is to maximize the guaranteed (worst‐case) profit. We assume that both the firm and the competitor can perform only one activity at a time. We perform a detailed complexity analysis of the problem, and consider problems with and without precedence constraints, with and without delay of the competitor, with general and equal processing times of activities. For polynomially solvable cases (which include, for example, all the considered problems without delay of the competitor), we present easily implementable and intuitive rules that allow us to obtain optimal schedules in linear or almost linear time. For some NP‐hard cases, we present pseudopolynomial algorithms and fast heuristics with worst‐case approximation guarantees. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Efficient distributions of arms‐control inspection effort

A rule that constrains decision‐makers is enforced by an inspector who is supplied with a fixed level of inspection resources—inspection personnel, equipment, or time. How should the inspector distribute its inspection resources over several independent inspectees? What minimum level of resources is required to deter all violations? Optimal enforcement problems occur in many contexts; the motivating application for this study is the role of the International Atomic Energy Agency in support of the Treaty on the Non‐Proliferation of Nuclear Weapons. Using game‐theoretic models, the resource level adequate for deterrence is characterized in a two‐inspectee problem with inspections that are imperfect in the sense that violations can be missed. Detection functions, or probabilities of detecting a violation, are assumed to be increasing in inspection resources, permitting optimal allocations over inspectees to be described both in general and in special cases. When detection functions are convex, inspection effort should be concentrated on one inspectee chosen at random, but when they are concave it should be spread deterministicly over the inspectees. Our analysis provides guidance for the design of arms‐control verification operations, and implies that a priori constraints on the distribution of inspection effort can result in significant inefficiencies. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

A novel modeling approach for express package carrier planning

Express package carrier networks have large numbers of heavily‐interconnected and tightly‐constrained resources, making the planning process difficult. A decision made in one area of the network can impact virtually any other area as well. Mathematical programming therefore seems like a logical approach to solving such problems, taking into account all of these interactions. The tight time windows and nonlinear cost functions of these systems, however, often make traditional approaches such as multicommodity flow formulations intractable. This is due to both the large number of constraints and the weakness of the linear programming (LP) relaxations arising in these formulations. To overcome these obstacles, we propose a model in which variables represent combinations of loads and their corresponding routings, rather than assigning individual loads to individual arcs in the network. In doing so, we incorporate much of the problem complexity implicitly within the variable definition, rather than explicitly within the constraints. This approach enables us to linearize the cost structure, strengthen the LP relaxation of the formulation, and drastically reduce the number of constraints. In addition, it greatly facilitates the inclusion of other stages of the (typically decomposed) planning process. We show how the use of templates, in place of traditional delayed column generation, allows us to identify promising candidate variables, ensuring high‐quality solutions in reasonable run times while also enabling the inclusion of additional operational considerations that would be difficult if not impossible to capture in a traditional approach. Computational results are presented using data from a major international package carrier. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Optimizing natural gas pipeline transmission with nonuniform elevation: A new initialization approach

In this paper, we develop an iterative piecewise linear approximation approach with a novel initialization method to solve natural gas pipeline transmission problems with the nonuniform network elevation. Previous approaches, such as energy minimization methods, cannot be applied to solve problems with the nonuniform network elevation because they exclude pressure range constraints, and thus provide solutions far from optimum. We propose a new initialization model that considers pressure range constraints and improves the optimality of the solutions and the computational efficiency. Furthermore, we extend the energy minimization methods and provide the necessary conditions under which the extended methods operate in networks with the nonuniform elevation. We test the performances of the methods with previously reported pipeline networks from the literature, with the open data set GasLib, and with our industrial collaborator. The initialization approach is shown to be more efficient than the method with fixed initial breakpoints. The newly proposed initialization approach generates solutions with a higher accuracy than the extended energy minimization methods, especially in large‐size networks. The proposed method has been applied to natural gas transmission planning by the China National Petroleum Corporation and has brought a direct profit increase of 330 million U.S. dollars in 2015‐2017.     

Balancing stability and efficiency in team formation as a generalized roommate problem

The assignment of personnel to teams is a fundamental managerial function typically involving several objectives and a variety of idiosyncratic practical constraints. Despite the prevalence of this task in practice, the process is seldom approached as an optimization problem over the reported preferences of all agents. This is due in part to the underlying computational complexity that occurs when intra-team interpersonal interactions are taken into consideration, and also due to game-theoretic considerations, when those taking part in the process are self-interested agents. Variants of this fundamental decision problem arise in a number of settings, including, for example, human resources and project management, military platooning, ride sharing, data clustering, and in assigning students to group projects. In this article, we study an analytical approach to “team formation” focused on the interplay between two of the most common objectives considered in the related literature: economic efficiency (i.e., the maximization of social welfare) and game-theoretic stability (e.g., finding a core solution when one exists). With a weighted objective across these two goals, the problem is modeled as a bi-level binary optimization problem, and transformed into a single-level, exponentially sized binary integer program. We then devise a branch-cut-and-price algorithm and demonstrate its efficacy through an extensive set of simulations, with favorable comparisons to other algorithms from the literature.     

Measuring defense conversion in Russian industry

This paper develops and implements a methodology for quantifying defense conversion in Russian manufacturing in the early 1990s. A two‐sector, three‐good model is employed to analyze the flows of resources from military to non‐military uses and applied to firm‐level survey data under alternative definitions of military production and the MIC. An aggregation framework is constructed to estimate the total quantity and change in Russian military production, the latter decomposed into intrafirm and intersectoral resource reallocation and overall industrial decline. Although there is evidence of substantial decline in military production, the data show little reallocation to productive civilian uses, neither within the MIC nor to other manufacturing sectors.