多机调度问题

问题描述：设有n个独立的作业{1,2，，n}由m台相同的机器进行加工处理。作业 i 所需的处理时间为t_i ,(t为正整数)。约定每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理，即作业不能拆分成更小的子作业。要求给出一种作业调度方案，使得所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

贪心算法

当n⇐m 的时候，直接将n个作业分配个n个机器 当n>m 的时候，贪心策略是最长处理时间优先。优先将长时间的作业分配给空闲的机器

 
function scheduleJobs(jobTimes,numMachines ){
 // 每个对象包含原始索引（作为ID）和处理时间
  const jobs = jobTimes.map((time, index) => ({
    id: index + 1, // 作业ID从1开始
    time: time,
  }));
  // --- 步骤 1: 按处理时间降序排序 (LPT核心) ---
  jobs.sort((a, b) => b.time - a.time);
  // 如果机器数量大于等于作业数量，每个作业独占一台机器
  // 最短完工时间就是最长作业的时间
  if (numMachines >= jobs.length) {
    const schedule = {};
    for (let i = 0; i < jobs.length; i++) {
        schedule[`机器 ${i + 1}`] = {
            jobs: [jobs[i]],
            totalLoad: jobs[i].time
        };
    }
    return {
        schedule,
        makespan: jobs.length > 0 ? jobs[0].time : 0
    };
    
  }
  // --- 步骤 2: 初始化机器 ---
  // 创建一个数组来表示所有机器
  // 每个机器对象包含分配给它的作业列表和当前的总负载（累计工作时间）
  const machines = [];
  for (let i = 0; i < numMachines; i++) {
    machines.push({
      jobs: [],
      totalLoad: 0,
    });
  }
 
  // --- 步骤 3 & 4: 遍历作业并分配给负载最小的机器 ---
  for (const job of jobs) {
    // 找到当前总负载最小的机器
    let minLoadMachine = machines[0];
    let minLoadIndex = 0;
    for (let i = 1; i < machines.length; i++) {
      if (machines[i].totalLoad < minLoadMachine.totalLoad) {
        minLoadMachine = machines[i];
        minLoadIndex = i;
      }
    }
 
    // 将当前作业分配给这台机器
    machines[minLoadIndex].jobs.push(job);
    // 更新这台机器的总负载
    machines[minLoadIndex].totalLoad += job.time;
  }
 
  // --- 步骤 6: 计算最终结果 ---
  // 格式化最终的调度方案
  const finalSchedule = {};
  let makespan = 0;
  machines.forEach((machine, index) => {
    finalSchedule[`机器 ${index + 1}`] = machine;
    if (machine.totalLoad > makespan) {
      makespan = machine.totalLoad;
    }
  });
 
  return {
    schedule: finalSchedule,
    makespan: makespan,
  };
}
const n_jobs = [2, 14, 4, 16, 6, 5, 3]; 
// 由3台相同的机器处理
const m_machines = 3;
 
// 调用函数计算调度方案
const result = scheduleJobs(n_jobs, m_machines);
 
// --- 打印结果 ---
console.log(`给定的作业处理时间: [${n_jobs.join(', ')}]`);
console.log(`可用的机器数量: ${m_machines}`);
console.log("\n--- 作业调度方案 ---");
 
for (const machineName in result.schedule) {
  const machine = result.schedule[machineName];
  const jobIds = machine.jobs.map(j => `作业${j.id}(${j.time})`).join(', ');
  console.log(`${machineName}: 分配的作业 [${jobIds}] | 总耗时: ${machine.totalLoad}`);
}
 
console.log(`\n=> 所有作业处理完成所需的最短时间 (Makespan) 为: ${result.makespan}`);

reference