Как найти эффективную последовательность для моего N номера последовательности в Javascript

Question

Я просто пытаюсь найти правильную последовательность в последовательности N. Число, о котором я говорю, Предположим, что у нас есть 5 машин и 20 заданий на этих машинах У нас будет вероятность 20! то есть 2,432,902,008,176,640,000 возможной последовательности, чтобы сделать это правильно. Какая лучше последовательность, основанная на времени завершения. Мы должны ее найти. К сожалению, я немного смущен, что, как получить правильную и эффективную последовательность времени. Me застрял после получения возможности 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

Я думаю, что единственный способ, чтобы получить идеальное решение, чтобы проверить все возможности. Если вы заботитесь о производительности, это должно, но это должно дать вам правильное решение в большинстве случаев в то же время достаточно быстро ...

Главная область действия:

1. Сортировать задания по timeToFinish, самый длинный в самой короткой
2. Добавить первую работу в кратчайшую нить
3. Сортировать темы по суммарному времени выполнения, кратчайшие к длинному
4. Перейти к 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. Я бы попросил knapsack.js. Исходный код находится на 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));