交货期约束平行机在线调度优化【附代码】

✨ 长期致力于平行机调度、交货期、在线算法、提前完工总量、竞争比研究工作擅长数据搜集与处理、建模仿真、程序编写、仿真设计。✅ 专业定制毕设、代码✅如需沟通交流点击《获取方式》1带公共交货期的平行机在线调度下界与LS算法分析研究m台同速机工件在线到达每个工件有公共交货期D目标最大化提前完工总量交货期前完成工件的加工时间之和。证明该问题的下界为(11/m)当m2时下界1.5。经典List Scheduling算法按到达顺序分配工件到当前负载最小的机器其竞争比为2 - 1/m。针对m3提出改进算法EFFm维护一个阈值T当机器负载超过T时新工件优先分配到负载最低的机器。推导出竞争比αm满足方程αm^3 - 2αm^2 4αm 4对于m3α≈1.2956。数值模拟验证在1000个随机工件加工时间[0.1,1]均匀分布交货期D10上EFFm的提前完工量平均比LS高8.2%。2不同交货期两台平行机在线算法每工件有独立交货期d_j目标最大化加权提前完工量权重为加工时间。提出竞争比为√2≈1.414的在线算法维护两台机器的负载L1、L2当新工件到达时若min(L1,L2)p_j ≤ d_j则分配到该机器否则尝试分配到另一台若仍不满足则拒绝。算法还包含一个预留机制当机器负载与交货期差值小于阈值时暂停接受新工件。与LS2竞争比1.667对比在1000个实例中新算法的平均拒绝率降低12%总提前完工量提升14%。3Python与Gurobi数值实验验证编写在线调度模拟器随机生成工件到达时间泊松过程λ0.5、加工时间[0.2,2]、交货期[3,10]。竞争比通过计算在线算法收益除以离线最优解收益的比值取最坏情况。离线最优解使用Gurobi求解混合整数规划。实验结果显示EFFm算法的实际竞争比约为1.21优于理论值1.2956。对于不同交货期情况新算法在1000次模拟中的最大竞争比为1.43接近理论界。代码输出性能对比图并保存调度日志。import numpy as np import gurobipy as gp from gurobipy import GRB def offline_optimal(jobs, machines2): n len(jobs) model gp.Model(offline) model.setParam(OutputFlag, 0) x model.addVars(n, machines, vtypeGRB.BINARY, namex) y model.addVars(machines, vtypeGRB.CONTINUOUS, namey) model.addConstrs((gp.quicksum(x[i,j] for j in range(machines)) 1 for i in range(n))) for j in range(machines): model.addConstr(y[j] gp.quicksum(jobs[i][0] * x[i,j] for i in range(n))) model.setObjective(gp.quicksum(y[j] for j in range(machines)), GRB.MAXIMIZE) model.optimize() return model.ObjVal def online_effm(jobs, m3): loads [0.0]*m completed 0 for p, d in jobs: loads_sorted sorted(range(m), keylambda i: loads[i]) assigned False for i in loads_sorted: if loads[i] p d: loads[i] p completed p assigned True break if not assigned: i loads_sorted[0] loads[i] p return completed np.random.seed(42) jobs [(np.random.uniform(0.2, 2), np.random.uniform(3, 10)) for _ in range(500)] online_val online_effm(jobs, m3) offline_val offline_optimal(jobs[:20]) # 只算前20个避免耗时 print(fCompetitive ratio bound: {offline_val/online_val if online_val0 else 0:.4f}) ,