GitList
Raw Blame History 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
  86
 
import {
  addIndex, findIndex, find, map, propEq, reduce, sort, range, concat,
  filter, reverse, prop, flatten, uniq, reject, contains, omit
} from 'rambda';
import type { JobId } from '../../types';
import { max, remove, slice } from 'ramda';
 
type JobTime = {
  jobId: JobId,
  t: number,
  d: number,
  c: number,
  w: number,
  anc: JobId[],
};
 
const findMaxTJob = (jobTimes: JobTime[]) =>
  reduce(
    (maxTJob: JobTime, jobTime: JobTime) => maxTJob.t >= jobTime.t ? maxTJob : jobTime,
    { t: -Infinity },
    jobTimes
  );
 
const findMinJob = (fi: number, jobTimes: JobTime[]) =>
  reduce(
    (minJob: JobTime, jobTime: JobTime) => {
      const minJobU = minJob.w * max(fi - minJob.d, 0);
      const jobTimeU = jobTime.w * max(fi - jobTime.d, 0);
 
      return minJobU < jobTimeU ? minJob : jobTime;
    },
    { w: Infinity },
    jobTimes
  );
 
const updateCTime = (jobTimes: JobTime[]) => {
  let prev = 0;
 
  const cj = map((jobTime: JobTime) => {
    prev += jobTime.t;
 
    return { ...jobTime, c: prev };
  }, jobTimes);
 
  return cj;
};
 
export const createSchedule = (jobs: JobTime[]) => {
  let fi = reduce((sum, job: JobTime) => sum + job.t, 0, jobs);
  let jobsD = jobs;
  let R = [];
 
  while (fi > 0) {
    const allAcc = uniq(flatten(
      map(prop('anc'), jobsD)
    ));
 
    const G = reject((jobTime: JobTime) => contains(jobTime.jobId, allAcc), jobsD);
 
    if (!G.length) return null;
 
    const minJob = findMinJob(fi, G);
    const minJobIndex = findIndex(propEq('jobId', minJob.jobId), jobsD);
 
    jobsD = remove(minJobIndex, 1, jobsD);
    fi -= minJob.t;
 
    R.push(minJob);
  }
 
  const withC = updateCTime(reverse(R));
 
  return map(omit(['w', 'anc']), withC);
};
 
export default (jobs: JobTime[]) => {
  const schedule = createSchedule(jobs);
 
  const normalizedSchedule = map((jobTime: JobTime) => ({
    processor: 1,
    startTime: jobTime.c - jobTime.t,
    endTime: jobTime.c,
  }), schedule);
 
  return [normalizedSchedule];
};