机床调度策略的设计.doc

三峡大学-数学建模，2011机床调度策略的设计摘要本文从横向和纵向两个方面对机床的调度策略做出了分析。首先从工序的顺序（横向）方面作出了分析，五项任务依次完成，由此建立了模型一，即横向单机床优化模型；然后从五项任务的角度（纵向）作出了分析，四道工序依次执行，由此建立了模型二，即纵向多机床优化模型。最后运用禁忌-遗传算法，通过计算机编程求解。对于问题一：横向考虑工序顺序，每个工序中只选择一台机床进行生产，然后五项任务依次执行此过程，完成产品的加工。纵向考虑五项任务同时执行，按照工序顺序进行。问题要求完成产品加工的总时间最短，各个机床完成的工作量尽量均衡，以均衡度作为衡量值。然后运用禁忌-遗传算法，通过MATLAB和LINGO编程求解得到模型一和模型二的结果。通过比较问题一两个模型的求解结果（表5.3、5.7）可以看出，两个模型的均衡度相差不大，但是模型二结果中总时间远小于模型一。因此模型二是问题一的最优机床调度策略。总时间小时，均衡度。对于问题二：问题需要求解最小加工费用，属于单目标最优化问题，但是本文从实际出发，考虑加工费用最小的同时也使得总时间最短，并使各机床的任务量尽量均衡。同样经过横向和纵向分析，在问题一的基础上运用模型一和模型二来求解。通过比较问题二的两个模型的求解结果（表 6.2、6.4 ）可以看出，两个模型的均衡度和总费用相差不大，但是模型二结果中总时间远小于模型一的，因此模型二求解的机床调度策略是最优的，总费用万元，总时间小时。文章最后给出了对模型一和模型二的优点和缺点的评价，提出了模型的改进方案，并对本文建立的模型进行了推广。关键字：机床调度 禁忌-遗传算法 均衡度 多目标最优化 横向纵向分析法1 问题重述1.1 问题提出背景某工厂收到了5个客户提交的5种不同的加工任务订单, 每种任务中的每一件产品在加工时都要经过A,B,C，D，4道工序。这些工序由工厂的6台机床来完成。下表给出了各项任务的每件产品的每道工序可供选择的加工机床编号及其所需要的完成时间（单位：小时）工表 1 各项任务的相关参数任务序工序任ABCD1（1, 3，5）5,7,12（1, 2，6）3,5,9（2，4）7,9（5，6）8,132（2, 3）12,10（3，5，6）9,7,10（1, 4，5）5,7,12（2，6）11,93（1, 4，5）6,7,6（3，6）9,13（1, 3，5）8,9,12（ 3，4）17,144（3, 4，5）9,7,12（2, 4）10,12（1, 3，6）8,7,9（1, 3，5）5,7,55（3，5）8,10（6）9（1，4，6） 5,7,12（1，2，5）7,9，10【注】：其中圆括号内数据为该工序可以选择的加工机床号，方括号内数据为对应的加工时间。1.2 需要解决的问题问题一：请将任务合理地分配到各机床，以期望用最短的时间完成订单，并且保证各机床任务量尽可能均衡；问题二：假设每件产品在加工时在两台机床之间的调度需要1小时，每件的调度费用为1000元，6台机床每小时的运行成本分别为2000元,1800元,1500元,1200元，1000元，800元，此种情况下任务又该怎样合理地分配到各机床，保证生产费用最小。2 模型假设及符号说明2.1 模型假设1.假设题目给出的机床工作时间和费用是有效的、合理的；2.假设车床在加工产品（零件）时未出现故障；3.假设工序是有序的，每台机床在任何时刻只可加工1个零件；4.假设进行下一个工序时不考虑中间停顿时间；5.假设加工所有零件的速度是均匀的，恒定的。2.2 符号说明第个任务中每个零件在每个工序中通过某个机床加工所需的时间矩阵第个任务中每个零件在每个工序中通过某个机床加工所需的运行成本矩阵机床加工零件所花的总时间加工所有零件所需的总费用任务分配的均衡度第个任务的需加工的零件总数第个任务中每个零件在第道工序中利用机床加工所需时间第个任务中零件在第道工序中利用机床加工所需的运行成本零件在第道工序中所需的调度费用第台机床加工的零件的总次数第道工序加工零件所需的总时间第个任务的第道工序中选择机床的台数第道工序中任务的零件调度的次数零件调度一次的费用横向分析中的逻辑函数纵向分析中的逻辑函数3 问题分析本题是要根据所给的任务订单，将任务合理的分配到有限个数的机床进行加工。现在知道，工厂收到的5种不同的任务订单中, 每种任务中的每一件产品在加工时都要经过A，B，C，D，4道工序，这些工序由工厂的6台机床来完成。加工零件在每道工序中从所提供的机床中进行选择，且对应地选择一台机床。基于所给的数据，本题提出了两个问题，针对这两个问题，我们分别做出了横向和纵向的分析：针对问题一，求解目标有两个：最短时间，最好的均衡度。(1) 横向分析：分析角度从四个工序出发，因为工序的有序性（假设3），所以在计算一项任务完成的时间时，工序从A到B，再到C、D，在每个工序中只选择一台机床进行加工，按照这个顺序来累积每个工序的时间。再将5项任务的加工时间累和，就可以得到优化目标总时间了。另外还要求每个机床的任务量尽量均衡，就定义均衡度作为衡量指标。这样就建立了模型一，即横向单机床模型。(2)纵向分析：分析角度是从五个任务出发的，即进行工序A时，任务1，2，3，4，5同时进行工序A的加工，各工序中所有机床都运行，充分利用， 零件在每道工序中都根据自身可供选择的机床进行加工，若机床被占用，则不选择这台机床，这样就能很大程度上缩短加工时间。计算时只需要取5项任务中时间最长的时间作为最后的总时间。同样定义均衡度作为各台机床工作量均衡程度的指标。相对于横向分析法，纵向分析更能达到优化目的。为此我们建立了模型二，即纵向多机床模型。针对问题二，求解目标有一个：加工费用最小。虽然只有一个求解目标，但是为了更符合实际需求，我们对问题的求解做出优化，即在使得加工费用最小的同时又满足所用时间最短。因此，同样做出如下分析。（1）横向分析：分析角度同样从四个工序出发，因为每件产品在加工时在两台机床之间的调度需要1小时，故工序更换时要考虑调度带来的费用；另外，6台机床每小时的运行成本不同，所以机床的运行时间决定了总费用的大小。最后运用模型一（横向单机床模型）求解总费用的最小值。（2）纵向分析：分析角度仍然是从五个任务出发，五个任务同时进行，四个工序A、B、C、D分别按顺序进行。求解时按照模型二（纵向多机床模型）进行，考虑在工序更换时产生调度费用，并且6台机床每小时产生不同的运行成本。对于运行成本，可以转化为5个任务的零件运行成本总和，而每个任务的零件运行成本总和又可转化为每个零件在4道工序中运行成本总和。另外，每个零件在每道工序中加工时，机床需要选择，因此可以构造一个逻辑函数（只可取1,0两个值），来进行选择。 对于调度费用，每个零件在每道工序中是否需要调度，要看每个零件在相邻工序中选择机床是否是相同的，若相同，则无需调度，若不相同，则需调度。在此也可构造逻辑函数来进行选择。4 数据分析4.1问题一原始数据的处理由已知数据（见附录表1）可知，公司接到5个任务，每个任务是加工一定数量不同种类的零件数，所有的零件可分配给6台机床加工。每个零件要经过A,B,C,D共4道工序，并且是按顺序的。每道工序只能选择j(j6)台机床中的一台加工。1-6号机床每道工序加工每个零件所需的时间，因此可构造矩阵,具体如下： 其中i=1,2,.,5,为任务的编号，为工序的编号，为每个零件在每道工序中被每台机床加工的时间。若机床可供零件选择，则时间就为对应的给出时间，若机床不可被零件选择，则时间就为。如： 继续构造矩阵A,具体如下： 其中i=1,2,.,5,为任务的编号，为工序的编号，为逻辑函数，当零件在第道工序选择机床j时，则为1，否则为04.2 问题二原始数据的处理由已知数据（见附表2 ）可知，每个零件在每道工序中只能选择j(j6)台机床中的一台加工，而万一零件在换工序的同时换了机床，则还需调度费用，因此必须分调度还是未调度。4.2.1 若调度了，则构造矩阵,具体如下： 其中=1,2,.,5,为任务的编号，为工序的编号，为机床在每道工序中加工每个零件运行所需的总费用，若机床可供零件选择，则运行总的费用就为对应的给出费用，若机床不可被零件选择，则费用就为。如： 4.2.2若未调度：则只有当相邻工序有相同机床的选择时，才可以进行调度。机床在每道工序中加工每个零件运行所需的总费用与调度时的相同。5 问题一的解答5.1 均衡度的定义定义均衡度为六台机床中的最大任务量与最小任务量差值与最大任务量的比值，其中为第j台机床加工的零件的总次数。模型一 横向单机床模型5.2 模型一的建立5.2.1确定目标函数题目有两个目标，即零件加工的最小时间与任务分配的均衡度。假设任务是按序完成的，零件在每个任务每道工序加工也是按序的，且零件未同时加工。加工零件所花总时间相当于求每个零件单独加工的总时间，表达式如下：其中，为任务的编号，为机床的编号，为工序的编号，为第个任务的零件总数，为第个任务中的每个零件在第道工序中利用机床j加工所需时间。当零件选择了机床j，则，当零件未选择机床，则。5.2.2确定约束条件: 5.2.3综上所述，所得问题一的多目标优化模型一: 5.3模型一的求解:（1）多目标转化为单目标：问题一需要求解的目标有两个，属于多目标最优化1的求解，因此需要将多目标优化模型转化为单目标优化模型进行求解，转化后的模型求解目标如下:（2）确定算法：本文研究的对象这是机床调度问题，目的是求最小的加工时间，因此需选择每个零件相应的加工工艺路线，安排零件在机床上的加工顺序，确定每台机床的最后完工时间，则最大的完工时间即为本题最小的完工时间。因此设计嵌套的禁忌-遗传算法2，首先利用禁忌算法搜索零件的加工工艺路线，在工艺算法确定的情况下再用遗传算法3每个零件的加工顺序。).禁忌算法设计：.解的编码及规模：编码采用自然数，共有个零件待加工，编码长度为。比如有个零件待加工，每个零件可选的加工路线有，其中，表示第个零件的加工路线数，则个零件的编码为,其中。同时对每个零件的加工路线按加工时间的长短进行自然编码。这样生成初始解群，对每个零件尽量采用较小的工艺路线编码。初始解规模定为。.适配值函数：本组工艺路线安排下，经遗传算法求得的最小完工时间。).遗传算法设计：.遗传编码及解码算法：要产生活性调度，则要查看前一道工序的约束时间，待加工的工序只能安排在前一道工序的约束时间之后。要查看此工序的加工机床在此工序的上道约束工序结束之后和本机床最后的一个加工任务结束之前是否有满足此道工序加工的空闲时间。若有，则尽可能把此道工序安排在尽可能在前得空闲时间上。若无，则把此道工序安排在本机床目前为止最后的一个任务之后。.选择适值函数：为提高算法的运行速度，选目标函数为适值函数。(3) 算法主流程图：（4）模型一求解结果：通过遗传算法的思想，运用MATLAB编程4求解，并利用LINGO软件编程辅助求解（程序代码见附录）得到的结果见表5.3：表5.3模型一的求解结果机床编号123456任务量(次数)322236253629总时间（h）1452模型一的结果分析：任务分配均衡度，机床加工零件所花总时间,机床1,2,3,4,5,6加工的零件次数分别为32，22，36，25，36，29，可见任务分配的均衡性一般，而且机床加工零件的总时间过大，因此需要对模型一进行优化，由此建立了模型二。模型二 纵向多机床模型5.4 模型二的建立5.4.1确定目标函数：纵向考虑时，五个任务各自所有的零件均被机床加工，直到5个任务中的零件在该工序全部完成，再将所有零件转到下一个工序。对于同一个任务，每个工序中的每次加工只能选择一个零件，直到4道工序全部完成，再选择第二个零件。这样一来只需分别求出每道工序中零件加工的时间，而每道工序零件加工的总时间应取每个任务的所有零件在这道工序中加工时间的最大值。由此确定各道工序的加工时间表达式如下： 即 所以加工零件的总时间为：其中，为任务的编号，为机床的编号，为工序的编号，为第个任务的零件总数，第个任务中每个零件在第道工序中利用机床加工所需时间。为第个任务的第道工序中选择机床的台数。同样，任务分配的均衡度的表达式如下：为第j台机床加工的零件的总次数.5.4.2确定约束条件：综上确定约束条件为 其中为第个任务的总零件数，=1,2,.,5。5.5 综上所述，所得问题一的多目标优化模型二： 约束条件为： 5.6 模型二的求解：（1）算法的确定：算法同模型一，同样确定为禁忌-遗传算法。算法流程图见附录一。（2）多目标转化为单目标：同样，问题一需要求解的目标有两个，属于多目标最优化的求解，因此需要将多目标优化模型转化为单目标优化模型进行求解，转化后的模型求解目标如下:（3） 模型二的求解结果：通过遗传算法的思想，运用MATLAB和LINGO软件辅助编程求解（程序代码见附录），得到的结果见表5.6、5.7：表5.6 各道工序中5个任务各自加工时间（h）任务工序第一道工序第二道工序第三道工序第四道工序第1个任务54726264第2个任3个任务46915698第4个任务841208460第5个任务40456035最大时5.7模型二的求解结果机床编号123456任务量(次数)342137233530总时间（h）477（4）各机床加工产品的次数变化图：图5.1 各机床加工产品次数5.7 模型二的结果分析：（1） 由表5.6可知，第一道工序中任务2的加工时间最长，为130小时，第二道工序中任务4的加工时间最长，为120小时，第三道工序中任务4的加工时间最长，为84小时，第四道工序中任务2的加工时间最长，为143小时。之所以出现这种情况，有两个原因：（1）任务2和任务4的加工零件数最多，分别为13,12，因此四道工序均是任务2,4的加工时间最长。（2）第一道工序中，任务2的零件选择机床加工的最短时间可为10小时，任务4是7小时，因此工序一中任务2时间较长。第二道工序中，任务2的零件选择机床加工的最短时间可为7小时，任务4是10小时，因此工序二中任务4时间较长。第三道工序中，任务2的零件选择机床加工的最短时间可为5小时，任务4是7小时，因此工序三中任务4时间较长。第四道工序中，任务2的零件选择机床加工的最短时间可为9小时，任务4是5小时，因此工序一中任务2时间较长。（2）由表5.7结果可以看到，任务分配均衡度，机床加工零件所花总时间，机床1,2,3,4,5,6加工的零件次数分别为34,21,37，23,35,30。由图5.1可见，模型二任务分配的均衡度与模型一的相差不大，但是机床加工零件的总时间却比模型一的时间小得多，这对于生产厂家来说，大大提高了生产效率，获得更大利润。这也比较符合实际，因为模型一是以单独加工零件为前提建立的，模型二是以同时加工为前提建立的，同时加工的时间比单独加工的时间要小是更加符合实际的，因此模型二为最优调度策略。6 问题二的解答对于问题二，要求在满足所给条件下求解最小费用，故问题二建立的是单目标最优化模型，在问题分析中对问题二已经做过横向和纵向分析，得出可以运用问题一的模型一和模型二来解决问题二的结论，所以，以下是对问题二的求解过程。6.1 问题二模型一的建立（横向单机床模型）6.1.1确定目标函数问题二中只有一个求解目标，即最小的生产费用。在横向分析中，任务是按序完成的（假设3），且零件在每个任务每道工序加工也是按序的。加工零件所花的总生产费用表达式如下： 其中，为任务的编号，为机床的编号，为工序的编号，为第个任务的零件总数,为第个任务每个零件在第道工序中利用机床加工所需的运行成本，为零件在第道工序的调度费用。，均为逻辑函数，当零件选择了机床，则，当零件未选择机床，则。当零件在第道工序调度时，,零件在第道工序未调度时，。6.1.2横向考虑的机床加工工序流程图：6.1.3确定约束条件： 6.1.4综上所述，所得问题二的单目标最优化模型一： 约束条件为： 6.2 问题二模型一的求解：（1）算法的确定：算法同样确定为禁忌-遗传算法。具体流程图见附录一。（2） 模型的求解结果：由于分析角度是从四个工序出发（横向分析），每件产品在加工时在两台机床之间的调度需要1小时，工序更换时要考虑调度带来的费用；另外，6台机床每小时的运行成本不同，所以机床的运行时间决定了总费用的大小。通过LINGO编程求解实现，得到问题二模型一的求解结果如下表6.2：表6.2 模型一求解结果机床编号123456任务量(次数)362033273727总费用（元）1669000总时间（h）1555问题二模型一的结果分析：由结果可知，任务分配均衡度，机床加工零件所花总时间小时,机床1,2,3,4,5,6加工的零件次数分别为36,20,33，27,37,27。机床加工零件的总费用元。可见，任务分配的均衡性一般，但机床加工零件的总时间有些过大，生产效率太低，不满足生产厂家的要求，因此需要对问题二的模型一进行优化，因此建立了问题二的模型二。6.3 问题二模型二的建立（纵向多机床模型）6.3.1 确定目标函数：根据纵向分析法，在同一时刻，几台机床可以同时加工不同任务中的零件。由于在同一时刻并且是同一工序中，5个任务各自所有的零件均被机床加工，直到5个任务中的零件这个工序完成，再将所有零件转到下一个工序。这样一来只需分别求出每道工序中零件加工的总费用（运行成本和调度费用）（1）各道工序加工的运行成本表达式： 即 （2）各道工序的零件调度成本： 综上，加工零件的总费用为： 其中，为任务的编号，为机床的编号，为工序的编号，为零件调度一次的费用。为第个任务每个零件在第道工序中利用机床加工所需的运行成本，为第个任务第道工序机床加工零件的个数。为第道工序中任务的零件调度的次数。6.3.2确定约束条件： 6.3.4综上所述，最终确定问题二的单目标优化模型二 6.4 问题二模型二的求解：（1）算法的确定：算法同样确定为禁忌-遗传算法。（2）模型的求解结果：分析角度依然是从四个工序出发（横向分析），通过LINGO编程求解实现，得到问题二模型二的求解结果如下表6.3、6.4：表6.3 各道工序中5个任务各自加工时间（h）任务工序第一道工序第二道工序第三道工序第四道工序第1个任务40247264第2个任务1309191117第3个任务42918498第4个任务8414410860第5个任务50453550最大时间130144108117表6.4 模型二的求解结果：机床编号123456任务量(次数)402329283624总费用（元）1714000总时间（h）596（3） 各机床加工产品次数关系图（图 6.1）：图 6.1 各机床加工产品次数关系图问题二模型二的结果分析：（1）由表6.3可知，第一道工序中任务2的加工时间最长，为130小时，第二道工序中任务4的加工时间最长，为144小时，第三道工序中任务4的加工时间最长，为108小时，第四道工序中任务2的加工时间最长，为117小时。之所以出现这种情况，有两个原因：（1）任务2和任务4的加工零件数最多，分别为13,12，因此四道工序均是任务2,4的加工时间最长。（2）第一道工序中，任务2的零件选择机床加工的最短时间可为10小时，任务4是7小时，因此工序一中任务2时间较长。第二道工序中，任务2的零件选择机床加工的最短时间可为7小时，任务4是10小时，因此工序二中任务4时间较长。第三道工序中，任务2的零件选择机床加工的最短时间可为5小时，任务4是7小时，因此工序三中任务4时间较长。第四道工序中，任务2的零件选择机床加工的最短时间可为9小时，任务4是5小时，因此工序一中任务2时间较长。