Abstract Scheduling jobs with given processing times on identical parallel machines so as to minimize their total completion time is one of the most basic scheduling problems. We study this classical problem under uncertainty, in which the uncertainty is modeled by a set of scenarios. In our model, a scenario is defined as a subset of a predefined and fully specified set of jobs. The aim is to find an assignment of the whole set of jobs to identical parallel machines such that the schedule, obtained for the given scenarios by simply skipping the jobs not in the scenario, optimizes a function of the total completion times over all scenarios. While the underlying scheduling problem without scenarios can be solved efficiently by a simple greedy procedure (SPT rule), scenarios, in general, make the problem NP-hard. We paint an almost complete picture of the evolving complexity landscape, drawing the line between easy and hard. One of our main algorithmic contributions relies on a deep structural result on the maximum imbalance of an optimal schedule, based on a subtle connection to Hilbert bases of a related convex cone.

Abstract We introduce and study a class of optimization problems we call replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Clients with capacity for storing a certain commodity are located at various places; at each client the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Clients should never run empty. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a client becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each client and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min – avg minimizes the average tour cost and min – max minimizes the maximum tour cost over all days. For min – max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min – avg we present a logarithmic factor approximation on general metrics, a 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.

Abstract In the inventory routing problem (IRP) inventory management and route optimization are combined. The traveling salesman problem (TSP) is a special case of the IRP, hence the IRP is NP‐hard. We investigate how other aspects than routing influence the complexity of a variant of the IRP. We first study problem variants on a point and on the half‐line. The problems differ in the number of vehicles, the number of days in the planning horizon and the service times of the customers. Our main result is a polynomial time dynamic programming algorithm for the variant on the half‐line with uniform service times and a planning horizon of 2 days. Second, for nearly any problem in the class with nonfixed planning horizon, we show that the complexity is dictated by the complexity of the pinwheel scheduling problem, for which the complexity is a long‐standing open research question. Third, NP‐hardness is shown for problem variants with nonuniform servicing times. Finally, we prove strong NP‐hardness of a Euclidean variant with uniform service times and an easily computable routing cost approximation, avoiding immediate NP‐hardness via the TSP.

The field of a priori optimization is an interesting subfield of stochastic combinatorial optimization that is well suited for routing problems. In this setting, there is a probability distribution over active sets, vertices that have to be visited. For a fixed tour, the solution on an active set is obtained by restricting the solution on the active set. In the well-studied a priori traveling salesman problem, the goal is to find a tour that minimizes the expected length. In the a priori traveling repairman problem (TRP), the goal is to find a tour that minimizes the expected sum of latencies. In this paper, we study the uniform model, where a vertex is in the active set with probability p independently of the other vertices, and give the first constant-factor approximation for a priori TRP.