最优加工排序问题

1、EAST CHINA INSTITUTE OF TECHNOLOGY数学建模暑期培训第四次论文论文题目：加工任务的最优调度方案研究姓名：卢丰海 学号：09102126专业：信息与计算科学姓名： 曾洁 学号：09032104专业：环境工程2011年7月19日加工任务的最优调度方案研究摘要本文采用排序理论中的思想及方法来编制印刷厂的作业计划，依据题目要 求，建立了任务完工时间的递推模型，求解出较优的印刷厂调度方案。针对问题一，本文首先分别用Palmer启发式算法、CDS启发式算法确定任 务在车间的加工顺序；再以最长流程时间Fmax最短为目标函数，建立任务完工时 间的递推模型；在求得两种排列顺序的基

2、础上，用Matlab编程分别求解出各个 任务在不同车间的完工时间：其中用Palmer算法完成前6项任务所需58天，完 成20项任务需170天；用CDS算法完成前6项任务所需57天，完成20项任务 需157天。故本文取CDS算法所得的排序结果来编制调度方案。前6项任务的 调度方案见表3, 20项任务的具调度方案见表4。问题二是求解目标函数为120天内能完工的最大任务数的排列排序问题。对 于此问的求解，本文首先将耗时较长的任务按耗时量的大小排序，再将这些任务 按从大到小逐个剔除，在依次剔除了 12、13、17并再重新排序后，观察所得的 最大完工时间为117天，刚好小于120天，故求解出120天内能

3、完工的最大任务 数为 17。17 项任务的加工工序为 8-14-3-19-5-2-11-16-18-10-1-4-7-20-13-6-9，具 体调度方案见表5。针对问题三，本文根据题目所给限制条件，运用逐步筛选法求出放假后完成 所有任务的最少天数。当各个车间放2天假时，运用matlab编程（程序见附录） 求解得完成所有任务的天数为159天且方案不唯一，其中一种方案的任务加工顺 序为：8-14-3-5-10-19-2-17-15-12-11-16-18-1-4-7-20-13-9-6。同理可得当在第 50 天到第60天之间连续放3天假时，求解完成所有任务的天数为160天，任务的 加工工序与放2天

4、假的加工顺序一致，只是完工时间在放两天假的基础上往后挪 一天。具体调度方案见下表：车间印刷车间装订车间打包车间放1时假 2天间安排的第54、 55天第55、 56天第53、 54天放1时假 3天间安排的第 54、 55、 56 天第 55、 56、 57 天第 53、 54、 55 天关键词：逐步筛选法；CDS启发式算法；加工排序；调度方案；最小完工时间1问题的重述一、问题背景某印刷厂共有3个车间，分别为印刷车间、装订车间和打包车间。每一项任 务必须依次经过印刷车间、装订车间和打包车间。由于技术原因，每一项任务在 该车间完成该任务的全部加工后才可进入下一个车间；任务在一个车间完成后， 可以间隔

5、若十天进入下个车间，也可以连续依次进行；不同的任务不能同时共享 同一车间；一旦某项任务进入某一车间，该任务就必须连续被执行，不允许被其 它任务或事件打断。该印刷厂各车间目前均处于空闲状态，没有任务需要加工。印刷车间将来开 工的那天记为第1天。二、需解决的问题问题一：现接到6项加工任务，试设计一个加工方案使得完成这6项任务总 共需要的天数尽量少；当6项任务还没有下达到车间，现又接到14项加工任务， 试设计一个加工方案使得完成这20项任务总共需要的天数尽量少。各项任务对 各车间所需的时间（单位为：天）如表1所示。表1任务编号 车间71234567891011121314151617181920印刷

6、车间3105691152381116321310111565装订车间8129652632615162615913583打包车间215531012617916251781510102问题二：对于问题2中所考虑的20个任务，请设计一个加工方案使得尽量 多的任务在120天内（含第120天）完成加工。问题三：为了工人的健康，印刷厂工会决定从第50天到第60天的时间里每 个车间放假2天，并且必须是放连续的2天假，每个车间的放假起止时间可以不 一样。如果每个车间是放连续3天的假，为了尽量把放假对印刷厂的生产进度造 成的影响降到最低，请分别制定一个包含每个车间放假方案的任务加工方案，使 得完成问题1中的这2

7、0项任务总共需要的天数尽量少。附加题（选做）.由于数据录入有错误，经核对，任务6、7、8、9、13和 16对三个车间所需要的时间应为表3所示，其余任务的数据没有错误。试用你 们在求解上述问题中所使用的方法、算法或模型对经过数据核对和更正后的这 20项任务进行重新求解（对核对后和更正后的20项任务的数据重新求解上述问 题）。表2任爰编号 车间67891316印刷车间252335装订车间11161318715打包车间112101128注：一个完整的加工方案应包括每-项任务在各个车间中的开始加工时间和完成时间。2问题的分析印刷厂任务的最优调度是一个大规模的优化调度问题，第一个任务合格的生 产计划，依

8、题意应满足以下几点基本要求：1、不同的任务不能同时共享同一车间；2、每一项任务必须依次经过印刷车间、装订车间和打包车间；3、每一项任务在该车间完成该任务的全部加工后才可进入下一个车间；4、任务在一个车间完成后，可以间隔若十天进入下个车间，也可以连续依 次进行；5、某项任务进入某一车间，该任务就必须连续被执行，不允许被其它任务 或事件打断。一、对问题的具体分析1、对问题一的分析问题要求利用表1及表2的数据，设计一个加工方案使印刷厂完成所接到的 所有任务需要的天数尽量少。经分析，本问是典型的排列排序问题，目标函数是使完成所有任务的最长流 程时间最短。故应将给的所有任务按一定的方法进行排序，便可得到

9、任务先后处 理的较优顺序。再将所得的顺序依据上述要求按如下思路进行递推，即会得到完 成所有任务的较少天数。本文以加工前6项任务为例：（具体每项任务的加工时 间见表一）假设s= 1,2,3,4,5,6为所求的最优排列顺序，首先将每个工件的完工时间 标在其加工时间的后面，对于第一行第1列，只需把加工时间的数值作为完工时 间标在加工时间的后面。对于第一行的其它元素，只需从左到右依次将前一列后 面的数字加上计算列的加工时间，将结果填在计算列加工时间的后面。对于从第 二行到第三行，与第一列的算法相同，只要把上一行后面的数字和本行的加工时 间相加，将结果填在本行加工时间的后面；从第2列到第6列，则要从本行

10、前 一列后面数字和本列上一行后面数字中取大者，再和本列加工时间相加，将结果 填在本列加工时间的后面。这样计算下去，最后一行最后一列的后面数字，即为 完成所有任务所需的较少天数。依照上述思想，建立递推模型，并用Matlab编程，再将之前所得的较优排序 输入求解，即可得到每一项任务在各个车间中的完成时间，再结合原有表1中的 数据得到每一项任务在各个车间中的起始时间，最终便得到6项任务的优化调度 方案。同理可求解出20项任务的优化调度方案。2、对问题二的分析问题要求考虑问题1中的20个任务，请设计一个加工方案使得尽量多的任 务在120天内（含第120天）完成加工。经分析，本问是求解目标函数为120天

11、内能完工的任务数量最大的排列排序 问题。观察到表1所列的20项任务，发现其中某些任务在各个车间的完工时间 较长，故猜想去除部分这些任务后重新排序所得的结果是比较理想的。具体操作 如下：本文先在第一问求解的排序结果上，将随机淘汰一些任务所得到的最大完 工时间与淘汰一些耗时较长的任务所得到的结果相比较。再将耗时较长的任务按 耗时量的大小排序，将这些任务按从大到小逐个剔除，每剔除一个观察所得的最大完工时间是否超出120天，直到刚好不超过为止，则所剩的任务数则为最少任 务数。3、对问题三的分析由于一旦某项任务进入某一车间，该任务就必须连续被执行，不允许被其它 任务或事件打断，所以要放假必须是车间某项任

12、务完成后或者还没开始前就放 假。又由于题目中说明印刷厂工会讨论决定从第50天到第60天这个长度为11 天的时间里每个车间连续放假2 （或3）天。所以可知放假时间应该是在车间工 作到第50天就可以开始，第60天放假结束，即有放假起始时间在第50至第58 （或第57）天之间，结束时间应在第52 （或第53）至第60天之间。当各车间 均有完成任务时间在5058 （或5057）之间时，就可以安排连续2天（或3） 的放假，排定后便可求出完成20个任务所需天最少天数。3模型的假设1、假设只对所给数据进行分析和排定；2、假设所有数据均为原始数据，来源真实可靠；3、假设只要求得近优解便可认为该排定方案可行；4

13、、假设可以忽略由算法本身缺陷带来的较小误差；5、假设任务排定后均能按时按序在规定时间内完成;6、假设忽略其他能对任务完工时间产生影响的因素;序号符号1n2m3P4Fmax5Cmax6九i7si8Mk9t10院cs*11Pi,12jT13U4符号说明符号说明表示需完成的任务数表示加工完任务所需的工序数表示流水作业排列排序问题表示排在末位加工的任务在车间的停留时间表示一批任务的最长完工时间表示工件，的斜度指标（slope index）表示排第，位加工的任务的代号表示第k个车间表示任务在车间Mk上的加工时间表示任务S.在车间Mk上的完工时间表示任务顺序排序后可得第i个车间完成第j个任务所需时间表示放

14、假后完成所有任务所需的最少天数表示放假后不同工序完成不成任务的完成时间5模型的建立与求解从所要解决的的问题和对问题所做的假设出发，我们对问题一建立了模型I,对问题二建立了模型II和模型III,对问题三建立了模型w。一、问题一模型的建立及求解1、对问题一的分析本问所讨论的是n ImlP /F问题。其中n为需完成的任务数；m为加工完任务所需的工序数；P则表示流水作业排列排序问题；目标函数是使最长流程时 间最短，即求解F 。最长流程时间又称作加工周期，它是从第一个任务在第一 个车间开始加工时算起，到最后一个任务在最后一台机器上完成加工时为止所经 过的时间。由于假设所有任务的到达时间都为零(尸.=0

15、,i=1,2. n),所以F 等于排在末位加工的任务在车间的停留时间，也等于一批任务的最长完工时间” max。经分析，对本问题本处理要分两个步骤进行：第一，寻找较好的算法给所有 的任务进行排序，得到任务处理的较优顺序；第二，将第一步骤所得的排序结果 按递推思想求解出排在末位加工的任务在车间的停留时间，并确定相应的加工方 案。2、两种启发式算法的排序结果(一)Palmer启发式算法Palmer启发式算法是基于工件的加工时间按斜度顺序指标(slope order index )排列工件的算法，其基本思想是给每个工件赋优先权数。具体操作如下: 按机器的顺序，加工时间趋于增加的工件得到较大的优先数；与

16、此相反，按机器 的顺序，加工时间趋于减少的工件得到较小的优先数。工件.的斜度指标(slope index) X.按下式计算：人= (2 j - m - 1)t , i = 1, 2, , n( 1)j=i按照各工件x.不增的顺序排列工件，可得出令人满意的顺序。本文用Palmer启发式算法得到前6项任务的加工工序为= 2,5,1,6,3,4； 20 项任务的加工工序为 s2= 2,19,17,15,8,14,5,12,3,13,10,1,16,11,9,20,7,4,18,6。(二)CDS启发式算法该法把Johnson算法用于一般的n / ml P / F 问题，得到m -1个加工顺序， 取其中

17、优者。算法首先把m台机器系统地组成两组，产生m -1个两台机器问题 的集合，然后利用Johnson的两台机器算法得到m -1个加工顺序，最后选择其 中最好的一个作为近似最优解。具体做法是先定义a. = Z t ,0. = Z t , i = 1, 2,，m 1; j = 1, 2,，n(2)k=1k=1依次令i=1,2,.,m-1可以得到m-1组a和们对i的每一个取值，把a.和及 看成作业J.分别在两台机器处理上的加工时间，利用Johnson算法可以求得一个 排序，共可以得到m-1个排序，取其中目标函数最小值。本文用CDS启发式算法得到前6项任务的加工工序为s3=3,5,2,4,1,6;20项

18、 任务的加工工序为 s4= 8,14,5,3,19,2,17,15,12,11,16,18,10,1,4,7,20,13,9,6。对比以上两种算法可知，CDS算法的求解结果更优，故本文选择CDS算法来对任务进行排序。3、模型一的建立设n个任务的加工顺序为 s= s,s2，,sn 的代口 加工时间，号。c表示任务s.在车间Mk上的完工时间, s-ki = 1,2,，n； k = 1,2,m，贝Ucs,k其中s.为排第i位加工的任务 t表示任务s.在车间Mk上的 可按以下公式计算：1 11+ t , k = 2,，m s1 k(3)=c + t1si-1 1=max s ，ck si，k-1s i

19、-1,i = 2,，n1+ t , i = 2,n, k = 2,mSi(4)(5)i =1,2,，n时，最大流程时间为Fmax(6)当由式（4）得出c时,Fmax就可求得。smn4、模型一的求解本文先将用上述两种启发式算法所求得的排列顺序按模型一的思想用 Matlab编程实现，其中用Palmer启发式算法排序所得的任务完成最少天数是： 完成前6项任务所需58天，而完成20项任务需170天；用CDS启发式算法排 序所得的任务完成最少天数是：完成前6项任务所需57天，而完成20项任务需 157天。由此看来，CDS启发式的排序算法结果更优于Palmer启发式算法的排 序结果，故本文取较优解。以下是

20、运用CDS算法的排序结果所得的较优调度方 案，其中表3是前6项任务的调度方案，表4为20项任务的调度方案。表3次序印刷车间装订车间打包车间任务开始所需完成开始所需完成开始所需完成编号时间时间时间时间时间时间时间时间时间3155691415519569141551920102921510242512363715511253273784452253428633456505435663411445125257157从上表可知，较优的调度方案的任务执行顺序为s=s3,s5,s2,s4,s1,s6,即s3最 先进入印刷车间，其开始加工时间为第1天，在耗时5天后完成全部印刷，即紧 接着在第6天进入装订车间

21、；而s5在第6天进入装订车间的开始加工，在耗时9 天后完成全部印刷，即在第15天进入装订车间，依此类推可得表4,其如下所 示：表4次序印刷车间装订车间打包车间任务开始所需完成开始所需完成开始所需完成编号时间时间时间时间时间时间时间时间时间8122335661114324661112516355912920215255109182152526103519196242683336104522510343512464715611735114547135962157615461358601574771793125916747516909416109117511859115105110911816861

22、095106911411981261896151101155119127101361011181181206125137714311193121126813314421454122612713461391463148712851321406145149215020133513714631481512152131383140149215015321539141314315121521551155614411 _154155_ 2156157一 1157二、问题二的求解本问是求解目标函数为120天内能完工的任务数最大的排列排序问题。对于 此问的求解，本文在第一问求解的排序结果的基础上，首先将耗时较

23、长的任务按 耗时量的大小排序，将这些任务按从大到小逐个剔除，每剔除一个任务并再重新 排序后，观察所得的最大完工时间是否超出120天，直到刚好不超过为止，则所 剩的任务数即为120天内能完工的最大任务数。本文用上述思想依次剔除了 s12、 s15、s17，求解出120天内能完工的最大任务数为17。为验证上述求解结果的可靠性，本文在第一问求解的排序结果的基础上，将 耗时最大及次大的s12、土数剔除后，用Matlab编程产生随机数，剔除随机选出 的任务，剔除该任务并再重新排序后，观察所得的最大完工时间是否超出120 天。经重复多次上述操作后发现，仅当随机抽取到的任务为s17时，所得的最大 完工时间才

24、未超出120天，故上述所求结果可靠。所求17项任务的加工工序为 c ccc c ccc 该17项任务且体的BS8 sm 七 Lq s5 % 也1 16 只 s10 s1s4、B” S13s6Sq。必【/ I工力尹 I平口 J8，14， 3，1Q，5，2，11，10,18，10，1， 4，/， 20， 13，6，q调度万案见表5。表5次序印刷车间装订车间打包车间任务开始所需完成开始所需完成开始所需完成编号时间时间时间时间时间时间时间时间时间8122335661114324661112516355912920215251910615218282910385169242953339104822510

25、34351246491563113511454715616497216461055629707388016561570715758110901071878796849179717938185892982994826879369810031027885929961041052106209359710531071082109980112113113心14oil溶2 5 oil2 36 oil0471111112 1114 7三、问题三模型的建立与求解由第二问计算结果可知，假设随机产生任务顺序排序后可得第i个车间完成 第j个任务所需时间为P.，则有不同车间完成不同任务所需时间为矩阵P。假设假设U表示

26、第i个车间完成第j个任务的完成时刻，则有不同车间完成 不同任务的完成时刻矩阵U，且有：U.i = P.（7）U = U + P , j = 2, . ,20U = U + P , i = 2,3U j = max U ., U . + P , i = 2,3; j = 2,20由每个车间必须连续放假2天，所以每个车间至少存在一个完成时刻在49 至58之间的数，则有：49 U 58, k = 1,2,., 20s.t49 U 58, n = 1,2,., 20（8）49 U 58, m = 1,2,., 20 3 m假设U表示安排放假后的不同车间完成不同任务的完成时刻矩阵，则有假 设分别存在k、

27、n和m使得U1k、U2n和U3m的值第一次落在4958内，则有： TOC o 1-5 h z U = U + 2（9）U = U+ max2, 2 - max0, U - U（1 ）U = U + max2, 2 - max0, U - U （11）当任务编号j min k,n,m时，联立（7）式和（9）式则可求出U矩阵。因此放假后完成所有任务所需的天数为T：min T=max（ U.），i =1,2,3； j=1,2,20（12）根据上述约束条件进行逐步筛选，找出满足需要的完成时刻矩阵即可得到放假后 完成所有任务所需的最少天数。对此运用Matlab编程（程序见附录）求解可知 当任务排序依次为

28、 8、14、3、5、10、19、2、17、15、12、11、16、18、1、4、7、20、13、9和6时，T值最小且数值为159。因此即有每个车间在都第50天 到第60天内连续放假2天，完成20个任务最少需要159天，其放假时间安排为: 表6车间印刷车间装订车间打包车间放假时间第54天和第55天第55天和第56天第53天和第54天同理可得当在第50天到第60天之间连续放3天假，运用matlab编程（程 序见附录）求解可知当任务排序依次为8、14、3、5、10、19、2、17、15、12、 11、16、18、1、4、7、20、13、9和6时，T值最小且数值为160。因此即有每 个车间在都第50天

29、到第60天内连续放假3天，完成20个任务最少需要160天，其放假时间安排为:表7车间印刷车间装订车间打包车间放假时间第 54、 55、 56 天第 55、 56、 57 天第 53、 54、 55 天6模型的误差分析、检验和进一步讨论一、误差分析在模型I中，由于确定任务的执行顺序有多种算法，而本文选择了两种较为 容易操作的算法来对比。虽然本文所用的CDS启发式算法较优于Palmer启发式 算法，但这并不能说明用该法所求得的调度方案就为全局最优解，只能为较优解， 故会有相应的偏差。二、模型的检验针对模型一，本文通过将所求解得的前6项方案进行分析，由下面所画出的 甘特图可知，所得的方案完全符合任务

30、合格生产的要求，即不存在不同的任务同注：上图中的各色段的长短表示任务在不同车间的加工天数；黄色表示任务在印 刷车间的加工，红色表示任务在装订车间加工，蓝色表示任务在打包车间加工。三、模型的进一步讨论针对模型一，本文可考虑选择多种排序算法进行排序，如分支定界法等，对 排序结果进行比较，取其最优的一个做为最优调度方案加工排序。这样可以增强 模型的说服力和科学性。针对问题三，当对数据量比较大的时候，逐步筛选法操作耗时较多，对此可 以考虑分类求解，即就所有任务根据完成时间长短或完成不同工序耗时差距进行 分类，然后对先每类进行求解，在综合求解，从而达到减少程序运算时间，优化 模型。 7模型的评价与推广一

31、、模型的优缺点1、优点：用CDS启发式算法排序，操作较为简单且所求的结果也比较合理；本文建立的模型与实际紧密联系，充分考虑问题背景的要求，从而使模 型更贴近实际，能为相关排列排序问题的求解提供一定参考；（3）运用数学软件可直接得出较优调度方案，操作简单，可为调度人员分担 繁杂的计算过程。2、缺点：（1）由于未使用更优的排序方法，使得所求结果与最优调度方案有一定偏差;（2）在第二问的求解过程中，未建立相关模型，使得该法的通用性不强。二、模型的推广流水作业的排列排序问题管理科学、计算机科学和工程技术等许多领域皆会 遇到的问题。该问题的特点是模型繁多，适用于某一模型的算法，只要将模型的 条件稍加改变

32、，该算法即不适用。对于印刷厂的任务调度问题，没有一种单一的 模型（或算法）是通用的，即使在同一个印刷厂中，任务对各车间加工的需求时 间不同、一个模型的目标功能和限制条件不同，模型（或算法）就会千差万别。故本文中用于解决该印刷厂调度问题的模型及算法，仅能适用于与本文中限 制条件相类似的排班问题。但即使如此，本文在一定程度上仍能为现实管理调度 中的某些常见的流水作业排序问题提供参考，例如工厂工件加工排序问题、生产 计划安排问题等等。参考文献唐恒永、赵传立，排序引论（第一版）M,科学出版社，2002.6.司守奎，数学建模算法与程序M,2003.姜启源、谢金星、叶俊，数学模型（第三版）M,高等教育出版

33、社2003.8.肖华勇，实用数学建模与软件应用M,西北工业大学出版，2008.11.赵静、但琪，数学建模与数学实验（第三版）M,高等教育出版社，2008.11.附录问题一的程序：function exampleclcT=3 10 5 6 9 11;8 12 9 6 5 2;15 5 3 10 1;n,m=size(T); %n为工件的个数，m为机器的台数txm=; %存放所有m-1个两台虚拟机器问题的加工时间矩阵Fmax=; %存放所有m-1个两台虚拟机器问题的流程时间TUV=; %存放m-1个加工顺序for k=1:m-1for i=1:ntx(i,1)=sum(T(i,1:k);tx(i,

34、2)=sum(T(i,m+1-k:m);endfmax,uv=myjohnson(tx,T,n,m); %调用下面的 Johnson 算法函数 Fmax=Fmax,fmax;txm=txm,tx;TUV=TUVuv;end txm,Fmax,TUVoptim_Fmax=min(Fmax) %近似最优流程时间 ind=find(Fmax=optim_Fmax);optim_seq=TUV(:,ind) %近似最优加工顺序rrf “%* function f,UV=myjohnson(tx,T,n,m);U=find(tx(:,1)tx(:,2); %提出工件集 V tU=tx(U,1);tV=t

35、x(V2); %提出工件集U，V对应的时间 stU,ind1=sort(tU); %对时间按照从小到大排序 stV,ind2=sort(tV,descend); %对时间按照从大到小排序 UV=U(ind1);V(ind2); % 计算最优顺序 st=T(UV:); %最优顺序下的加工时间表 c(1,:)=cumsum(st(1,:); %求工件1的加工结束时间 c(2:n,1)=c(1,1)+cumsum(st(2:n,1); % 求机器 1 的加工结束时间 for i=2:n for k=2:mc(i,k)=max(c(i-1,k),c(i,k-1)+st(i,k);endendf=c(e

36、nd);运行结果：txm =32111010152227551414631299101415111133Fmax =5757TUV =335522411466optim_Fmax =57optim_seq = TOC o 1-5 h z 3552211466function example clcT=3105691152381116321310111565;8129652632615162615913583;215531012617916251781510102;n,m=size(T); %n为工件的个数，m为机器的台数txm=; %存放所有m-1个两台虚拟机器问题的加工时间矩阵Fmax=;

37、%存放所有m-1个两台虚拟机器问题的流程时间TUV=; %存放m-1个加工顺序for k=1:m-1for i=1:ntx(i,1)=sum(T(i,1:k);tx(i,2)=sum(T(i,m+1-k:m);endfmax,uv=myjohnson(tx,T,n,m); %调用下面的 Johnson 算法函数Fmax=Fmax,fmax;txm=txm,tx;TUV=TUVuv; end txm,Fmax,TUVoptim_Fmax=min(Fmax) %近似最优流程时间 ind=find(Fmax=optim_Fmax);optim_seq=TUV(:,ind) %近似最优加工顺序E“%*

38、 function f,UV=myjohnson(tx,T,n,m);U=find(tx(:,1)tx(:,2); %提出工件集 V tU=tx(U,1);tV=tx(V2); %提出工件集U, V对应的时间 stU,ind1=sort(tU); %对时间按照从小到大排序 stV,ind2=sort(tV,descend); %对时间按照从大到小排序 UV=U(ind1);V(ind2); % 计算最优顺序 st=T(UV:); %最优顺序下的加工时间表 c(1,:)=cumsum(st(1,:); %求工件1的加工结束时间 c(2:n,1)=c(1,1)+cumsum(st(2:n,1);

39、% 求机器 1 的加工结束时间 for i=2:nfor k=2:mc(i,k)=max(c(i-1,k),c(i,k-1)+st(i,k);endendf=c(end);一、定义myjohnson函数function f,UV=myjohnson(tx,T,n,m);U=find(tx(:,1)tx(:,2); %提出工件集 V tU=tx(U,1);tV=tx(V2); %提出工件集U，V对应的时间 stU,ind1=sort(tU); %对时间按照从小到大排序 stV,ind2=sort(tV,descend); %对时间按照从大到小排序 UV=U(ind1);V(ind2); % 计算

40、最优顺序 st=T(UV:); %最优顺序下的加工时间表 c(1,:)=cumsum(st(1,:); %求工件1的加工结束时间 c(2:n,1)=c(1,1)+cumsum(st(2:n,1); % 求机器 1 的加工结束时间 for i=2:nfor k=2:mc(i,k)=max(c(i-1,k),c(i,k-1)+st(i,k);endendf=c(end);二、求排序的编号函数function ggg=ggg(t)T=t;n,m=size(T); %n为工件的个数，m为机器的台数txm=; %存放所有m-1个两台虚拟机器问题的加工时间矩阵Fmax=; %存放所有m-1个两台虚拟机器问

41、题的流程时间TUV=; %存放m-1个加工顺序for k=1:m-1for i=1:ntx(i,1)=sum(T(i,1:k);tx(i,2)=sum(T(i,m+1-k:m);endfmax,uv=myjohnson(tx,T,n,m); %调用下面的 Johnson 算法函数 Fmax=Fmax,fmax;txm=txm,tx;TUV=TUVuv;endtxm;Fmax;TUV;optim_Fmax=min(Fmax); %近似最优流程时间ind=find(Fmax=optim_Fmax);optim_seq=TUV(:,ind); %近似最优加工顺序ggg=optim_seq(:,1);三、求解调度问题clc,clear;dd=188;yy=;dss=;ss3=;ss=input(请输入问题1 /2);for ii=1:10kk=31056911523811163213101115658129