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/ .

Abstract University students benefit academically, personally and professionally from an expansion of their in‐class social network. To facilitate this, we present a novel and broadly‐applicable optimization approach that exposes individuals to as many as possible peers that they do not know. This novel class of “social seating assignment problems” is parameterized by the social network, the physical seating structure and “tie potentials” representing the likelihood for two neighbors to connect. The resulting problem is NP‐hard and belongs to assignment problems with an elaborate objective that depends on the relation of both seats and individuals assigned to them. We develop compact integer programming formulations and strengthen them with valid inequalities to improve performance. In parallel, we suggest fast heuristics that are guided by network centrality measures. Finally, we present the necessary modeling techniques to integrate practically relevant instructor preferences and special student needs. Combining the above, we experiment on a set of 320 realistic instances with up to 200 students forming both sparse and dense social networks and for both rectangular and circular classrooms. For sparse or small instances we present optimality gaps under 1.3% within a few minutes, whereas in larger or denser cases the algorithmic performance decreases. We also evaluate our approach from both a quantitative and a qualitative perspective on three actual classes with more than 70 students. A network‐analysis‐based comparison of a priori and a posteriori networks shows that 40% of opportunities led to new connections, while feedback from both instructor and student is particularly favorable for our method.

Effective computational methods are important for practitioners and researchers working in strategic underground mine planning. We consider a class of problems that can be modeled as a resource-constrained project scheduling problem with optional activities; the objective maximizes net present value. We provide a computational review of math programming and constraint programming techniques for this problem, describe and implement novel problem-size reductions, and introduce an aggregated linear program that guides a list scheduling algorithm running over unaggregated instances. Practical, large-scale planning problems cannot be processed using standard optimization approaches. However, our strategies allow us to solve them to within about 5% of optimality in several hours, even for the most difficult instances. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms—Discrete. Funding: This work was supported by Alford Mining Systems, the Centro de Modelamiento Matemático [Grants ACE210010 and FB21005], ANID-Chile [BASAL funds for center of excellence and FONDEF Grant ID19-10164], and the supercomputing infrastructure of the NLHPC [Grant ECM-02].

In the multi‐depot ring star problem (MDRSP), a set of customers has to be connected to a set of given depots by ring stars. Such a ring star is a cycle graph, also called a ring, with some additional nodes assigned to its nodes by single star edges. Optional Steiner nodes can be used in the network as intermediate nodes on the rings. Depot dependent capacity limits apply to both, the number of customers in each ring star and the number of ring stars connected to a depot. The MDRSP asks for a network such that the sum of the edge costs is minimized. In this article, we present a matheuristic that iteratively refines a solution network in a locally exact fashion. In contrast to existing approaches, we define an equi‐model matheuristic. That is a refinement method in which the subproblems are modeled as smaller instances of the global problem. Hence the optimization model that is used to explore the various structural multi‐exchange neighborhoods in our algorithm is the MDRSP itself. A first class of neighborhoods considers local subnetworks for optimal improvements. Through an advanced modeling technique, we are able to refine arbitrary subnetworks of suitable size induced by simple node sets. A second class aims at globally restructuring the current network after the application of different contraction techniques. For both purposes, we develop an exact branch & cut algorithm for the MDRSP that efficiently solves the local optimization problems to optimality, if they are chosen reasonably in terms of size and complexity. The efficiency of the approach is shown by computational results improving known upper bounds for instance classes from the literature containing up to 1000 nodes. Ninety‐one percent of the known best objective values are improved up to 13% in competitive computational time. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 67(3), 222–237 2016