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

Question

I am just trying find the right sequence in N number sequence.What I am talking about is Suppose we have 5 Machines and 20 jobs have to do in that machines.We will have the probability of 20! that is 2,432,902,008,176,640,000 possible sequence to do it right .What is best Sequence based on the time of completion.we have to find it. Unfortunately I am little bit confused that how to get the right and best time efficient sequence. Me stuck after producing the possibilities of sequence.And I don't Know how to get the right sequence

My try

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

I think the only way to get a perfect solution is to check all the possibilities. If you care about performance, this should but this should give you a correct solution in most cases while being reasonably quick ...

Main steps area:

1. Sort jobs by timeToFinish, longest to shortest
2. Add first job to the shortest thread
3. Sort threads by total time of execution, shortest to longest
4. Go to 2 and repeat until no more jobs available

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

You might do as follows; It will generate 20 jobs with random time for each and then will evenly distribute them into 5 machines.

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));

Answer 3

Best according to time of completion sounds like deadline scheduling.

Planning of these large jobs in advance sounds like the knapsack problem. I'd give knapsack.js a try. Source code is on GitHub.