Exact and Approximate High-Multiplicity Scheduling on Identical Machines
摘要
Goemans and Rothvoss (SODA’14) gave a framework for solving problems which can be described as finding a point in \(\text {int.cone}(P\cap \mathbb {Z}^N)\cap Q\) , where \(P,Q\subset \mathbb {R}^N\) are (bounded) polyhedra. The running time for solving such a problem is \(\langle P\rangle ^{2^{O(N)}}\langle Q\rangle ^{O(1)}\) . This framework can be used to solve various scheduling problems, but the encoding length \(\langle P\rangle \) usually involves parameters like the makespan or deadlines (which can be very large compared to the processing times). We describe three tools to improve the framework by Goemans and Rothvoss: For example, applied to the scheduling problems \({P||\{C_{\max },C_{\min },C_{envy }\}}\) , these tools improve the running time from \((\log (C_{\max }))^{2^{O(d)}}\langle I\rangle ^{O(1)}\) to the possibly much better \((\log (p_{\max }))^{2^{O(d)}}\langle I\rangle ^{O(1)}\) . Here, \(p_{\max }\) is the largest processing time, d is the number of different processing times, \(C_{\max }\) is the makespan and \(\langle I\rangle \) is the encoding length of the instance. On the complexity side, we use reductions from the literature to provide new parameterized lower bounds for \({P||C_{\max }}\) . Finally, we show that the big open question asked by Mnich and van Bevern (Comput. Oper. Res. ’18) whether \({P||C_{\max }}\) is FPT w.r.t. the number of job types d has the same answer as the question whether \({Q||C_{\max }}\) is FPT w.r.t. the number of job and machine types \(d+\tau \) (all in high-multiplicity encoding). The same holds for objective \(C_{\min }\) .