粒子群优化PSO+禁忌搜索TS组合模型案例 半导体车间设备调度 数学建模竞赛题目+Python源代码

粒子群优化（PSO）+禁忌搜索（TS）组合模型案例题目题目：半导体车间多设备协同调度问题问题背景：某半导体工厂的芯片封装车间有10台不同型号的封装设备，需处理80批不同规格的芯片（每批数量500-2000片）。芯片封装需经过“固晶-焊线-塑封-切筋”4道工序，不同设备的工序加工效率差异显著，且设备切换规格时需停机调试（耗时30-60分钟）。当前调度方案导致设备闲置率达25%，订单平均延期率18%。问题描述：需优化各批次芯片在设备间的加工顺序和时间分配，目标包括：①最小化总生产周期（≤72小时）；②最大化设备利用率；③最小化订单延期时间（重要订单延期罚款是普通订单的3倍）。约束条件：每道工序必须按顺序执行，某设备同一时间只能处理一批芯片，部分精密设备每日需预留2小时维护时间。数据情况：提供各批次芯片的工序需求（如A批次需在设备1完成固晶、设备5完成焊线）、各设备的工序加工速率（片/分钟）、设备切换规格的调试时间矩阵、各订单的交货截止时间及优先级标签、设备每日可用时间窗口。2.粒子群优化（PSO）+禁忌搜索（TS）求解半导体车间调度代码importnumpyasnpimportrandomimportmatplotlib.pyplotasplt#数据初始化np.random.seed(42)n_jobs=80#80批芯片n_machines=10#10台设备n_stages=4#4道工序#每批芯片的工序需求（每道工序对应一台设备）processing_machines=np.random.randint(0,n_machines,size=(n_jobs,n_stages))#每台设备的工序加工速率（片/分钟）process_rate=np.random.uniform(50,200,size=(n_machines,n_stages))#设备切换规格的调试时间（分钟）setup_time=np.random.randint(30,61,size=(n_machines,n_jobs,n_jobs))#订单截止时间（小时）due_dates=np.random.uniform(24,72,size=n_jobs)#订单优先级（1-3，3为最高）priority=np.random.randint(1,4,size=n_jobs)#每批数量（片）batch_sizes=np.random.randint(500,2001,size=n_jobs)#计算加工时间（分钟）processing_time=np.zeros((n_jobs,n_stages))forjinrange(n_jobs):forsinrange(n_stages):machine=processing_machines[j,s]processing_time[j,s]=batch_sizes[j]/process_rate[machine,s]#PSO参数n_particles=30max_iter=100w=0.8#惯性权重c1,c2=0.5,0.5#学习因子#禁忌搜索参数tabu_size=20tabu_list=[]#粒子表示：每个粒子是作业的加工顺序definit_particles(n_particles,n_jobs):particles=[]for_inrange(n_particles):particles.append(random.sample(range(n_jobs),n_jobs))returnnp.array(particles)#计算makespan（总生产周期）defcalculate_makespan(sequence):#设备上的完工时间machine_end=np.zeros((n_machines,n_stages))#作业的工序完工时间job_end=np.zeros((n_jobs,n_stages))forjobinsequence:forstageinrange(n_stages):machine=processing_machines[job,stage]#前道工序完工时间prev_stage_end=job_end[job,stage-1]ifstage>0else0#设备空闲时间machine_idle=machine_end[machine,stage]start_time=max(prev_stage_end,machine_idle)#如果是同一设备上的前一个作业，需加切换时间ifstage==0:#第一道工序看设备上一个作业prev_job=Noneforjinsequence:ifj==job:breakifprocessing_machines[j,0]==machine:prev_job=jifprev_jobisnotNone:start_time+=setup_time[machine,prev_job,job]job_end[job,stage]=start_time+processing_time[job,stage]machine_end[machine,stage]=job_end[job,stage]returnnp.max(job_end)#计算延期时间defcalculate_tardiness(sequence):makespan=calculate_makespan(sequence)tardiness=0forjobinsequence:t=max(0,makespan/60-due_dates[job])#转换为小时tardiness+=t*priority[job]#优先级加权returntardiness#适应度函数（最小化makespan和延期时间）deffitness(sequence):makespan=calculate_makespan(sequence)tardiness=calculate_tardiness(sequence)#设备利用率（1-空闲时间占比）machine_util=1-(np.sum(machine_end)-np.sum(processing_time))/np.sum(machine_end)return1/(makespan+tardiness*60-machine_util*1000)#60转换为分钟#禁忌搜索局部优化deftabu_search(best_seq,fitness_func):current_seq=best_seq.copy()current_fit=fitness_func(current_seq)best_tabu_seq=current_seqbest_tabu_fit=current_fitfor_inrange(50):#邻域搜索次数#生成邻域解（交换两个作业）a,b=random.sample(range(len(current_seq)),2)new_seq=current_seq.copy()new_seq[a],new_seq[b]=new_seq[b],new_seq[a]#检查禁忌表iftuple(new_seq)intabu_list:continuenew_fit=fitness_func(new_seq)ifnew_fit>best_tabu_fit:best_tabu_seq=new_seqbest_tabu_fit=new_fitcurrent_seq=new_seqcurrent_fit=new_fit#更新禁忌表tabu_list.append(tuple(new_seq))iflen(tabu_list)>tabu_size:tabu_list.pop(0)else:#藐视准则：如果解更优则接受ifnew_fit>current_fit:current_seq=new_seqcurrent_fit=new_fitreturnbest_tabu_seq,best_tabu_fit#PSO主算法defpso_ts_optimize():particles=init_particles(n_particles,n_jobs)velocities=[random.sample(range(n_jobs),n_jobs)for_inrange(n_particles)]#速度表示交换位置pbest=particles.copy()pbest_fitness=[fitness(seq)forseqinparticles]gbest_idx=np.argmax(pbest_fitness)gbest=pbest[gbest_idx].copy()gbest_fitness=pbest_fitness[gbest_idx]#禁忌搜索优化全局最优gbest,gbest_fitness=tabu_search(gbest,fitness)foriterinrange(max_iter):foriinrange(n_particles):#更新速度（粒子群优化的离散化处理）#1.向个体最优学习pbest_diff=[idxforidx,(a,b)inenumerate(zip(particles[i],pbest[i]))ifa!=b]#2.向全局最优学习gbest_diff=[idxforidx,(a,b)inenumerate(zip(particles[i],gbest))ifa!=b]#生成新速度（合并差异并抽样）new_vel=pbest_diff[:int(c1*len(pbest_diff))]+gbest_diff[:int(c2*len(gbest_diff))]new_vel=list(set(new_vel))#去重iflen(new_vel)<2:new_vel+=random.sample(range(n_jobs),2-len(new_vel))random.shuffle(new_vel)#更新位置（根据速度进行交换）new_seq=particles[i].copy()forkinrange(0,len(new_vel)-1,2):ifk+1<len(new_vel):a,b=new_vel[k],new_vel[k+1]new_seq[a],new_seq[b]=new_seq[b],new_seq[a]particles[i]=new_seq#评估适应度current_fit=fitness(new_seq)#更新个体最优ifcurrent_fit>pbest_fitness[i]:pbest[i]=new_seq.copy()pbest_fitness[i]=current_fit#更新全局最优ifcurrent_fit>gbest_fitness:gbest=new_seq.copy()gbest_fitness=current_fit#禁忌搜索优化新的全局最优gbest,gbest_fitness=tabu_search(gbest,fitness)ifiter%10==0:print(f"迭代{iter},最优适应度:{gbest_fitness:.4f}")returngbest,gbest_fitness#运行算法best_sequence,best_fit=pso_ts_opti