2-approximation algorithm for minmax absolute maximum lateness scheduling-location problem

The problem of minmax absolute scheduling-location is investigated on trees with interval edge length. Jobs are located at vertices and must travel to the machine. The goal is to find a machine location and simultaneously a schedule to minimize the maximum lateness in the worst-case. We derive a result that could reduce the robust versions to deterministic problems. An efficient algorithm is developed to solve special cases. A 2-approximation algorithm is proposed for the robust problem on the underlying tree.