We study the preemptive scheduling problem of a set of n jobs with release times and equal processing times on a single machine. The objective is to minimize the sum of the weighted completion times (∑{sub}i=1){sup}n w{sub}iC{sub}i of the jobs. We propose for this problem the first parameterized algorithm on the number k of different weights. The runtime of the proposed algorithm is O((n/k+1){sup}kn{sup}8) and hence, this is the first polynomial algorithm for any fixed number k of different weights.
展开▼
机译：我们研究了一组N个作业的抢购调度问题，在单个机器上具有释放时间和平等的处理时间。目标是最小化加权完成时间（Σ{sub} i = 1）{sup} n w {sub} i的作业的总和。我们为此问题提出了不同权重的第一个参数化算法。所提出的算法的运行时间是O（（n / k + 1）{sup} kn {sup} 8），因此，这是用于不同权重的任何固定数k的第一多项式算法。
展开▼
