Java中的贪心算法应用：半导体晶圆生产问题详解
1. 问题背景与定义
半导体晶圆生产是芯片制造的核心环节，涉及复杂的生产调度和资源分配问题。在这个领域中，贪心算法常被用于解决以下典型问题：
1.1 晶圆生产调度问题
给定：
- 一组晶圆生产任务，每个任务有处理时间、截止时间和优先级
- 一组可用的生产设备（机器）
- 各种生产约束（如设备准备时间、温度转换时间等）
目标：
- 安排晶圆生产顺序，以优化某些指标（如总完成时间最小、按时完成的任务数最多等）
1.2 问题形式化定义
对于n个晶圆生产任务和m台机器：
- 每个任务j有处理时间p_j，截止时间d_j，权重w_j（表示重要性）
- 每台机器一次只能处理一个任务
- 任务一旦开始不能中断
常见优化目标：
- 最小化最大完成时间（Makespan）
- 最小化总加权完成时间
- 最大化按时完成的任务数
2. 贪心算法基本原理
贪心算法在每一步选择当前看起来最优的选项，希望这种局部最优选择能导致全局最优解。对于调度问题，常见的贪心策略包括：
- 最短处理时间优先(SPT): 优先安排处理时间短的任务
- 最早截止时间优先(EDD): 优先安排截止时间早的任务
- 最高权重优先(WSPT): 优先安排权重高的任务
- 最小松弛时间优先: 优先安排松弛时间(截止时间-剩余处理时间)小的任务
3. Java实现：最小化最大完成时间问题
3.1 问题描述
有n个晶圆生产任务和m台相同机器，如何分配任务到机器上使得所有任务完成时间中的最大值最小。
3.2 贪心策略：最长处理时间优先(LPT)
将任务按处理时间从大到小排序，每次将当前最长任务分配给当前负载最轻的机器。
3.3 Java实现代码
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class WaferScheduling {
// 表示晶圆任务
static class Task {
int id;
int processingTime;
public Task(int id, int processingTime) {
this.id = id;
this.processingTime = processingTime;
}
}
// 表示机器及其当前负载
static class Machine {
int id;
int load; // 当前机器上所有任务的总处理时间
public Machine(int id, int load) {
this.id = id;
this.load = load;
}
}
/**
* 使用LPT贪心算法调度晶圆生产任务
* @param tasks 晶圆任务数组
* @param m 机器数量
* @return 各机器分配的任务列表和最大完成时间
*/
public static Object[] scheduleTasks(Task[] tasks, int m) {
// 1. 按处理时间降序排序
Arrays.sort(tasks, new Comparator<Task>() {
@Override
public int compare(Task t1, Task t2) {
return Integer.compare(t2.processingTime, t1.processingTime);
}
});
// 2. 使用优先队列（最小堆）来管理机器负载
PriorityQueue<Machine> pq = new PriorityQueue<>(m, new Comparator<Machine>() {
@Override
public int compare(Machine m1, Machine m2) {
return Integer.compare(m1.load, m2.load);
}
});
// 初始化机器
for (int i = 0; i < m; i++) {
pq.offer(new Machine(i, 0));
}
// 3. 分配任务
@SuppressWarnings("unchecked")
java.util.List<Task>[] assignments = new java.util.ArrayList[m];
for (int i = 0; i < m; i++) {
assignments[i] = new java.util.ArrayList<>();
}
for (Task task : tasks) {
Machine machine = pq.poll();
machine.load += task.processingTime;
assignments[machine.id].add(task);
pq.offer(machine);
}
// 4. 计算最大完成时间
int maxLoad = 0;
while (!pq.isEmpty()) {
maxLoad = Math.max(maxLoad, pq.poll().load);
}
return new Object[]{assignments, maxLoad};
}
public static void main(String[] args) {
// 示例：5个晶圆生产任务，3台机器
Task[] tasks = {
new Task(1, 5), // 任务ID=1，处理时间=5
new Task(2, 3),
new Task(3, 7),
new Task(4, 2),
new Task(5, 4)
};
int m = 3; // 3台机器
Object[] result = scheduleTasks(tasks, m);
@SuppressWarnings("unchecked")
java.util.List<Task>[] assignments = (java.util.List<Task>[]) result[0];
int maxCompletionTime = (int) result[1];
System.out.println("最大完成时间: " + maxCompletionTime);
System.out.println("任务分配情况:");
for (int i = 0; i < m; i++) {
System.out.print("机器" + (i+1) + ": ");
for (Task t : assignments[i]) {
System.out.print("任务" + t.id + "(时间=" + t.processingTime + ") ");
}
System.out.println("=> 总时间: " + assignments[i].stream().mapToInt(t -> t.processingTime).sum());
}
}
}
3.4 代码解析
- Task类：表示晶圆生产任务，包含任务ID和处理时间
- Machine类：表示生产机器，跟踪当前负载
- scheduleTasks方法：
- 将任务按处理时间降序排序
- 使用最小堆优先队列管理机器，总是选择当前负载最小的机器
- 将每个任务分配给当前负载最轻的机器
- 计算并返回最大完成时间
- main方法：演示如何使用该算法
3.5 算法分析
时间复杂度：
- 排序：O(n log n)
- 优先队列操作：每次插入和删除O(log m)，共n次 → O(n log m)
- 总时间复杂度：O(n log n + n log m) = O(n log n)（因为n通常远大于m）
近似比：LPT算法是4/3-近似的，即最坏情况下解不超过最优解的4/3倍
4. Java实现：最大化按时完成任务数问题
4.1 问题描述
给定n个晶圆生产任务和1台机器，每个任务有处理时间和截止时间，如何安排任务顺序使按时完成的任务数最多。
4.2 贪心策略：最早截止时间优先(EDD)
按截止时间从早到晚排序，依次尝试将任务加入调度，如果加入后会导致某些任务超期，则舍弃当前任务。
4.3 Java实现代码
import java.util.Arrays;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.List;
public class WaferDeadlineScheduling {
static class Task {
int id;
int processingTime;
int deadline;
public Task(int id, int processingTime, int deadline) {
this.id = id;
this.processingTime = processingTime;
this.deadline = deadline;
}
}
/**
* 最大化按时完成的任务数
* @param tasks 任务数组
* @return 按时完成的任务列表和数量
*/
public static Object[] maximizeOnTimeTasks(Task[] tasks) {
// 1. 按截止时间升序排序
Arrays.sort(tasks, new Comparator<Task>() {
@Override
public int compare(Task t1, Task t2) {
return Integer.compare(t1.deadline, t2.deadline);
}
});
List<Task> scheduled = new ArrayList<>();
int currentTime = 0;
// 2. 依次尝试安排任务
for (Task task : tasks) {
if (currentTime + task.processingTime <= task.deadline) {
scheduled.add(task);
currentTime += task.processingTime;
}
}
return new Object[]{scheduled, scheduled.size()};
}
public static void main(String[] args) {
// 示例：5个晶圆生产任务
Task[] tasks = {
new Task(1, 3, 5), // 任务ID=1，处理时间=3，截止时间=5
new Task(2, 2, 4),
new Task(3, 1, 7),
new Task(4, 4, 8),
new Task(5, 2, 6)
};
Object[] result = maximizeOnTimeTasks(tasks);
@SuppressWarnings("unchecked")
List<Task> scheduled = (List<Task>) result[0];
int count = (int) result[1];
System.out.println("按时完成的任务数: " + count);
System.out.println("按时完成的任务:");
int time = 0;
for (Task t : scheduled) {
System.out.println("任务" + t.id + ": 开始=" + time +
", 完成=" + (time + t.processingTime) +
", 截止=" + t.deadline);
time += t.processingTime;
}
}
}
4.4 代码解析
- Task类：增加了截止时间属性
- maximizeOnTimeTasks方法：
- 按截止时间升序排序
- 依次尝试安排任务，如果加入后不会导致超期则接受
- main方法：演示算法使用
4.5 算法分析
- 时间复杂度：主要由排序决定，O(n log n)
- 最优性：对于单机问题，EDD策略可以最大化按时完成的任务数
5. Java实现：最小化总加权完成时间问题
5.1 问题描述
给定n个晶圆生产任务和1台机器，每个任务有处理时间、权重，如何安排顺序使Σw_jC_j最小，其中C_j是任务j的完成时间。
5.2 贪心策略：最高权重/处理时间比优先(WSPT)
按w_j/p_j的比值从高到低排序，依次安排任务。
5.3 Java实现代码
import java.util.Arrays;
import java.util.Comparator;
public class WeightedWaferScheduling {
static class Task {
int id;
int processingTime;
int weight;
double ratio;
public Task(int id, int processingTime, int weight) {
this.id = id;
this.processingTime = processingTime;
this.weight = weight;
this.ratio = (double)weight / processingTime;
}
}
/**
* 最小化总加权完成时间
* @param tasks 任务数组
* @return 任务顺序和总加权完成时间
*/
public static Object[] minimizeWeightedCompletionTime(Task[] tasks) {
// 1. 按权重/处理时间比降序排序
Arrays.sort(tasks, new Comparator<Task>() {
@Override
public int compare(Task t1, Task t2) {
return Double.compare(t2.ratio, t1.ratio);
}
});
// 2. 计算总加权完成时间
int currentTime = 0;
int totalWeightedCompletionTime = 0;
for (Task task : tasks) {
currentTime += task.processingTime;
totalWeightedCompletionTime += task.weight * currentTime;
}
return new Object[]{tasks, totalWeightedCompletionTime};
}
public static void main(String[] args) {
// 示例：4个晶圆生产任务
Task[] tasks = {
new Task(1, 3, 10), // 任务ID=1，处理时间=3，权重=10
new Task(2, 4, 12),
new Task(3, 2, 8),
new Task(4, 5, 15)
};
Object[] result = minimizeWeightedCompletionTime(tasks);
Task[] scheduled = (Task[]) result[0];
int total = (int) result[1];
System.out.println("总加权完成时间: " + total);
System.out.println("任务顺序:");
int time = 0;
for (Task t : scheduled) {
System.out.println("任务" + t.id + ": 开始=" + time +
", 完成=" + (time + t.processingTime) +
", 权重=" + t.weight);
time += t.processingTime;
}
}
}
5.4 代码解析
- Task类：增加了权重属性和权重/处理时间比
- minimizeWeightedCompletionTime方法：
- 按权重/处理时间比降序排序
- 计算总加权完成时间
- main方法：演示算法使用
5.5 算法分析
- 时间复杂度：O(n log n)
- 最优性：WSPT规则对于单机问题可以得到最优解
6. 更复杂的晶圆生产调度问题
实际半导体制造中的调度问题更加复杂，需要考虑：
6.1 多阶段流水线调度
晶圆生产通常包含多个工艺阶段（光刻、蚀刻、沉积等），每个阶段可能有多个并行机器。
6.2 带准备时间的调度
更换产品类型时需要准备时间（温度调整、模具更换等）
6.3 Java实现：带序列相关准备时间的调度
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
public class WaferSetupTimeScheduling {
static class Task {
int id;
int processingTime;
int family; // 任务所属的家族（相同家族不需要准备时间）
public Task(int id, int processingTime, int family) {
this.id = id;
this.processingTime = processingTime;
this.family = family;
}
}
/**
* 带序列相关准备时间的调度
* @param tasks 任务数组
* @param setupTime 不同家族间的准备时间
* @return 调度顺序和总完成时间
*/
public static Object[] scheduleWithSetupTimes(Task[] tasks, int setupTime) {
// 1. 按家族分组，家族内按SPT排序
Arrays.sort(tasks, new Comparator<Task>() {
@Override
public int compare(Task t1, Task t2) {
if (t1.family != t2.family) {
return Integer.compare(t1.family, t2.family);
}
return Integer.compare(t1.processingTime, t2.processingTime);
}
});
// 2. 计算总完成时间
int totalCompletionTime = 0;
int currentTime = 0;
int lastFamily = -1;
for (Task task : tasks) {
if (task.family != lastFamily) {
currentTime += setupTime;
lastFamily = task.family;
}
currentTime += task.processingTime;
totalCompletionTime += currentTime;
}
return new Object[]{tasks, totalCompletionTime};
}
public static void main(String[] args) {
// 示例：6个晶圆生产任务，属于3个不同家族
Task[] tasks = {
new Task(1, 3, 1), // 任务ID=1，处理时间=3，家族=1
new Task(2, 2, 2),
new Task(3, 4, 1),
new Task(4, 1, 3),
new Task(5, 5, 2),
new Task(6, 2, 1)
};
int setupTime = 2; // 家族切换需要2单位时间
Object[] result = scheduleWithSetupTimes(tasks, setupTime);
Task[] scheduled = (Task[]) result[0];
int total = (int) result[1];
System.out.println("总完成时间: " + total);
System.out.println("任务顺序:");
int time = 0;
int lastFamily = -1;
for (Task t : scheduled) {
if (t.family != lastFamily) {
time += setupTime;
System.out.println("切换到家族" + t.family + ", 准备时间=" + setupTime);
lastFamily = t.family;
}
System.out.println("任务" + t.id + ": 开始=" + time +
", 完成=" + (time + t.processingTime) +
", 家族=" + t.family);
time += t.processingTime;
}
}
}
7. 性能优化与工业实践
在实际半导体制造中，还需要考虑以下优化：
7.1 启发式改进
- 迭代贪心：多次运行贪心算法，每次移除部分任务后重新调度
- 局部搜索：对贪心解进行邻域搜索改进
7.2 混合方法
- 贪心算法与动态规划结合
- 贪心算法与整数规划结合
7.3 并行计算
利用多线程加速贪心算法的执行：
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
public class ParallelWaferScheduling {
static class ParallelLPT extends RecursiveAction {
private static final int THRESHOLD = 1000;
private Task[] tasks;
private int start, end;
private Machine[] machines;
public ParallelLPT(Task[] tasks, int start, int end, Machine[] machines) {
this.tasks = tasks;
this.start = start;
this.end = end;
this.machines = machines;
}
@Override
protected void compute() {
if (end - start <= THRESHOLD) {
// 直接处理小任务
for (int i = start; i < end; i++) {
assignTask(tasks[i]);
}
} else {
// 分而治之
int mid = (start + end) >>> 1;
invokeAll(
new ParallelLPT(tasks, start, mid, machines),
new ParallelLPT(tasks, mid, end, machines)
);
}
}
private void assignTask(Task task) {
// 找到负载最轻的机器
Machine lightest = machines[0];
for (Machine m : machines) {
if (m.load < lightest.load) {
lightest = m;
}
}
lightest.load += task.processingTime;
}
}
// 其他代码与前面示例类似...
}
8. 总结
贪心算法在半导体晶圆生产调度中有着广泛应用，尽管它不能保证总是得到最优解，但在许多情况下可以提供高质量的近似解，且计算效率高。Java作为一种面向对象的语言，非常适合实现这些调度算法，通过合理设计类和接口，可以构建灵活、可扩展的调度系统。
关键要点：
- 不同调度目标需要不同的贪心策略
- 贪心算法实现简单、运行快速
- 实际应用中常需要结合其他技术进行改进
- Java的面向对象特性和丰富类库为算法实现提供了良好支持
在实际半导体制造系统中，通常会结合多种调度算法，并根据实时生产数据进行动态调整，以达到最佳的生产效率和资源利用率。