Nir Halman

We study a single-machine problem with time-dependent processing times following a V-shape around a common ideal time. The slopes are under an agreeableness condition and can be asymmetric and job-specific. Its application lies in production with a moving assembly line, to minimize a worker’s walking time retrieving parts from a supply point, in which part weight affects walking velocity. In this problem, the global start time (or ideal time) can be fixed or variable. For both variants, we devise the first function-based monotonic dynamic programs, which let us derive fully polynomial time approximation schemes employing a recent framework for K -approximation sets and functions. For the variable variant with asymmetric, job-uniform slopes, we introduce a polynomial time algorithm.

We consider a certain proportionate flow shop scheduling problem with step-deteriorating processing times and study two objective functions: makespan and sum of completion times. We reformulate these problems as monotone dynamic programs that fall into both FPTAS frameworks of Alon and Halman. Consequently, we get for each one of them an FPTAS and a strongly polynomial FPTAS, where the latter one improves upon the running time of the fastest FPTAS known to date.

We design a framework to obtain Fully Polynomial Time Approximation Schemes (FPTASes) for adjustable robust multistage decision making under the budgeted uncertainty sets introduced by Bertsimas and Sim. We apply this framework to the robust counterpart of three problems coming from operations research: (i) ordered knapsack, (ii) single-item inventory control, and (iii) single-item batch dispatch. Our work gives the first FPTAS for these problems, and for adjustable robust multistage decision making in general. The proposed approximation schemes are constructed with the technique of K-approximation sets and functions, relying on careful robust dynamic programming formulations for a master problem (corresponding to the decision maker) and for an adversary problem (corresponding to nature, which chooses bad realizations of uncertainty for the decision maker). The resulting algorithms are short and simple, requiring just a few concise subroutines. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research was supported in part by the United States-Israel Binational Science foundation [Grant 2018095). N. Halman was also supported in part by the Israel Science Foundation [Grants 399/17 and 1074/21].

We consider three new knapsack problems with variable weights or profits of items, where the weight or profit of an item depends on the position of the item in the sequence of items packed in the knapsack. We show how to solve the problems exactly using dynamic programming algorithms with pseudo-polynomial running times and propose fully polynomial-time approximation schemes for their approximate solution.