fe944750 |
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];
}; |