如何在 Javascript 中为我的 N 个序列找到有效序列

Question

我只是想在 N 个数中找到正确的序列 sequence.What 我说的是假设我们有 5 台机器和 20 个工作要做 machines.We 的概率是 20 ！那就是 2,432,902,008,176,640,000 种可能的序列来做对。什么是最好的序列基于 completion.we 的时间必须找到它。不幸的是，我对如何获得正确和最佳时间效率的顺序有点困惑。我在产生 sequence.And 的可能性后卡住了，我不知道如何获得正确的序列

我的尝试

var howManyMachines = 2;
var Sequenxe = [
    {
        jobId:1,
        timeToFinish:5
    },
    {
        jobId:2,
        timeToFinish:4
    },
    {
        jobId:3,
        timeToFinish:4
    }


];
var machines = Array(howManyMachines).fill().map((m, i) => {
    var Mindex = i;
    if(i == 0){
        Mindex = 1
    }else{
        Mindex = i+1
    }
    return {
        id: i,
        value: 0,
        jobs: [],
        name:"M"+Mindex

    } });
function permutations(items) {
    if (items.length == 1) return [items];
    var combos = [];
    for (var i = 0; i < items.length; i++) {
        var first = items[i], rest = items.slice(0);
        rest.splice(i, 1);
        permutations(rest).forEach(function(combo){
            combo.unshift(first);
            combos.push(combo);
        });
    }
    return combos;
}



const allSequence = permutations(Sequenxe);


console.log(allSequence.length+" Sequence to test")
console.log(machines.length+" Machines Available");



allSequence.forEach(singleSequence => {
    console.log("===>",singleSequence)
   //I don't Know what to do

});

Answer 1

我认为获得完美解决方案的唯一方法是检查所有可能性。如果您关心性能，这应该可以，但在大多数情况下这应该能为您提供正确的解决方案，同时速度相当快...

主要步骤区域：

按完成时间排序，最长到最短
将第一份工作添加到最短线程
按总执行时间对线程进行排序，从最短到最长
转到 2 并重复直到没有更多工作可用

var machines = 2;
var jobs = [{
  jobId: 1,
  timeToFinish: 5
}, {
  jobId: 2,
  timeToFinish: 4
}, {
  jobId: 3,
  timeToFinish: 4
}];

jobs.sort((a, b) => b.timeToFinish - a.timeToFinish);

var threads = new Array(2).fill({
  jobs: [],
  totalTime: 0
});

while (jobs.length > 0) {
  threads = threads.map(t => {
    j = jobs.shift();
    return j ? {
      jobs: t.jobs.concat(j),
      totalTime: t.totalTime + j.timeToFinish
    } : t;
  });
  threads.sort((a, b) => a.totalTime - b.totalTime);
}

console.log(JSON.stringify(threads, null, 2))

Answer 2

最佳根据完成时间 听起来像 deadline scheduling.

提前规划这些大型工作听起来像 knapsack problem. I'd give knapsack.js a try. Source code is on GitHub。

Answer 3

您可以按照以下方式进行；它会生成20个随机时间的作业，然后将它们平均分配到5台机器上。

function groupTasks(jobs,machineCount){
  var  sum = jobs.reduce((p,c) => p + c.time, 0),
   initial = [...Array(machineCount)].map(sa => (sa = [], sa.sum = 0, sa));
   console.log("total number of jobs:",jobs.length,"\n");
   console.log("total job time:", sum,"\n");
   console.log("number of machines:", machineCount,"\n");
   console.log("target total job time per machine:", sum/machineCount,"\n");
  return jobs.sort((a,b) => b.time-a.time)
             .reduce((machines,job) => { var machine = machines.reduce((p,c) => p.sum < c.sum ? p : c);
                                         machine.push(job);
                                         machine.sum += job.time;
                                         return machines;
                                       },initial);
}

var jobs = [...Array(20)].map((_,i) => ({id:i, time:~~(Math.random()*10)+1})),
  result = groupTasks(jobs,5);
console.log("jobs: \n", JSON.stringify(jobs));
console.log("jobs per machine:","\n",JSON.stringify(result));

如何在 Javascript 中为我的 N 个序列找到有效序列

How to find the efficient sequence for my N number of sequence in Javascript

javascript

node.js

genetic-algorithm