机床调度策略的设计

三峡大学-数学建模，20111机床调度策略的设计摘要本文从横向和纵向两个方面对机床的调度策略做出了分析。首先从工序的顺序（横向）方面作出了分析，五项任务依次完成，由此建立了模型一，即横向单机床优化模型；然后从五项任务的角度（纵向）作出了分析，四道工序依次执行，由此建立了模型二，即纵向多机床优化模型。最后运用禁忌-遗传算法，通过计算机编程求解。对于问题一：横向考虑工序顺序，每个工序中只选择一台机床进行生产，然后五项任务依次执行此过程，完成产品的加工。纵向考虑五项任务同时执行，按照工序顺序进行。问题要求完成产品加工的总时间T最短，各个机床完成的工作量尽量均衡，以均衡度作为衡量值。然后运用禁忌-遗传算法，通过MATLAB和LINGO编程求解得到模型一和模型二的结果。通过比较问题一两个模型的求解结果（表5.3、5.7）可以看出，两个模型的均衡度相差不大，但是模型二结果中总时间远小于模型一。因此模型二是问题一的最优机床调度策略。总时间4772T小时，均衡度125.302。对于问题二：问题需要求解最小加工费用，属于单目标最优化问题，但是本文从实际出发，考虑加工费用最小的同时也使得总时间最短，并使各机床的任务量尽量均衡。同样经过横向和纵向分析，在问题一的基础上运用模型一和模型二来求解。通过比较问题二的两个模型的求解结果（表6.2、6.4）可以看出，两个模型的均衡度和总费用相差不大，但是模型二结果中总时间远小于模型一的，因此模型二求解的机床调度策略是最优的，总费用.4171M万元，总时间596T小时。文章最后给出了对模型一和模型二的优点和缺点的评价，提出了模型的改进方案，并对本文建立的模型进行了推广。关键字：机床调度禁忌-遗传算法均衡度多目标最优化横向纵向分析法三峡大学-数学建模，20112工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,13]2（2,3）[12,10]（3，5，6）[9,7,10]（1,4，5）[5,7,12]（2，6）[11,9]3（1,4，5）[6,7,6]（3，6）[9,13]（1,3，5）[8,9,12]（3，4）[17,14]4（3,4，5）[9,7,12]（2,4）[10,12]（1,3，6）[8,7,9]（1,3，5）[5,7,5]5（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符号说明(0)iR第i个任务中每个零件在每个工序中通过某个机床加工所需的时间矩阵任务序工序任三峡大学-数学建模，20113(0)iQ第i个任务中每个零件在每个工序中通过某个机床加工所需的运行成本矩阵T机床加工零件所花的总时间M加工所有零件所需的总费用任务分配的均衡度iw第i个任务的需加工的零件总数ijkt第i个任务中每个零件在第k道工序中利用机床j加工所需时间ijkq第i个任务中零件在第k道工序中利用机床j加工所需的运行成本km零件在第k道工序中所需的调度费用jR第j台机床加工的零件的总次数KT第k道工序加工零件所需的总时间ijkx第i个任务的第k道工序中选择机床j的台数iky第k道工序中任务j的零件调度的次数p零件调度一次的费用jC横向分析中的逻辑函数kp纵向分析中的逻辑函数3问题分析本题是要根据所给的任务订单，将任务合理的分配到有限个数的机床进行加工。现在知道，工厂收到的5种不同的任务订单中,每种任务中的每一件产品在加工时都要经过A，B，C，D，4道工序，这些工序由工厂的6台机床来完成。加工零件在每道工序中从所提供的机床中进行选择，且对应地选择一台机床。基于所给的数据，本题提出了两个问题，针对这两个问题，我们分别做出了横向和纵向的分析：针对问题一，求解目标有两个：最短时间，最好的均衡度。(1)横向分析：分析角度从四个工序出发，因为工序的有序性（假设3），所以在计算一项任务完成的时间时，工序从A到B，再到C、D，在每个工序中只选择一台机床进行加工，按照这个顺序来累积每个工序的时间。再将5项任务的加工时间累和，就可以得到优化目标总时间T了。另外还要求每个机床的任务量尽量均衡，就定义均衡度作为衡量指标。这样就建立了模型一，即横向单机床模型。(2)纵向分析：分析角度是从五个任务出发的，即进行工序A时，任务1，2，3，4，5同时进行工序A的加工，各工序中所有机床都运行，充分利用，零件在每道工序中都根据自身可供选择的机床进行加工，若机床被占用，则不选择这台机床，这样就能很大程度上缩短加工时间。计算时只需要取5项任务中时间最长的时间作为最后的总时间T。同样定义均衡度作为各台机床工作量均衡程三峡大学-数学建模，20114度的指标。相对于横向分析法，纵向分析更能达到优化目的。为此我们建立了模型二，即纵向多机床模型。针对问题二，求解目标有一个：加工费用最小。虽然只有一个求解目标，但是为了更符合实际需求，我们对问题的求解做出优化，即在使得加工费用最小的同时又满足所用时间最短。因此，同样做出如下分析。（1）横向分析：分析角度同样从四个工序出发，因为每件产品在加工时在两台机床之间的调度需要1小时，故工序更换时要考虑调度带来的费用；另外，6台机床每小时的运行成本不同，所以机床的运行时间决定了总费用的大小。最后运用模型一（横向单机床模型）求解总费用M的最小值。（2）纵向分析：分析角度仍然是从五个任务出发，五个任务同时进行，四个工序A、B、C、D分别按顺序进行。求解时按照模型二（纵向多机床模型）进行，考虑在工序更换时产生调度费用，并且6台机床每小时产生不同的运行成本。对于运行成本，可以转化为5个任务的零件运行成本总和，而每个任务的零件运行成本总和又可转化为每个零件在4道工序中运行成本总和。另外，每个零件在每道工序中加工时，机床需要选择，因此可以构造一个逻辑函数jC（只可取1,0两个值），来进行选择。对于调度费用，每个零件在每道工序中是否需要调度，要看每个零件在相邻工序中选择机床是否是相同的，若相同，则无需调度，若不相同，则需调度。在此也可构造逻辑函数kP来进行选择。4数据分析4.1问题一原始数据的处理由已知数据（见附录表1）可知，公司接到5个任务，每个任务是加工一定数量不同种类的零件数，所有的零件可分配给6台机床加工。每个零件要经过A,B,C,D共4道工序，并且是按顺序的。每道工序只能选择j(j6)台机床中的一台加工。1-6号机床每道工序加工每个零件所需的时间，因此可构造矩阵,具体如下：(0)(0)(0)(0)((1),(2),...,())iiRrrrg其中i=1,2,...,5,为任务的编号，1,2,...,4ig为工序的编号，R为每个零件在每道工序中被每台机床加工的时间。若机床可供零件选择，则时间就为对应的给出时间，若机床不可被零件选择，则时间就为。如：(0)1535779128913R继续构造矩阵A,具体如下：(0)(0)(0)(0)((1),(2),...,())iiAaaag其中i=1,2,...,5,为任务的编号，1,2,...,4ig为工序的编号，A为逻辑函数，当零件在第ig道工序选择机床j时，则为1，否则为04.2问题二原始数据的处理三峡大学-数学建模，20115由已知数据（见附表2）可知，每个零件在每道工序中只能选择j(j6)台机床中的一台加工，而万一零件在换工序的同时换了机床，则还需调度费用，因此必须分调度还是未调度。4.2.1若调度了，则构造矩阵Q,具体如下：(0)(0)(0)(0)((1),(2),...,())iiQqqqg其中i=1,2,...,5,为任务的编号，1,2,...,4ig为工序的编号，Q为机床在每道工序中加工每个零件运行所需的总费用，若机床可供零件选择，则运行总的费用就为对应的给出费用，若机床不可被零件选择，则费用就为。如：(0)1106912.610.510.81287.210.4Q4.2.2若未调度：则只有当相邻工序有相同机床的选择时，才可以进行调度。机床在每道工序中加工每个零件运行所需的总费用与调度时的相同。5问题一的解答5.1均衡度的定义定义均衡度为六台机床中的最大任务量与最小任务量差值与最大任务量的比值，maxminmaxjjjRRR其中(1,2,...,6)jRj为第j台机床加工的零件的总次数。模型一横向单机床模型5.2模型一的建立5.2.1确定目标函数题目有两个目标，即零件加工的最小时间与任务分配的均衡度。假设任务是按序完成的，零件在每个任务每道工序加工也是按序的，且零件未同时加工。加工零件所花总时间相当于求每个零件单独加工的总时间，表达式如下：654111ijkjijikTtCw其中，i为任务的编号，j为机床的编号，k为工序的编号，iw为第i个任务的零件总数，ijkt为第i个任务中的每个零件在第k道工序中利用机床j加工所需时间。当零件选择了机床j，则1jC，当零件未选择机床，则0jC。5.2.2确定约束条件:三峡大学-数学建模，2011661123451,018,13,7,12,5jjjCC5.2.3综上所述，所得问题一的多目标优化模型一:minminT61123451,0.18,13,7,12,5jjjCstC5.3模型一的求解:（1）多目标转化为单目标：问题一需要求解的目标有两个，属于多目标最优化[1]的求解，因此需要将多目标优化模型转化为单目标优化模型进行求解，转化后的模型求解目标如下:min()minmax(1)T（2）确定算法：本文研究的对象这是机床调度问题，目的是求最小的加工时间，因此需选择每个零件相应的加工工艺路线，安排零件在机床上的加工顺序，确定每台机床的最后完工时间，则最大的完工时间即为本题最小的完工时间。因此设计嵌套的禁忌-遗传算法[2]，首先利用禁忌算法搜索零件的加工工艺路线，在工艺算法确定的情况下再用遗传算法[3]每个零件的加工顺序。Ⅰ).禁忌算法设计：①.解的编码及规模：编码采用自然数，共有n个零件待加工，编码长度为n。比如有N个零件待加工，每个零件可选的加工路线有1,2,,(...,...,)iNpppp，其中(1)iipp，表示第i个零件的加工路线数，则N个零件的编码为12(,,...,,...,)iNaaaa,其中1iiap。同时对每个零件的加工路线按加工时间的长短进行自然编码。这样生成初始解群，对每个零件尽量采用较小的工艺路线编码。初始解规模定为N。②.适配值函数：本组工艺路线安排下，经遗传算法求得的最小完工时间。Ⅱ).遗传算法设计：①.遗传编码及解码算