We consider novel project scheduling problems in which the experience gained from completing selected activities can be used to accelerate subsequent activities. Given a set of potential learning opportunities, our model aims to identify the opportunities that result in a maximum reduction of the project makespan when scheduled in sequence. Accounting for the impact of such learning opportunities causes significant complications, due to the cyclic nature of the learning relations and their interference with the precedence network. We propose additive and subtractive algorithms that iteratively reschedule the project using an enhanced topological sorting algorithm. Learning opportunities are integrated, activated, and potentially deactivated in each step by maintaining the acyclicity of the combined precedence and learning network. To illustrate the challenges that arise in this setting, we first consider the special case where activities can learn from at most one other activity. Subsequently, we extend our approach to the general case that admits multiple learning opportunities. We show that our approaches guarantee the construction of an optimal solution in polynomial time. In a computational study using 340 small and large resource-unconstrained PSPlib instances, we analyze the model behavior under various scenarios of learning intensity and learning opportunity. We demonstrate that significant project speedups can be obtained when proactively accounting for learning opportunities. History: Accepted by Pascal van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0107 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0107 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Dynamic stochastic matching problems arise in a variety of recent applications, ranging from ridesharing and online video games to kidney exchange. Such problems are naturally formulated as Markov decision processes (MDPs) that are, however, intractable in general. To improve tractability, we investigate the linear programming-based approach to approximate dynamic programming. This approach can provide both feasible control policies and bounds on the MDPs’ optimal policy value, which can be used to establish optimality gaps. However, the approximate linear programs (ALPs) resulting from this approach can often be difficult to solve. To address this computational challenge, we derive novel ALP reformulations that can be used for a broad class of dynamic stochastic matching problems that incorporate, among others, possible match failures and certain restrictions on feasible matchings. We show that these ALP reformulations can be solved efficiently and applied to a broad class of dynamic matching problems. In addition, our numerical results indicate that our ALP reformulations can produce tight bounds that allow us to establish near-optimal policy performance for a broad set of problem instances. Thus, ALP reformulations can present an attractive alternative for applications that involve dynamic stochastic matching. History: Accepted by Nicola Secomandi, Area Editor for Stochastic Models & Reinforcement Learning. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0203 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0203 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract In this article we analyze certain matching problems that arise in ground delay program planning. Ground delay programs are air traffic flow management initiatives put in place when airport arrival demand is expected to exceed arrival capacity for an extended length of time, e.g. 4 h. Most of the problems we study can be modeled as assignment problems, where flights are assigned to arrival slots. In the context we analyze, however, these problems have important special structure, which allows us to develop special solution properties. In particular, solutions are measured both in terms of efficiency (delay minimization) and equity (delay distribution). We show that the theory of majorization provides a powerful tool in addressing solution equity. We consider problems with flight deletions and develop special solution properties and parametric methods. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

We represent planning as a set of loosely coupled network flow problems, where each network corresponds to one of the state variables in the planning domain. The network nodes correspond to the state variable values and the network arcs correspond to the value transitions. The planning problem is to find a path (a sequence of actions) in each network such that, when merged, they constitute a feasible plan. In this paper we present a number of integer programming formulations that model these loosely coupled networks with varying degrees of flexibility. Since merging may introduce exponentially many ordering constraints we implement a so-called branch-and-cut algorithm, in which these constraints are dynamically generated and added to the formulation when needed. Our results are very promising, they improve upon previous planning as integer programming approaches and lay the foundation for integer programming approaches for cost optimal planning.