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 }\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Exact and Approximate High-Multiplicity Scheduling on Identical Machines

  • Klaus Jansen,
  • Kai Kahler,
  • Esther Zwanger

摘要

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 }\) .