带约定时间的多维任务负载平衡问题

Multidimensional Task Load Balancing Problem with a Common Due Date

摘要: 本文研究了两台平行机上带约定时间的多维任务负载平衡问题，该问题是传统负载平衡问题的推广，目标是最大化机器的提前工作量。带有约定时间的多维任务负载平衡问题涉及到在多个维度上平衡任务的分配，同时满足任务的约定时间。这种问题在许多实际应用中都很常见，比如生产调度、交通规划、资源分配等领域。对于该问题，当任务的维数为 时，本文设计了一个在线算法，算法的竞争比为(√5-1)l，然后设计了一个动态规划算法以得到问题的最优解，最后在动态规划的基础上采用舍入取整技术设计了一个FPTAS。

Abstract: In this paper, we study multidimensional task loading problem on two parallel machines with a common due date. This problem is a generalization of the traditional load balancing problem, with the goal of maximizing the advance workload of machines. The multi-dimensional task load balanc-ing problem with a common due date involves balancing the distribution of tasks in multiple di-mensions while satisfying the due date time of tasks. This kind of problem is common in many prac-tical applications, such as production scheduling, transportation planning, resource allocation. For this problem, when the dimension of the task is l, we first designs an online algorithm with a com-petitive ratio of (√5-1)l , and the dynamic programming algorithm is designed to obtain the op-timal solution of the problem. Finally, on the basis of dynamic programming, the FPTAS is designed by rounding technique.