We consider a single-item multilevel lot-sizing problem with a serial structure where one of the levels has an inventory capacity (the bottleneck level). We propose a novel dynamic programming algorithm combining Zangwill’s approach for the uncapacitated problem and the basis-path approach for the production capacitated problem. Under reasonable assumptions on the cost parameters the time complexity of the algorithm is [Formula: see text] with L the number of levels in the supply chain and T the length of the planning horizon. Computational tests show that our algorithm is significantly faster than the commercial solver Cplex applied to a standard formulation and can solve reasonably sized instances up to 48 periods and 12 levels in a few minutes. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the National Research Foundation of Korea (NRF) funded by the Ministry of Education [Grant 2014R1A1A2058513].

To eliminate and eradicate gambiense human African trypanosomiasis (HAT), maximizing the effectiveness of active case finding is of key importance. The progression of the epidemic is largely influenced by the planning of these operations. This paper introduces and analyzes five models for predicting HAT prevalence in a given village based on past observed prevalence levels and past screening activities in that village. Based on the quality of prevalence level predictions in 143 villages in Kwamouth (DRC), and based on the theoretical foundation underlying the models, we consider variants of the Logistic Model-a model inspired by the SIS epidemic model-to be most suitable for predicting HAT prevalence levels. Furthermore, we demonstrate the applicability of this model to predict the effects of planning policies for screening operations. Our analysis yields an analytical expression for the screening frequency required to reach eradication (zero prevalence) and a simple approach for determining the frequency required to reach elimination within a given time frame (one case per 10000). Furthermore, the model predictions suggest that annual screening is only expected to lead to eradication if at least half of the cases are detected during the screening rounds. This paper extends knowledge on control strategies for HAT and serves as a basis for further modeling and optimization studies.

In this paper we consider the two-machine flow shop problem with varying machine speeds. We present an algorithm which determines the optimal permutations for all machine speeds in O(n log n) time, where n is the number of jobs. To achieve this bound on the running time, the algorithm employs an elementary dominance relation.

A class of strong valid inequalities is described for the single-item uncapacitated economic lot-sizing problem with start-up costs. It is shown that these inequalities yield a complete polyhedral characterization of the problem. The corresponding separation problem is formulated as a shortest path problem. Finally, a reformulation as a plant location problem is shown to imply the class of strong valid inequalities, which shows that this reformulation is tight, also.