数学建模：印刷厂任务的最优调度问题

1、暑期数学建模第四次培训印刷厂任务的最优调度问题印刷厂任务的最优调度问题摘要本文主要研究的是印刷厂任务的最优调度问题，在满足问题中任务调度和车间工作的相关约束下，为使完成任务总天数达到尽量小，从而建立资源受限排序模型，得出一个完整的任务加工方案。针对问题1和问题2，其主要研究的是任务最优调度问题，在所给假设的基础上，将3个车间组成两组，产生 2个两个虚拟车间问题的集合，然后利用 Johnson算法，把6或者20个任务分成两个集合U、V，前一个车间比后一个车间加工时间长的放到集合U中，否则就放入另一个集合V中。然后对集合U中的任务按照该个任务前一个车间的加工时间非递减顺序调度，对集合V中的任务按照

2、该个任务后一个车间的加工时间非递增顺序调度，最后有序集合U放到有序集合V之前构成任务的最优加工顺序，比较Johnson算法的2个最优加工顺序得出6个任务的所需最少天数为57天，最优加工顺序为（3,5,2,4,1,6）或者（3,5,2,1,4,6），20个任务最少需要157天，最优加工顺序为（8,14,3,5,19,2,17,15,12,11,16,18,10,1,4,7,20,13,6,9）。针对问题3，主要是设计一个加工方案使得尽量多的任务在120天内完成加工。首先将20个任务在三个车间的所需的天数累加得到该个任务的总天数，然后把所有任务按照天数递增的方式排序，循环删除任务天数多的任务，剩下

3、的任务用CDS 启发式算法，直到算出的天数不大于120天就不再删除任务，最后得出最优加工顺序(8,14,3,5,19,2,17,16,18,10,1,4,7,20,13,9,6,15,13,11)，120天内最多完成17个任务。 问题4和问题5要求制定一个包含每个车间放假方案的任务加工方案，使得完成问题2中的这20项任务总共需要的天数尽量少。为满足在第50天到第60天这个长度为11天的时间里每个车间连续放假2天与3天的要求，我们要找到在49至58天及49至57天完工的对应任务项。由问题2结果知排名在第五项任务前的各任务对应完工时间都小于49，依次取出后15项任务中的任意一项排在第六，原方案中第

4、五项任务之后的各项依次向后排一位。依此类推，得到新排名第六至二十项任务的对应完成时间及方案，最后从中筛选出使完成所有任务总共需要的天数最少的序列即为所求。由运行结果知该加工顺序方案是在问题2排序的基础上将原排名十三的任务项插至第五项与第六项任务之间，得到的序列（8,14,3,5,19,10,2,17,15,11,16,18,1,4,7,20,13,6,9），对应的Fmax=159, 即最少天数为159，得到具体的最优加工方案。问题5得出的序列与问题4一样，对应的Fmax=160，即最少天数为160，得到具体的最优加工方案。关键词：CDS 启发式算法；Johnson算法；调度；最优加工方案；一、

5、问题重述某印刷厂共有3个车间，分别为印刷车间、装订车间和打包车间。每一项任务必须依次经过印刷车间、装订车间和打包车间。由于技术原因，每一项任务必须在印刷车间完成该任务的全部印刷之后才可以进入装订车间（印刷和装订之间可以间隔若干天，也可以连续依次进行）；每一项任务必须在装订车间完成该任务的全部装订之后才可以进入打包车间（装订和打包之间可以间隔若干天，也可以连续依次进行）；不同的任务不能同时共享同一车间；一旦某项任务进入某一车间，该任务就必须连续被执行，不允许被其它任务或事件打断。该印刷厂各车间目前均处于空闲状态，没有任务需要加工。印刷车间将来开工的那天记为第1天。问题1.现接到6项加工任务，各项

6、任务对各车间所需的时间（单位为：天）如表1所示。试设计一个加工方案（一个完整的加工方案应该包括每一项任务在各个车间中的开始加工时间和完成时间）使得完成这6项任务总共需要的天数尽量少。表1任务编号车间123456印刷车间31056911装订车间8129652打包车间21553101问题2. 问题1中的6项任务还没有下达到车间，现又接到14项加工任务，各项任务对各车间所需的时间（单位为：天）如表2所示。试设计一个加工方案使得完成这20项任务总共需要的天数尽量少。表2任务编号车间7891011121314151617181920印刷车间52381116321310111565装订车间63261516

7、2615913583打包车间2617916251781510102问题3. 对于问题2中所考虑的20个任务，请设计一个加工方案使得尽量多的任务在120天内（含第120天）完成加工。问题4. 为了工人的健康，印刷厂工会讨论决定从第50天到第60天这个长度为11天的时间里每个车间放假2天。为了尽量把放假对印刷厂的生产进度造成的影响降到最低，工会决定把具体的放假时间交给印刷厂调度员来决定，并要求每个车间放假的这2天必须是连续的2天，每个车间的放假起止时间可以不一样。请你们帮助印刷厂调度员来制定一个包含每个车间放假方案的任务加工方案使得完成问题2中的这20项任务总共需要的天数尽量少。问题5. 在问题4

8、中，如果每个车间的放假天数不是2天而是连续的3天，请在问题4中其余条件和要求不变的情况下重新制定一个包含每个车间放假方案的任务加工方案使得完成问题2中的这20项任务总共需要的天数尽量少。二、问题分析 根据表中所给的各项任务的印刷时间、装订时间和打包时间，要求每项任务先完成印刷工序，再进行装订，最后完成打包工序，各车间按自然顺序工作。针对问题1，在Matlab软件中采用了CDS 启发式算法，然后利用 Johnson的两个车间算法得到 m-1个加工顺序，最后选择其中最好的一个作为近似最优解，求出完成所有任务总工期最短的加工顺序和近似最优流程时间，建立车间最优顺序流水作业模型，最后得到一个

9、总任务天数最少的最优方案；问题2是在问题1的基础上增加任务项至20，与问题1的思想一致，只要在问题1的程序基础上改变任务所需时间对应的矩阵即可求解。 问题3针对问题2所考虑的20个任务，要设计一个加工方案使得尽量多的任务在120天内完成加工，而设有n项任务满足要求，根据问题2的结果可预测10项任务一定能在120天内完成，故令n从10开始循环到20，可得出相应完成任务的项数t，其中最大的t值为所求解。问题4和问题5要求的是制定一个包含每个车间放假方案的任务加工方案，使得完成问题2中的这20项任务总共需要的天数尽量少，考虑到每个车间在50到60天这个时间段连续放两天假，而各个车间的任务一旦执行就不

10、能中断，因此，我们需要在模型一的基础上优化求解。前面已经得出每个任务在各车间的结束时间，为满足放假时间段的限制，找到在49至58天完工的对应任务项。根据得到的最少天数方案将对应任务项所需时间加两天代入原方案求解，最后将问题2的结果对应排序得到最后的方案。三、模型假设（1）不考虑车间机器损坏情况的影响；（2）一个任务不能两次在同一车间执行；（3）任务在加工过程中采取平行移动方式，即当上一项任务完工后，立即送下个车间加工；（4）任务一旦进行，则不会被其他事情打断即不允许中断；（5）每个车间一次只能加工一个任务；（6）任务项数、车间数和加工时间已知，加工时间与加工顺序无关。 四、符号说明符号符号说明

11、tij各任务的加工所需时间U，V有序集n所有任务的个数m所有车间的个数五、模型求解与建立5.1.1问题1和问题2的模型建立问题1和问题2主要研究的是设计加工方案，使得完成这6或者20项任务总共需要的天数尽量少。这是一个非线性的优化问题，本模型主要采用了CDS 启发式算法，算法的具体的做法是首先把m个车间系统地组成两组，产生 m-1个两个车间问题的集合，然后利用 Johnson的两个车间算法得到 m-1个加工顺序，最后选择其中最好的一个作为近似最优解。问题2相对于问题1的加工车间数量不改变，只是任务数量由6增大到20，因而使用对应到CDS 启发式算法中的分组情况类似。具体的做法是首先把3个车间系

12、统地组成两组，产生 2个两个车间问题的集合，然后利用 Johnson的两个车间算法得到 2个加工顺序，其中Johnson算法的做法把所有的任务分成两个集合，前一个车间比后一个车间加工时间长的放到集合U中，否则就放入另一个集合V中。然后对集合U中的任务按照该个任务前一个车间的加工时间非递减顺序调度，对集合V中的任务按照该个任务后一个车间的加工时间非递增顺序调度，最后有序集合U放到有序集合V之前构成任务的最优加工顺序。对于用ohnson算法得到的2个最优加工顺序选择其中最好的一个作为近似最优解。5.12问题1和问题2的模型求解为了方便求解，本模型先介绍Johnson算法的规则和具体做法：假定有n个

13、任务，在第一个车间和第二个车间的加工时间分别为ti1，i=1.n和ti2，i=1.n最优调度由如下规则给出:Johnson 规则:如果，则在最优调度中排在的前面。Johnson 算法可以描述为: 步骤1：对个任务进行分组，具体分组情况； 步骤2：对集合中的任务按非递减顺序调度； 步骤3：对集合中的任务按非递增顺序调度； 步骤4：有序集合放在集合中之前构成任务最优加工顺序。本文中有三个车间，主要采用的是CDS 启发式算法，具体是先对所有任务进行按照加工时间分组，具体分组情况如下：和， 具体分组结果如表1和表2所示表1i12345678910k=1ti3310569115238ti32155310

14、12617k=2ti1+ti2112214121413115514ti2+ti3102714915399313表2i11121314151617181920k=1ti11116321310111565ti3916251781510102k=2ti1+ti226325827192430148ti2+ti3243241132172815185问题1中，当k=1时，用Johnson 算法和matlab编程计算可以得出加工顺序（3,5,2,4,1,6），相应的Fmax=57；当k=2时，得到加工顺序（3,5,2,1,4,6），相应的Fmax=57 ；比较得到的两个加工顺序，得出两组排序均可，最少天数为

15、57，具体的任务安排方案见表3。表3任务时间印刷车间装订车间打包车间任务3开始时间1615完成时间51419任务5开始时间61520完成时间141929任务2开始时间152537完成时间243651任务1开始时间253752完成时间274453任务4开始时间284554完成时间335056任务6开始时间345157完成时间445257问题2中，当k=1时，用Johnson 算法和matlab编程计算可以得出加工顺序（8,14,3,19,5,2,17,15,12,18,11,16,10,4,1,7,13,20,6,9），与之相应的Fmax=160；当k=2时，得到加工顺序（8,14,3,5,19

16、,2,17,15,12,11,16,18,10,1,4,7,20,13,6,9），相应的Fmax=157 ；比较得到的两个加工顺序，得出两组排序，最少天数为157，具体的任务安排方案见表4。表4任务时间印刷车间装订车间打包车间任务8开始时间136完成时间2511任务14开始时间3612完成时间41116任务3开始时间51221完成时间92025任务5开始时间102126完成时间182535任务19开始时间192636完成时间243345任务2开始时间253547完成时间344661任务17开始时间354762完成时间455976任务15开始时间466077完成时间587493任务12开始时间5

17、97594完成时间7490109任务11开始时间7591110完成时间85105118任务16开始时间86106119完成时间95114126任务18开始时间96115127完成时间110119136任务10开始时间111120137完成时间118125143任务1开始时间119126144完成时间121133145任务4开始时间122134146完成时间127139148任务7开始时间128140149完成时间132145150任务20开始时间133146151完成时间137148152任务13开始时间138149153完成时间140150154任务6开始时间141152155完成时间151

18、153155任务9开始时间152155157完成时间154156157问题3的模型建立问题3主要研究的是一个加工方案，使得尽量多的任务在120天内完成加工。针对这个问题，本模型采用把加工的天数多的任务,尽量往后排,这样能保证在120天内,完成的数量尽量多。本文把单个任务的三个车间加工的天数，然后按照加工总天数递增的顺序排序，删除天数最大的任务，用CDS 启发式算法计算剩余任务所需的最少天数，如果完工天数大于120天，继续删除天数次要大的天数，直到完工天数不大于120天为止。问题3的模型求解 首先对单个任务的三个车间加工天数进行累加，按照任务总天数递增排序得到如下排序如表5和表6：表5编号车间9

19、132081714643印刷车间33523521165装订车间2233866269打包车间1226225135总天数671011131313141519 表6编号车间105191618112171512印刷车间89610151110111316装订车间658951512131516打包车间71010810915151716总天数21242427303537394548 由表可知，第12个任务的所需天数最多，删除该任务，对剩下19个任务用CDS 启发式算法，得到Fmax=141;然后删除个15个任务，对剩下的18个任务用CDS 启发式算法，得到Fmax=128；继续删除17个任务，对剩下的17个

20、任务用CDS 启发式算法，得到Fmax=117；综上所述，在120天内最多完成17个任务，最优加工顺序为(8,14,3,5,19,2,17,16,18,10,1,4,7,20,13,9,6,15,13,11)具体的任务加工方案见表7。表7任务时间印刷车间装订车间打包车间任务8开始时间147完成时间3612任务14开始时间4713完成时间51217任务3开始时间61322完成时间102126任务5开始时间112227完成时间192636任务19开始时间202737完成时间253446任务2开始时间263648完成时间354762任务17开始时间364863完成时间466077任务16开始时间47

21、6178完成时间566985任务18开始时间577286完成时间717695任务10开始时间728096完成时间7985102任务1开始时间8086103完成时间8293104任务4开始时间8394105完成时间8899107任务7开始时间29100108完成时间93105109任务20开始时间93106110完成时间98108111任务13开始时间99109112完成时间101110113任务9开始时间102111114完成时间104112114任务6开始时间105116118完成时间115117118任务15开始时间116129144完成时间128143160任务13开始时间1291451

22、61完成时间144160176任务11开始时间145161177完成时间155175185问题4和问题5的模型建立问题4和问题5要求的是制定一个包含每个车间放假方案的任务加工方案，使得完成问题2中的这20项任务总共需要的天数尽量少，考虑到每个车间在50到60天这个时间段连续放两天假，而各个车间的任务一旦执行就不能中断，因此，我们需要在模型一的基础上优化求解。由表3，可以得出每个任务在各车间的结束时间，为满足放假时间段的限制，找到在49至58天完工的对应任务项。据表可知，排名在第五项任务前的各任务对应完工时间都小于49，为了尽量把放假对印刷厂的生产进度造成的影响降到最低，随机取出后15项任务中的

23、一项排在第六名，而原方案中第五项任务之后的各项依次向后排一位。因此，得出新方案中排在第六的任务对应完成时间和新的排序方案，依次类推，得到新排名七至二十任务的对应完成时间及方案。从中筛选出在49至58天完工的对应任务项的完成时间，最后取使完成所有任务总共需要的天最少的方案即为所求。根据得到的最少天数方案将对应任务项所需时间加两天代入原方案求解（相应语句在程序中实现），得出相应各项任务的结束时间即得到所求方案。问题5与问题4的思想一致，只是在其基础上将连续放假两天改为三天，其余条件和要求不变，制定一个包含每个车间放假方案的任务加工方案使得完成问题2中的所有任务总共需要的天数最少，根据得到的最少天数

24、方案将对应任务项所需时间加三天代入原方案求解即可。问题4和问题5的模型求解问题4中，根据程序运行后的结果得出后十五项中排名第八（即原方案中排名十三）的任务对应的总时间最少，该加工顺序方案是在问题2排序的基础上将原排名十三的任务项插至第五项与第六项任务之间，得到的序列（8,14,3,5,19,10,2,17,15,11,16,18,1,4,7,20,13,6,9), 相应的Fmax=159, 即最少天数为159，可将印刷车间放假时间定为第43、44两天，装订车间放假时间定为41、42两天，打包车间放假时间定为46、47两天，具体的加工方案见表8。表8任务时间印刷车间装订车间打包车间任务8开始时间

25、136完成时间2511任务14开始时间3612完成时间41116任务3开始时间51221完成时间92025任务5开始时间102126完成时间182535任务19开始时间192636完成时间243345任务10开始时间253448完成时间323954任务2开始时间334557完成时间425671任务17开始时间455772完成时间556986任务15开始时间567087完成时间6884103任务12开始时间6985104完成时间84100119任务11开始时间85101120完成时间95115128任务16开始时间96116129完成时间105124136任务18开始时间106125137完成时

26、间120129146任务1开始时间121130147完成时间123137148任务4开始时间124138149完成时间129143151任务7开始时间130144152完成时间134149153任务20开始时间135150154完成时间139152155任务13开始时间140153156完成时间142154157任务6开始时间143155158完成时间153156158任务9开始时间154157159完成时间156158159问题5中，根据程序运行后的结果得出后十五项中排名第八（即原方案中排名十三）的任务对应的总时间最少，该加工顺序方案是在问题2排序的基础上将原排名十三的任务项插至第五项与第六

27、项任务之间，得到的序列（8,14,3,5,19,10,2,17,15,12,11,16,18,1,4,7,20,13,6,9)，相应的Fmax=160，即最少天数为160，可将印刷车间放假时间定为第43、44、45三天，装订车间放假时间定为41、42、43三天，打包车间放假时间定为46、47、48三天，具体的加工方案见表9。表9任务时间印刷车间装订车间打包车间任务8开始时间136完成时间2511任务14开始时间3612完成时间41116任务3开始时间51221完成时间92025任务5开始时间102126完成时间182535任务19开始时间192636完成时间243345任务10开始时间2534

28、49完成时间323955任务2开始时间334658完成时间425772任务17开始时间465873完成时间567087任务15开始时间577188完成时间6985104任务12开始时间7086105完成时间85101120任务11开始时间86102121完成时间96116129任务16开始时间97117130完成时间106125137任务18开始时间107126138完成时间121130147任务1开始时间122131148完成时间124138149任务4开始时间125139150完成时间130144152任务7开始时间131145153完成时间135150154任务20开始时间1361511

29、55完成时间140153156任务13开始时间141154157完成时间143155158任务6开始时间144156159完成时间154157159任务9开始时间155158160完成时间157159160六、模型评价与推广6.1 模型的优点（1）由简单到复杂一步步地建立数学模型，将实际问题转化为数学问题，用数学知识进行分析，从而达到解决问题的目的；（2）该模型贴近实际、算法直观，注重数据的处理和存储方式，大大提高了效率，通过大量的特征信息的提取、观察，并结合有效的算法，使其满足现实要求；（3）该模型具有很强的现实意义，所解决的印刷厂调度问题有一定的社会价值。6.2 模型的缺点（1）该模型是在

30、众多假设成立的情况下建立的一种理想模型，而这些假设不一定全都符合实际情况；（2）由于考虑任务项不够充足，得出的结果具有一定的局限性，缺乏普遍性。6.3 模型的推广 印刷厂任务的调度模型在护士各项任务满足相应约束条件基础上，从多方面考虑，使工序的顺序最优化，减少了该厂的工资成本和任务总天数，从而大大提高了工作效率。进一步考虑车间放假因素，建立一个印刷问题扩展模型，使得模型更完善、更贴近实际。模型可以大量推广，如学校课表安排优化、传染病动力学、网络蠕虫研究等，甚至在一些教研领域，都可以运用本模型，类似地还可以推广到人们对于较复杂问题的决策上。七、参考文献1姜启源.数学建模(第三版).北京：高等教育

31、出版社，20032肖华勇.数学建模与软件.西安：西北工业大学出版社，20083 .算法设计技巧与分析.电子工业出版社,2009年4 胡守信.基于MATLAB的数学实验.北京：科学出版社，2004附录问题一程序：function example clc T=3 10 5 6 9 11 8 12 9 6 5 2 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-

32、1 for i=1:n tx(i,1)=sum(T(i,1:k); tx(i,2)=sum(T(i,m+1-k:m); end c,fmax,uv=myjohnson(tx,T,n,m); %调用下面的 Johnson 算法函数 Fmax=Fmax,fmax; txm=txm,tx; TUV=TUV,uv; end txm,Fmax,TUV optim_Fmax=min(Fmax) %近似最优流程时间 ind=find(Fmax=optim_Fmax); optim_seq=TUV(:,ind) %近似最优加工顺序 c %* function c,f,UV=myjohnson(tx,T,n,m

33、); U=find(tx(:,1)<=tx(:,2); %提出任务集 U V=find(tx(:,1)>tx(:,2); %提出任务集 V tU=tx(U,1);tV=tx(V,2); %提出任务集 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,

34、1)+cumsum(st(2:n,1); %求车间1的加工结束时间 for i=2:n for k=2:m c(i,k)=max(c(i-1,k),c(i,k-1)+st(i,k); end end f=c(end); 问题二程序：function example1 clc T=3 10 5 6 9 11 5 2 3 8 11 16 3 2 13 10 11 15 6 58 12 9 6 5 2 6 3 2 6 15 16 2 6 15 9 13 5 8 32 15 5 3 10 1 2 6 1 7 9 16 2 5 17 8 15 10 10 2' n,m=size(T); %n 为

35、任务的个数，m为车间的个数 txm=; %存放所有 m-1 个两个虚拟车间问题的加工时间矩阵 Fmax=; %存放所有 m-1 个两个虚拟车间问题的流程时间 TUV=; %存放 m-1 个加工顺序 for k=1:m-1 for i=1:n tx(i,1)=sum(T(i,1:k); tx(i,2)=sum(T(i,m+1-k:m); end c,fmax,uv=myjohnson(tx,T,n,m); %调用下面的 Johnson 算法函数 Fmax=Fmax,fmax; txm=txm,tx; TUV=TUV,uv; end txm,Fmax,TUV optim_Fmax=min(Fmax

36、) %近似最优流程时间 ind=find(Fmax=optim_Fmax); optim_seq=TUV(:,ind) %近似最优加工顺序 c %* function c,f,UV=myjohnson(tx,T,n,m); U=find(tx(:,1)<=tx(:,2); %提出任务集 U V=find(tx(:,1)>tx(:,2); %提出任务集 V tU=tx(U,1);tV=tx(V,2); %提出任务集 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); %求车间