Scheduling algorithms for time-dependent V-shaped processing times with agreeable slopes around a common ideal time

Abstract

Abstract 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.