Minimizing maximum lateness of jobs in inventory constrained scheduling

This paper focuses on a machine scheduling problem having applications in truck scheduling at transshipment terminals. Jobs increase and decrease, respectively, the level of a central inventory. Naturally, jobs decreasing the inventory level can be processed only if the level of the inventory is high enough not to drop below zero. We consider the problem to find a schedule for jobs such that the maximum lateness among all jobs is minimized. We develop properties of optimal solutions, lower bounds, and heuristic methods in order to find upper bounds. These are incorporated in four branch and bound algorithms that are based on fixing sequences of jobs in forward or backward direction in two different types of representations. By means of a computational study, we compare these approaches with each other in order to show their efficiency.