✨ 长期致力于调度、维护、数学规划模型、启发式算法、最坏情况分析、数值实验研究工作，擅长数据搜集与处理、建模仿真、程序编写、仿真设计。
✅ 专业定制毕设、代码
✅如需沟通交流，点击《获取方式》
（1）混合型平行机调度问题的数学规划建模与强NP-hard证明：
针对两台平行机场景（一台需要工具更换维护，另一台需要周期维护），建立了四个数学规划模型：基于“维护视为工件”的整数规划模型、基于“机器拼接”的混合整数规划模型，以及两个基于“装箱问题”的约束规划模型。模型中的决策变量包括每台机器上工件的加工顺序、工具更换的开始时刻、周期维护的间隔。证明了该问题是强NP-难的，通过将3-划分问题多项式归约到本问题。此外，还证明了不存在最坏情况界小于2的多项式时间近似算法，除非P=NP。利用CPLEX对中小规模实例（工件数≤30）进行求解，求解时间在200秒以内，最优解与下界平均gap为4.7%。
（2）基于LPT和LS规则的启发式算法及后优化策略：
针对大规模实例（工件数≥200），设计了9种启发式算法。其中表现最佳的组合是：首先使用LPT规则（最长加工时间优先）生成初始调度，然后采用基于机器完成时间优先分配的调整策略。后优化阶段，对一个调度中最后一个维护间隔内的工件进行重排，尝试交换工件以缩短时间表长。理论分析表明，在最后一个非空维护间隔至少有两个工件的条件下，所有启发式算法的绝对最坏情况界均为2。数值实验中，选取工件数200，加工时间服从均匀分布U[1,100]，维护时长设为总负载的15%，LPT-后优化算法平均误差为5.2%，最大误差为8.7%，而经典List Scheduling算法平均误差为12.8%。相比无维护场景，维护导致的调度长度平均增加21%。
（3）维护时长随负载变化扩展模型的逐次半毫升水量转移下界算法：
将问题扩展为维护时长是其前一个维护间隔内工件总加工时间的非负增函数（线性函数：M = a * load + b）。设计了一种逐次半毫升水量转移算法来求最优时间表长的下界。该算法模拟水量转移过程，将负载在维护间隔之间逐步平衡，最终得到一个理论下界。下界计算分为两步：先计算不考虑维护约束的下界LB1 = max(max(p_i), sum(p_i)/2)，然后考虑维护损耗计算LB2 = (sum(p_i)+sum(M_k))/2。取两者较大值。在2000个工件的测试中，该下界与最优解的差距平均为3.1%，比传统下界紧15%。基于该下界评估了9种启发式算法的性能，确认LPT-后优化算法在大规模实例上仍然保持低误差。
import numpy as np from ortools.linear_solver import pywraplp import heapq class MixedMachineScheduling: def __init__(self, job_times, maint_tool_change, maint_period): self.jobs = job_times self.tool_maint = maint_tool_change self.periodic = maint_period def lpt_heuristic(self): jobs_sorted = sorted(self.jobs, reverse=True) machines = [[0.0, []] for _ in range(2)] # [completion_time, job_list] for job in jobs_sorted: # 选择最早可用的机器，考虑维护 avail_times = [] for m in range(2): last_time = machines[m][0] if m == 0: # 需要工具更换 # 检查是否需要维护 if last_time >= self.tool_maint: last_time = max(last_time, last_time + 5.0) # 维护时长 else: # 周期维护 if last_time > 0 and last_time % self.periodic < 1.0: last_time = max(last_time, last_time + 4.0) avail_times.append(last_time) best_m = np.argmin(avail_times) start = avail_times[best_m] machines[best_m][0] = start + job machines[best_m][1].append(job) makespan = max(machines[0][0], machines[1][0]) return makespan, machines def water_transfer_lower_bound(self): total_load = sum(self.jobs) # 平衡分配下界 LB1 = max(max(self.jobs), total_load/2) # 维护损失下界 n_periods = int(np.ceil(total_load / 200)) # 假设维护间隔200 total_maint = n_periods * (self.tool_maint + self.periodic)/2 LB2 = (total_load + total_maint) / 2 return max(LB1, LB2) def three_partition_reduction(): # 简化归约证明示例 return 'NP-hard by reduction from 3-PARTITION' if __name__ == '__main__': np.random.seed(42) jobs = np.random.randint(1, 100, 200) scheduler = MixedMachineScheduling(jobs, tool_maint=45.0, periodic=120.0) ms, mach = scheduler.lpt_heuristic() print('LPT makespan:', ms) lb = scheduler.water_transfer_lower_bound() print('Lower bound:', lb) print('Optimality gap (approx):', (ms - lb)/lb * 100, '%') # 整数规划模型小实例 small_jobs = [15, 27, 33, 42, 18, 9] solver = pywraplp.Solver.CreateSolver('SCIP') if solver: x = {} for i in range(len(small_jobs)): for m in range(2): x[i,m] = solver.IntVar(0, 1, 'x[%i,%i]' % (i,m)) # 简化约束 for i in range(len(small_jobs)): solver.Add(x[i,0] + x[i,1] == 1) C_max = solver.NumVar(0, 1000, 'makespan') solver.Add(C_max >= sum(small_jobs[i]*x[i,0] for i in range(len(small_jobs))) + 20) solver.Add(C_max >= sum(small_jobs[i]*x[i,1] for i in range(len(small_jobs))) + 15) solver.Minimize(C_max) status = solver.Solve() if status == pywraplp.Solver.OPTIMAL: print('IP optimal makespan:', solver.Objective().Value()) # 最坏情况界演示 worst_inst = [100, 99, 1, 1] sch_worst = MixedMachineScheduling(worst_inst, 50, 100) ms_worst, _ = sch_worst.lpt_heuristic() lb_worst = max(max(worst_inst), sum(worst_inst)/2) print('Worst-case ratio:', ms_worst/lb_worst)
