一、游戏场景与核心问题
“烹饪大师”是一款模拟经营类游戏。玩家在限定时间内接收订单，每个订单由若干道菜品组成，每道菜品需要经过切配、煎炒、炖煮、摆盘等多个工序，每个工序占用特定的厨具与厨师。玩家需要合理调度厨师与厨具，最大化完成订单的总收益。
游戏的核心问题可以抽象为多机调度（Parallel Machine Scheduling）与资源受限项目调度问题（RCPSP）的组合。我们追求在有限时间窗口内：
– 完成尽可能多的订单（收益最大化）
– 不超时交付（违约惩罚最小化）
– 厨师与厨具的利用率最高
本文给出一种基于贪心调度 + 优先级队列的实用方案，配合模拟退火作为离线优化，给出可运行的 Java 实现。
二、问题建模
2.1 数据结构
/**
* 菜品工序定义
*/
class Step {
String station; // 厨具名称：切配台/煎锅/炖锅/摆盘台
int duration; // 该工序耗时（秒）
int chefsNeeded; // 需要的厨师数量
Step(String station, int duration, int chefsNeeded) {
this.station = station;
this.duration = duration;
this.chefsNeeded = chefsNeeded;
}
}
/**
* 菜品
*/
class Dish {
String name;
List<Step> steps; // 工序按顺序执行
int profit; // 完成该菜品的收益
Dish(String name, int profit) { this.name = name; this.steps = new ArrayList<>(); this.profit = profit; }
}
/**
* 订单
*/
class Order {
String id;
List<Dish> dishes;
long deadline; // 截止时间（秒，相对游戏开始）
int penalty; // 逾期每分钟惩罚
Order(String id, long deadline, int penalty) { this.id = id; this.dishes = new ArrayList<>(); this.deadline = deadline; this.penalty = penalty; }
}
2.2 厨具与厨师资源
/**
* 厨具：每个工位有数量限制
*/
class Station {
String name;
int capacity; // 同时间可容纳的厨师数
int busyUntil; // 释放时间（最早可用的时刻）
Station(String name, int capacity) { this.name = name; this.capacity = capacity; this.busyUntil = 0; }
}
/**
* 厨师
*/
class Chef {
int id;
int skillLevel; // 影响工序的实际耗时，1为标准
long availableAt; // 该厨师下一次可用的时刻
int completed; // 累计完成菜品数
Chef(int id, int skillLevel) { this.id = id; this.skillLevel = skillLevel; this.availableAt = 0; this.completed = 0; }
}
三、贪心调度策略
贪心思路：每一时刻选择”当前性价比最高”的可执行工序执行，性价比 = 收益 / (剩余时间 + 风险惩罚)。具体规则：
- 优先级：对每个未完成的订单计算
urgency = (deadline - now) / max(1, remainingWork)，越小越紧急。 - 工序选择：在所有就绪工序中，选
profit / time最大者；同分时优先选工位空闲者。 - 回填：当某工位空闲但无对应工序时，从其他订单”借调”工序填充。
/**
* 贪心调度器
*/
class GreedyScheduler {
List<Chef> chefs;
Map<String, Station> stations;
PriorityQueue<Order> orderQueue; // 按紧急度排序
Map<String, List<Dish>> inProgress; // 订单 -> 已开工菜品
Set<String> finished;
GreedyScheduler(List<Chef> chefs, Map<String, Station> stations) {
this.chefs = chefs;
this.stations = stations;
this.orderQueue = new PriorityQueue<>((a, b) -> Double.compare(urgency(a), urgency(b)));
this.inProgress = new HashMap<>();
this.finished = new HashSet<>();
}
double urgency(Order o) {
long now = currentTime();
long remaining = estimateRemainingWork(o);
return (o.deadline - now) / Math.max(1.0, remaining);
}
long estimateRemainingWork(Order o) {
long sum = 0;
for (Dish d : o.dishes) {
for (Step s : d.steps) sum += s.duration;
}
return sum;
}
/**
* 核心调度：返回当前时刻可执行的最优 (chef, step, order, dish)
*/
Optional<int[]> pickNextTask() {
long now = currentTime();
int bestScore = Integer.MIN_VALUE;
int[] best = null;
// 收集所有就绪工序
for (Order o : orderQueue) {
if (finished.contains(o.id)) continue;
for (Dish d : o.dishes) {
if (d.steps.isEmpty()) continue; // 已完成
Step next = d.steps.get(0);
Station st = stations.get(next.station);
if (st.busyUntil > now) continue; // 工位忙
if (chefsBusy() >= chefs.size()) break; // 厨师满
// 收益评分 = 菜品收益 / 工序耗时，工位利用率加权
int score = (d.profit * 100) / Math.max(1, next.duration);
if (score > bestScore) {
bestScore = score;
best = new int[]{o.id.hashCode(), d.name.hashCode()};
}
}
}
return best == null ? Optional.empty() : Optional.of(best);
}
}
四、可运行 Demo
下面给出一个可在控制台模拟整个餐厅运转的完整程序。
import java.util.*;
import java.util.stream.Collectors;
/**
* 烹饪大师 — 贪心调度 + 资源分配 Demo
* 运行：javac CookingMaster.java && java CookingMaster
*/
public class CookingMaster {
// ============= 数据模型 =============
static class Step {
String station; int duration; int chefsNeeded;
Step(String s, int d, int c) { station = s; duration = d; chefsNeeded = c; }
}
static class Dish {
String name; List<Step> steps = new ArrayList<>(); int profit;
Dish(String n, int p) { name = n; profit = p; }
Dish add(String station, int duration) {
steps.add(new Step(station, duration, 1)); return this;
}
}
static class Order {
String id; List<Dish> dishes = new ArrayList<>(); long deadline; int penalty;
Order(String i, long d, int p) { id = i; deadline = d; penalty = p; }
}
static class Station { String name; int capacity; int busyUntil;
Station(String n, int c) { name = n; capacity = c; busyUntil = 0; } }
static class Chef { int id; int skill; long availableAt = 0; int done = 0;
Chef(int i, int s) { id = i; skill = s; } }
// ============= 调度器 =============
static class Scheduler {
List<Chef> chefs;
Map<String, Station> stations;
long now = 0;
int totalProfit = 0, totalPenalty = 0;
List<String> log = new ArrayList<>();
Scheduler(List<Chef> chefs, Map<String, Station> stations) {
this.chefs = chefs; this.stations = stations;
}
/**
* 模拟运行所有订单直到全部完成或超时
*/
void run(List<Order> orders) {
// 跟踪每个订单的工序进度
Map<String, Map<String, Integer>> progress = new HashMap<>();
for (Order o : orders) for (Dish d : o.dishes)
progress.computeIfAbsent(o.id, k -> new HashMap<>()).put(d.name, 0);
int safety = 10000;
while (safety-- > 0) {
// 1. 推进时间到下一个事件
now = nextEventTime(orders, progress);
if (now == Long.MAX_VALUE) break;
// 2. 释放到期的厨师
for (Chef c : chefs) c.availableAt = Math.min(c.availableAt, now);
// 3. 选择最紧急订单中性价比最高的工序
Order chosen = orders.stream()
.filter(o -> !isDone(o, progress))
.min(Comparator.comparingDouble(this::urgency))
.orElse(null);
if (chosen == null) break;
Dish target = pickBestDish(chosen, progress);
if (target == null) { now += 1; continue; }
Step step = target.steps.get(progress.get(chosen.id).get(target.name));
// 4. 分配厨师与工位
Chef chef = chefs.stream()
.filter(c -> c.availableAt <= now)
.findFirst().orElse(null);
Station st = stations.get(step.station);
if (chef == null || st.busyUntil > now) { now += 1; continue; }
// 5. 执行
int realDuration = Math.max(1, step.duration / chef.skill);
chef.availableAt = now + realDuration;
st.busyUntil = now + realDuration;
int cur = progress.get(chosen.id).get(target.name);
progress.get(chosen.id).put(target.name, cur + 1);
log.add(String.format("t=%d 厨师#%d 加工 %s 的 %s 工位 (耗时 %ds)",
now, chef.id, target.name, step.station, realDuration));
// 6. 若该订单所有菜品完成则结算
if (isDone(chosen, progress)) {
if (now <= chosen.deadline) {
totalProfit += chosen.dishes.stream().mapToInt(d -> d.profit).sum();
log.add(String.format(">>> 订单 %s 准时完成，奖励 +%d", chosen.id,
chosen.dishes.stream().mapToInt(d -> d.profit).sum()));
} else {
int over = (int)((now - chosen.deadline) / 60);
totalPenalty += over * chosen.penalty;
log.add(String.format("XXX 订单 %s 逾期 %d 分钟，惩罚 -%d", chosen.id, over, over * chosen.penalty));
}
}
}
}
long nextEventTime(List<Order> orders, Map<String, Map<String, Integer>> progress) {
long t = Long.MAX_VALUE;
for (Chef c : chefs) t = Math.min(t, c.availableAt);
for (Station s : stations.values()) t = Math.min(t, s.busyUntil);
for (Order o : orders) if (!isDone(o, progress)) t = Math.min(t, o.deadline);
return t;
}
double urgency(Order o) {
long rem = 0;
Map<String, Integer> p = progress.get(o.id);
if (p == null) return 1e9;
for (Dish d : o.dishes) {
int start = p.getOrDefault(d.name, 0);
for (int i = start; i < d.steps.size(); i++) rem += d.steps.get(i).duration;
}
return (o.deadline - now) / Math.max(1.0, rem);
}
Dish pickBestDish(Order o, Map<String, Map<String, Integer>> progress) {
int best = Integer.MIN_VALUE; Dish res = null;
for (Dish d : o.dishes) {
int idx = progress.get(o.id).getOrDefault(d.name, 0);
if (idx >= d.steps.size()) continue;
Step s = d.steps.get(idx);
Station st = stations.get(s.station);
if (st.busyUntil > now) continue;
int score = d.profit * 100 / Math.max(1, s.duration);
if (score > best) { best = score; res = d; }
}
return res;
}
boolean isDone(Order o, Map<String, Map<String, Integer>> progress) {
Map<String, Integer> p = progress.get(o.id);
if (p == null) return true;
for (Dish d : o.dishes)
if (p.getOrDefault(d.name, 0) < d.steps.size()) return false;
return true;
}
}
// ============= 主程序 =============
public static void main(String[] args) {
// 资源：3 个工位
Map<String, Station> stations = new LinkedHashMap<>();
stations.put("切配台", new Station("切配台", 2));
stations.put("煎锅", new Station("煎锅", 1));
stations.put("炖锅", new Station("炖锅", 1));
stations.put("摆盘台", new Station("摆盘台", 1));
// 厨师：4 人
List<Chef> chefs = Arrays.asList(
new Chef(1, 1), new Chef(2, 1), new Chef(3, 2), new Chef(4, 2));
// 订单构造
Order o1 = new Order("A001", 600, 50);
o1.dishes.add(new Dish("宫保鸡丁", 80).add("切配台", 30).add("煎锅", 90).add("摆盘台", 20));
o1.dishes.add(new Dish("番茄蛋汤", 50).add("切配台", 20).add("炖锅", 120).add("摆盘台", 15));
Order o2 = new Order("A002", 500, 40);
o2.dishes.add(new Dish("红烧肉", 120).add("切配台", 40).add("炖锅", 180).add("摆盘台", 25));
Order o3 = new Order("A003", 800, 60);
o3.dishes.add(new Dish("清炒时蔬", 40).add("切配台", 25).add("煎锅", 60).add("摆盘台", 15));
o3.dishes.add(new Dish("酸辣土豆丝", 45).add("切配台", 30).add("煎锅", 50).add("摆盘台", 15));
Scheduler sch = new Scheduler(chefs, stations);
sch.run(Arrays.asList(o1, o2, o3));
System.out.println("=== 调度日志 ===");
sch.log.forEach(System.out::println);
System.out.println("\n总收益：" + sch.totalProfit);
System.out.println("总惩罚：" + sch.totalPenalty);
System.out.println("净利润：" + (sch.totalProfit - sch.totalPenalty));
}
}
五、进阶：模拟退火做离线参数寻优
贪心策略对单步最优敏感，但工位与厨师的容量、订单到达节奏不同，最优配置会变化。我们用模拟退火（Simulated Annealing）在离线阶段搜索较优的优先级权重与厨师分配。
import java.util.Random;
/**
* 模拟退火搜索最优调度参数
*/
class AnnealingTuner {
double[] weights = {1.0, 0.5, 0.2}; // 收益、紧急度、负载均衡权重
Random rnd = new Random(42);
double energy(List<Order> orders, List<Chef> chefs, Map<String, Station> stations) {
Scheduler s = new Scheduler(chefs, stations);
s.run(orders);
return -(s.totalProfit - s.totalPenalty);
}
void tune(List<Order> orders, List<Chef> chefs, Map<String, Station> stations) {
double T = 100.0, cool = 0.995;
double bestE = energy(orders, chefs, stations);
double[] bestW = weights.clone();
for (int it = 0; it < 5000; it++) {
double[] w = weights.clone();
int i = rnd.nextInt(w.length);
w[i] += (rnd.nextDouble() - 0.5) * 0.1;
weights = w;
double e = energy(orders, chefs, stations);
if (e < bestE || Math.exp((bestE - e) / T) > rnd.nextDouble()) {
bestE = e; bestW = w.clone();
} else weights = bestW.clone();
T *= cool;
}
System.out.println("最优权重：" + Arrays.toString(bestW) + " 能量=" + bestE);
}
}
六、复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 单次选工序 | O(D × S) | O(1) |
| 一次完整调度 | O(T × D × S) | O(D) |
| 模拟退火 N 次迭代 | O(N × T × D × S) | O(D) |
其中 D 为订单菜品数、S 为单菜品工序数、T 为模拟推进的时间步。
七、可扩展方向
- 多目标优化：将净利润与公平性同时作为目标，使用 NSGA-II。
- 强化学习：将调度过程建模为 MDP，用 PPO 学习长程策略。
- 不确定性建模：订单到达符合泊松过程，使用随机规划。
八、结语
烹饪大师看似是休闲经营游戏，但背后融合了调度理论、组合优化、贪心策略等经典算法思想。一个简单可读的 Java 实现，就能让游戏里的”手忙脚乱”变成”从容有序”。读者可在源码基础上扩展可视化（JavaFX/Swing），把日志绘制成甘特图，更直观地观察调度过程。
