《数学建模与计算》生产调度问题—遗传算法背景及摘要这是一个典型的Job-Shop动态排序问题。
目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。
一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序，而且工序的变更又可能导致相当大的调度规模。
解空间容量巨大，N个工件、M台机器的问题包含M(N)!种排列。
由于问题的连环嵌套性，使得用图解方法也变得不切实际。
传统的运筹学方法，即便在单目标优化的静态调度问题中也难以有效应用。
本文给出三个模型。
首先通过贪婪法手工求得本问题最优解，既而通过编解码程序随机模拟优化方案得出最优解。
最后采用现代进化算法中有代表性发展优势的遗传算法。
文章有针对性地选取遗传算法关键环节的适宜方法，采用MATLAB 软件实现算法模拟，得出优化方案，并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。
对车间调度系列问题的有效解决具有一定参考和借鉴价值。
一．问题重述某重型机械厂产品都是单件性的，其中有一车间共有A，B，C，D四种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加工，其工序与加工周期如下表：（S-设备号、T-周期）( 表一 )条件：1、每件产品必须按规定的工序加工，不得颠倒； 2、每台设备在同一时间只能担任一项任务。
（每件产品的每个工序为一个任务）问题：做出生产安排，希望在尽可能短的时间里，完成所接受的全部任务。
要求：给出每台设备承担任务的时间表。
注：在上面，机器 A ，B ，C ，D 即为机器 1，2，3，4，程序中以数字1，2，3，4表示，说明时则用A ，B ，C ，D二．模型假设1．每一时刻，每台机器只能加工一个工件，且每个工件只能被一台机器所加工 ，同时加工过程为不间断；2．所有机器均同时开工，且工件从机器I 到机器J 的转移过程时间损耗不计； 3．各工件必须按工艺路线以指定的次序在机器上加工多次；4．操作允许等待，即前一操作未完成，则后面的操作需要等待，可用资源有限。
三．符号说明及初始数据表达分析i J - 第i 个工件 （i=1…6）M J - 机器顺序阵 ）（j i J M,表示i 工件的第 j 个操作的机器号j M - 第j 台机器 （j=1…4）J M - 工件排列阵 ),(j i M J 表示i 机器上第j 次加工的工件号T - 加工时间阵 ),(j i T 为i 工件的第 j 个操作的时间周期C - 整个任务完成时间整理数据后得到：J=[ C A B C D 0 0 0 ] T= [ 8 2 4 24 6 0 0 0 ] M[ A D B C 0 0 0 0 ] [ 4 5 3 4 0 0 0 0 ] [ C D A B A 0 0 0 ] [ 3 7 15 20 8 0 0 0 ] [ B C D A D C 0 0 ] [ 7 6 21 1 16 3 0 0 ] [ D B C D A C D 0 ] [ 10 4 8 4 12 6 1 0 ] [ A B A C D A C A ] [ 1 4 7 3 5 2 5 8 ] 上述二阵直接从题目得出，而M则是我们要求的。
J关于工件的加工时间表：(表二)关于机器的加工时间表：(表三)分析：由于各产品总净加工时间和各机器总净加工时间之中最大值为 75，而总计为247，那么总时间 C 介于[75，247]。
同时各工件加工繁杂程度不一，各机器的任务量也有轻重之别。
合理的调度排序是对于节省时间和资源是必要的。
希望最优化答案是75，这样达到最小值，如果答案是75，那么意味着机器D 不间断工作,直至全部加工任务完成。
六．遗传算法模型建立和步骤解法遗传算法（Genetic Algorithm）作为一种优化算法特别适合于对象模型难于建立、搜索空间非常庞大的复杂问题的优化求解。
它和模糊控制技术一样，虽然在理论上还没有完善，但是在实践中已经得到了广泛的应用。
遗传算法的基本思想是：模仿生物系统“适者生成"的原理，通过选择、复制、交叉、变异等简单操作的多次重复来达到去劣存优的目的，从而获得问题的优化结果。
遗传算法的实现由两个部分组成，一是编码与解码，二是遗传操作。
其中遗传操作又包括选择、复制、交叉、变异等步骤。
本文根据实际情况采取了1-6整数编码。
数字1，2，3，4，5，6分别代表6件待加工产品。
本文遗传算法基本流程:通过编码，解码程序随机产生N 个（有一定数量,如50或100）个体构成初始种群a) 从初始中群中选取2个具有最优染色体（最有排序方案）的个体作为临时个体（父代）；b) 如果此2个体中有一个个体通过解码操作能够实现最优排序（即使总时间为75周期），那么结束此算法，得到最优解；c) 对2个临时个体以一定方式(循环交叉)执行染色体交叉变换和变异选择（小概率,互换操作），产生2个新的个体；d) 对父代和子代共4个个体进行选择，从中选出最佳的2个个体，做为下一代的父代；e) 重复执行第二步(b)操作；f) 如果执行完M 步后仍然未得出答案75，那么将目前的最优解作为本算法的最优解答案。
1．编码随机产生生产的工序操作优先顺序，进行编码，如：K=[ 4 3 5 6 6 2 3 1 41 6 3 5 4 5 3 6 6 4 1 5 5 1 32 6 2 2 4 4 1 5 6 6 5 ] （注：同时作为下文的染色体之用） 意思为：工件4优先被考虑进行第一次操作，然后3进行其第一步操作，然后5操作，6操作，再6操作其第二步工序，依次进行。
如果前后互相不冲突，则可同时在不同机器上操作。
通过排列组合得出，总共有类似K 的排列序列 22310 多种！当然，这其中只对应解 [75，247]，意味着有大量排列序列对应同一加工方案，而大量加工方案又对应同一时间解。
2．解码即对编码进行翻译，产生具体可操作工序安排方案，这里采用活动化解码算法。
例如工件2第i步操作（记为J（2，i），且在机器A上进行）被安排在M工件3第j步操作（记为JM（3,j））后面进行，那么如果安排好JM （3,j）后，只要J（2，i）在工件2已经排序好的操作之后进行，那么操M作J（2，i）可插入到机器A处最前可安置的时间段进行。
M在这里，一个编码序列对应一个加工方案，而一个加工方案可对应一个或多个编码序列，这就是二者之关系。
3．交叉变换(crossover)对2个父代临时个体进行染色体交叉变换，采用循环交叉方法（Cycle crossover CX），如父代染色体为：X：[9 2 6 4 7 3 5 8 1]和Y：[3 4 5 8 1 6 7 2 9]，如果随机选到第二位开始交叉，那么X的2对应Y的4，X的4对应Y的8，X的8对应Y的2，这样就确定了以上为不变的染色体，其余位置的染色体互换位置，最后得到X': [3 2 5 4 1 6 7 8 9], Y': [9 4 6 8 7 3 5 2 1],实现交叉变换。
4．变异选择（mutation）采用互换操作（SWAP），，即随机交换染色体中两不同基因的位置。
如上面的染色体为：X': [3 2 5 4 1 6 7 8 9] 。
随机产生变换位置号，如产生随机数3和5，那么交换数字后得到染色体： [3 2 1 4 5 6 7 8 9]，变异概率取0.1 。
5．选择操作（selection）对父代2个体f1,f2和子代2个体f3,f4进行选择，通过编码操作确定具有最优解的2个个体，成为新一代f1和f2 。
如此，通过多次编码和解码随机产生一定数量的个体，选取2个最佳个体进行交叉变换操作，产生2个新个体，然后对4个个体进行选择，产生下一代，如果某时刻通过解码操作得出最优解（所有解的下限，这里是75周期），那么算法结束，否则循环进行，直至预先给定的循环次数达到为止，以最后得到的最优解作为最终最优解。
七．遗传算法模拟（采用MATLAB工具编程）主程序如下：（子程序见略）% 本程序为主程序，调用以下各分支程序task= 'Welcome! Wait a moment please! --- Writer: 孙卓明 ,信息 014',f1=zeros(1,35);f2=zeros(1,35);while f1==f2; % 此步避免初始染色体 f1,f2 相同，导致以下死循环 [minminmax1,s1]=chushijie(N); % 种群初始化；基于操作的编码策略；活动化解码算法;chushijie(N) 参数 N 为初始种群数f1=s1 ; minminmax1, % 选取的第一个初始个体[minminmax2,s2]=chushijie(N); % 再次种群初始化f2=s2 ; minminmax2, % 选取的第二个初始个体end;for e=1:M; % e=1:M 进行 M 次遗传操作（交叉-变异-选择)[D]=jiaocha(f1,f2); % 交叉变化（循环交叉操作，cycle crossover CX）,选取f1; f2; “染色体”无需变动部分基因[f3,f4]=jiaocha_bianyi(f1,f2,D); % 生成交叉后的“染色体”,并进行变异选择f3; f4;[f1,f2]=xuanze(f1,f2,f3,f4); % 选择：对父代f1,f2和子代f3,f4进行解码，得出2个f1; f2; 较优个体，成为下一代的父代[minmaxf1,a1,b1]=tongbujinzhan(f1); % 求该时刻个体f1的最优时间(因为f1优于f2)if minmaxf1==75;f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1,task='Finish! Successful! Best answer! Congratulation! ' , return ;end; end;f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1,if minminmax_last>=90; task='Finish! Action again please!',end;if minminmax_last>=80&&minminmax_last<90; task='Finish!' , end;if minminmax_last<80; task='Finish! Successful!', end;八．遗传算法模拟结果首先给出最优方案:在进行某次n=100,m=200的操作后得到模拟最优结果75周期时间：minminmax1 =83 minminmax2 =78 （二个初始较优个体解）f1 =[4 5 6 6 3 1 3 6 4 5 6 1 3 2 5 4 5 3 1 5 2 6 4 5 6 4 6 6 4 3 2 2 5 1 1]（f1为各工件优先选择顺序排列,即“染色体”）a1 = 5 35 39 64 0 0 0 0 0 （a1,b1为四台机器空闲周期段）15 24 0 0 0 0 0 0 017 53 65 0 0 0 0 0 00 0 0 0 0 0 0 0 0b1 =11 38 42 65 0 0 0 0 020 35 0 0 0 0 0 0 018 54 68 0 0 0 0 0 00 0 0 0 0 0 0 0 0minminmax = 75 （最终最优解）其中机器A空闲时间段为:5-11,35-38,39-42,64-65; 机器B则为:15-20,24-35; 机器C为:17-18,53-54,65-68;机器D无空闲。