We consider a significant problem that arises in the planning of many projects. Project companies often use outsourced providers that require capacity reservations that must be contracted before task durations are realized. We model these decisions for a company that, given partially characterized distributional information, assumes the worst-case distribution for task durations. Once task durations are realized, the project company makes decisions about fast tracking and outsourced crashing, to minimize the total capacity reservation, fast tracking, crashing, and makespan penalty costs. We model the company’s objective using the target-based measure of minimizing an underperformance riskiness index. We allow for correlation in task performance, and for piecewise linear costs of crashing and makespan penalties. An optimal solution of the discrete, nonlinear model is possible for small to medium size projects. We compare the performance of our model against the best available benchmarks from the robust optimization literature, and show that it provides lower risk and greater robustness to distributional information. Our work thus enables more effective risk minimization in projects, and provides insights about how to make more robust capacity reservation decisions. Summary of Contribution: This work studies a financially significant planning problem that arises in project management. Companies that face uncertainties in project execution may need to reserve capacity with outsourced providers. Given that decision, they further need to plan their operational decisions to protect against a bad outcome. We model and solve this problem via adjustable distributionally robust optimization. While this problem involves two-stage decision making, which is computationally challenging in general, we develop a computationally efficient algorithm to find the exact optimal solution for instances of practical size.

Aset of original jobs has been scheduled on a single machine, but not processed, when a set of new jobs arrives. The decision maker needs to insert the new jobs into the existing schedule without excessively changing it. The objective is minimization of the maximum lateness of the jobs, subject to a customer service requirement modeled by a limit on the maximum time change of the original jobs. Because the schedule of the original jobs can be arbitrary, this problem models multiple disruptions from repeated new job arrivals. We show that this scheduling problem is intractable, even if no new jobs arrive. We describe several approximation algorithms and analyze their worst-case performance. Next, we develop a branch and bound algorithm that uses a variable neighborhood descent algorithm to obtain an initial upper bound, several dominance properties that we establish, and a lower bounding scheme based on a preemptive relaxation of the problem. The branch and bound algorithm solves 99.9% of randomly generated instances with up to 1,000 jobs within 60 CPU seconds. Our work demonstrates for the first time that optimization of large scale, intractable rescheduling problems is possible. More generally, it refocuses the literature on scheduling problems towards rescheduling issues.

Broadcasting in a communications network has been the subject of many studies in recent years. The studies vary in their assumptions governing the behavior of the network and in their objectives with respect to the network. Almost all the work to date uses the unit transmission time assumption, that is, the message transmission times between all pairs of vertices are equal. In this paper, we investigated the broadcast problem under four more general transmission time assumptions. In addition, four different objective functions were considered, including the minimization of (1) the broadcast time (the maximum time for any vertex to receive the message), (2) the average time to receive the message (both with and without ready times at the vertices), (3) the weighted average time to receive the message, and (4) the cycle time. Of the 20 problems thus generated, four admit polynomial time algorithms, 15 are (in the equivalent recognition version) unary NP-complete, and the complexity status of one remains open. All these results are proved, and heuristics with an attainable constant worst-case performance ratio are provided for two of the problems for which polynomial time algorithms are not found. © 1998 John Wiley & Sons, Inc. Networks 32:233–253, 1998

Under a variety of different random models of the maximal covering location problem, we show that the relative error of a randomly generated solution converges to zero in expectation as problem size grows. We prove similar results for the relative error between the optimal integer and fractional solutions to the problem. Suppose that randomly generated instances of this problem are used to test heuristics. One consequence of our results is that we should expect the mean relative error of a heuristic to be better than that of randomly generated solutions, if the heuristic is to be considered useful.