Interval Scheduling with Economies of Scale

Motivated by applications in cloud computing, we study interval scheduling problems exhibiting economies of scale. An instance is given by a set of jobs, each with start time, end time, and a function representing the cost of scheduling a subset of jobs on the same machine. Specifically, we focus on the max-weight function and non-negative, … Read more

A Parallel Hub-and-Spoke System for Large-Scale Scenario-Based Optimization Under Uncertainty

Efficient solution of stochastic programming problems generally requires the use of parallel computing resources. Here, we describe the open source package mpi-sppy, in which efficient and scalable parallelization is a central feature. We describe the overall architecture and provide computational examples and results showing scalability to the largest instances that we know of for the … Read more

Dynamic Node Packing

We propose a dynamic version of the classical node packing problem, also called the stable set or independent set problem. The problem is defined by a node set, a node weight vector, and an edge probability vector. For every pair of nodes, an edge is present or not according to an independent Bernoulli random variable … Read more