如何在n台机器上编写排序n个作业的算法

Question

我只是想写一个算法。对n台机器上的n个作业进行排序。例:-

 job1->2s;
 job2->1s;
 job3->5s;

首先，我们必须按时间对作业进行排序(desc)

 job3->5s;
 job1->1s;
 job2->2s;

假设我们有两台机器

machine1->job3
machine2->job2

作业2将首先完成写入，下一步应该是

machine1->job3 => 5s
machine2->job2+job1(2s+1s) => 3s

我希望这台机器能工作也就是5秒，它是最长的机器，对吧，我要那个答案。如何为这个写算法…到目前为止，我所做的是按时间顺序对对象进行排序。然后我不知道如何改进这个算法，使其适用于n个机器和n个作业。

thanks in advance

run.js

 var sorty = require('sorty');
    var njobs = [
        {
            jobname:"j1",
            time:42
        },
        {
            jobname:"j2",
            time:56
        },
        {
            jobname:"j3",
            time:78
        },
        {
            jobname:"j4",
            time:68
        },
        {
            jobname:"j5",
            time:43
        },
        {
            jobname:"j6",
            time:99
        },
        {
            jobname:"j7",
            time:88
        }
    ];
    var machines = 4;
    //sort desc with time
    var order = sorty([
        {name:'time',dir: 'desc',type:'number'}
    ],njobs);
    for(i=0;i<order.length;i++){
            console.log('job Name :'+order[i].jobname+' job Time to finish :'+order[i].time+' alloting machines to job');

    }

Answer 1

这里给出的答案的javascript实现示例(由用户BeyelerStudios在评论中链接)

• 按时间排序，从最高的
开始
• 创建机器列表
• 对于每台机器，存储所有作业的总作业时间
• 循环遍历作业，将作业分配给总作业时间最低的机器

正如链接的答案所述:这绝不能保证你得到完美的、最好的解决方案。此外，如果我们谈论的是成千上万的工作和机器，你会想要优化性能……如果您正在处理问题中提供的数据集，那么下面的示例实现可能适合您。

var njobs = [{
  jobname: "j1",
  time: 42
}, {
  jobname: "j2",
  time: 56
}, {
  jobname: "j3",
  time: 78
}, {
  jobname: "j4",
  time: 68
}, {
  jobname: "j5",
  time: 43
}, {
  jobname: "j6",
  time: 99
}, {
  jobname: "j7",
  time: 88
}];
var sorted = njobs.sort((a, b) => b.time - a.time);
var machines = Array(4).fill().map((m, i) => { return { id: i, value: 0, jobs: [] } });
sorted.forEach(job => {
  var minMachine = machines
    .slice(1)
    .reduce((res, cur) => res.value < cur.value ? res : cur, machines[0]);
  
  minMachine.jobs.push(job);
  minMachine.value += job.time;
});
console.log(machines.map(m => "Machine " + m.id + 
                         ", time: " + m.value + 
                         ", jobs: " + m.jobs.map(j => j.jobname).join(", ")));

(注意:对于旧浏览器的支持，您可能需要填充Array#fill)

Answer 2

@user3297291很好的实现，但是您的技术只考虑(n)个作业数，而没有考虑(m)个机器数。

这是另一个实现，它能够计算任意数量的工作(n)或机器(m)，其中(n&m> 1)。它验证给定的数据集，不仅应用约翰逊规则，而且还使用CDS算法来深入挖掘和计算更复杂的替代方案，可能的最大完成时间更少。稍后，您可以将整个时间轴导出为excel或pdf格式以供进一步使用。

该工具是完全免费使用https://job-sequencing.appspot.com尽情尝试吧!