Zamanlama ve Zincir Optimizasyonu (Scheduling & Chain Optimization) Algoritması

1export interface Job {
2  id: string;
3  deadline: number;
4  profit: number;
5}
6
7export function jobSequencing(jobs: Job[]): { sequence: string[]; totalProfit: number } {
8  // Sort by profit descending
9  const sorted = [...jobs].sort((a, b) => b.profit - a.profit);
10  const maxDeadline = Math.max(...jobs.map(j => j.deadline));
11  
12  const slots = new Array(maxDeadline).fill(null);
13  let totalProfit = 0;
14  
15  for (const job of sorted) {
16    for (let t = Math.min(maxDeadline, job.deadline) - 1; t >= 0; t--) {
17      if (slots[t] === null) {
18        slots[t] = job.id;
19        totalProfit += job.profit;
20        break;
21      }
22    }
23  }
24  
25  return {
26    sequence: slots.filter(id => id !== null) as string[],
27    totalProfit
28  };
29}
30
31export function matrixChainMultiplication(p: number[]): { cost: number; split: number[][] } {
32  const n = p.length - 1;
33  const m = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
34  const s = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
35  
36  for (let l = 2; l <= n; l++) {
37    for (let i = 1; i <= n - l + 1; i++) {
38      const j = i + l - 1;
39      m[i][j] = Infinity;
40      for (let k = i; k < j; k++) {
41        const q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
42        if (q < m[i][j]) {
43          m[i][j] = q;
44          s[i][j] = k;
45        }
46      }
47    }
48  }
49  
50  return { cost: m[1][n], split: s };
51}