基于matlab的GA优化算法优化车间调度问题。 n个工作在m个台机器上加工。 已知每个工作中工序加工顺序、各工序的加工时间以及每个工件所包含的工序在满足约束条件的前提下目的是确定机器上各工件顺序以保证某项性能指标最优。 程序功能说明共4个工件每个工件3个工序6台机器给出了每个工件的各工序能使用的机器序号矩阵Jm求解最优调度方案的加工时间。 程序已调通可直接运行。车间调度问题这玩意儿真是让人又爱又恨——特别是当工序数量蹭蹭往上涨的时候。今天咱们用Matlab的遗传算法GA来收拾这个烂摊子看看怎么把四个工件的加工时间压到最短。先剧透个重点工序顺序和机器选择的双重组合会产生爆炸式的解空间手动试算绝对会让人头秃。先看问题设定4个工件各含3道工序总共有6台机器可用。每个工序能选的机器都不同比如工件1的第一道工序可能只能在机器3和5里选。这个信息存在Jm矩阵里这货长这样Jm [3 5; 2 4 6; 1 3 5; 2 4];矩阵行号代表工件序号每行元素是该工件各工序可用的机器编号。比如第二行2 4 6表示工件2的每个工序分别能用机器2、4、6不过这里要注意实际数据可能更复杂。适应度函数是算法核心咱们得把染色体解码成实际加工时间。这段代码有点意思function makespan decode(chromo, Jm, pt) [num_jobs, ~] size(Jm); machine_timeline zeros(1,6); % 6台机器的当前时间 job_progress ones(1,num_jobs); % 各工件已完成的工序数 for gene chromo job gene; op_step job_progress(job); avail_machines Jm{job}(op_step,:); % 当前工序可用机器 [~, idx] min(machine_timeline(avail_machines)); % 选最早空闲的机器 selected_machine avail_machines(idx); start_time machine_timeline(selected_machine); proc_time pt{job}(op_step); end_time start_time proc_time; machine_timeline(selected_machine) end_time; job_progress(job) job_progress(job) 1; end makespan max(machine_timeline); end这里用了个贪心策略每次给当前工序分配最早空闲的可用机器。注意Jm和pt都用到了cell数组因为不同工序的可用机器数量不一致。比如pt{2}(3)就是工件2第3道工序的加工时间。基于matlab的GA优化算法优化车间调度问题。 n个工作在m个台机器上加工。 已知每个工作中工序加工顺序、各工序的加工时间以及每个工件所包含的工序在满足约束条件的前提下目的是确定机器上各工件顺序以保证某项性能指标最优。 程序功能说明共4个工件每个工件3个工序6台机器给出了每个工件的各工序能使用的机器序号矩阵Jm求解最优调度方案的加工时间。 程序已调通可直接运行。交叉操作采用OX交叉比普通交叉更适合工序序列问题。重点在于保留父代工序顺序function child crossover(p1, p2) len length(p1); cut1 randi([1,len-1]); cut2 randi([cut11,len]); segment p1(cut1:cut2); remaining p2(~ismember(p2, segment)); child [remaining(1:cut1-1), segment, remaining(cut1:end)]; end比如父代p1[2,4,1,3], p2[3,1,4,2]随机切取中间两个元素得到segment[4,1]然后把p2中不在segment里的元素按顺序填充到前后最终子代可能是[3,4,1,2]。跑完算法输出甘特图时会发现有些机器的工作间隙——这说明可能存在机器竞争导致的等待时间。下图是某次运行结果机器1: [工件3: 0~5] 机器2: [工件4: 0~3] [工件2: 3~7] 机器3: [工件1: 0~4] [工件3: 5~9] ... 最大完工时间: 12小时这个结果表示通过GA找到了12小时的最优解。不过要注意每次运行结果可能不同可以尝试把种群大小从50调到100增加收敛到全局最优的概率。代码里有个隐藏技巧在初始化种群时用了工序约束校验。比如工件必须完成前道工序才能进行后续操作这部分通过染色体编码天然保证——染色体是工件编号的排列每个编号出现次数等于该工件的工序数。例如[1,3,2,1,...]表示先安排工件1的第1工序再工件3的第1工序以此类推。最后说个坑变异概率别超过0.2否则算法容易变成随机搜索。实测当变异概率从0.1升到0.3时收敛代数从15代暴增到50代但最终结果可能反而更差。下次可以试试结合模拟退火的变异策略说不定有惊喜。