机床调度策略的设计

三峡大学-数学建模，2011

机床调度策略的设计

摘要

本文从横向和纵向两个方面对机床的调度策略做出了分析。首先从工序的顺序（横向）方面作出了分析，五项任务依次完成，由此建立了模型一，即横向单机床优化模型；然后从五项任务的角度（纵向）作出了分析，四道工序依次执行，由此建立了模型二，即纵向多机床优化模型。最后运用禁忌-遗传算法，通过计算机编程求解。

对于问题一：横向考虑工序顺序，每个工序中只选择一台机床进行生产，然后五项任务依次执行此过程，完成产品的加工。纵向考虑五项任务同时执行，按照工序顺序进行。问题要求完成产品加工的总时间T最短，各个机床完成的工作量尽量均衡，以均衡度?作为衡量值。然后运用禁忌-遗传算法，通过MATLAB和LINGO编程求解得到模型一和模型二的结果。

通过比较问题一两个模型的求解结果（表5.3、5.7）可以看出，两个模型的均衡度相差不大，但是模型二结果中总时间远小于模型一。因此模型二是问题一的最优机床调度策略。总时间T2?477小时，均衡度?2?0.3125。

对于问题二：问题需要求解最小加工费用，属于单目标最优化问题，但是本文从实际出发，考虑加工费用最小的同时也使得总时间最短，并使各机床的任务量尽量均衡。同样经过横向和纵向分析，在问题一的基础上运用模型一和模型二来求解。

通过比较问题二的两个模型的求解结果（表 6.2、6.4 ）可以看出，两个模型的均衡度和总费用相差不大，但是模型二结果中总时间远小于模型一的，因此模型二求解的机床调度策略是最优的，总费用M?171.4万元，总时间T?596小时。

文章最后给出了对模型一和模型二的优点和缺点的评价，提出了模型的改进方案，并对本文建立的模型进行了推广。

关键字：机床调度 禁忌-遗传算法 均衡度 多目标最优化 横向纵向分析法

1

三峡大学-数学建模，2011

1 问题重述

1.1 问题提出背景

某工厂收到了5个客户提交的5种不同的加工任务订单, 每种任务中的每一件产品在加工时都要经过A,B,C，D，4道工序。这些工序由工厂的6台机床来完成。下表给出了各项任务的每件产品的每道工序可供选择的加工机床编号及其所需要的完成时间（单位：小时）

表 1 各项任务的相关参数 工 工任务 1 任序 序A （1, 3，5）B C D （1, 2，6） （2，4） （5，6） [5,7,12] （2, 3）[3,5,9] （3，5，6）[7,9] （1, 4，5）[8,13] （2，6）2 [12,10] （1, 4，5）[9,7,10] （3，6）[5,7,12] （1, 3，5）[11,9] （ 3，4）3 [6,7,6] （3, 4，5）[9,13] （2, 4）[8,9,12] （1, 3，6）[17,14] （1, 3，5）4 [9,7,12] （3，5）[10,12] （6）[8,7,9] （1，4，6） [5,7,5] （1，2，5）5 [8,10] [9] [5,7,12] [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 符号说明 第i个任务中每个零件在每个工序中通过某个机床加工所需的时间矩Ri(0) 阵

2

三峡大学-数学建模，2011

Qi(0) 第i个任务中每个零件在每个工序中通过某个机床加工所需的运行成本矩阵 机床加工零件所花的总时间 加工所有零件所需的总费用 任务分配的均衡度 第i个任务的需加工的零件总数 第i个任务中每个零件在第k道工序中利用机床j加工所需时间 第i个任务中零件在第k道工序中利用机床j加工所需的运行成本 零件在第k道工序中所需的调度费用 第j台机床加工的零件的总次数 第k道工序加工零件所需的总时间 第i个任务的第k道工序中选择机床j的台数 第k道工序中任务j的零件调度的次数 零件调度一次的费用 横向分析中的逻辑函数 纵向分析中的逻辑函数 T M ? wi tijk qijk mk Rj TK xijk yik p Cj pk 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。同样定义均衡度?作为各台机床工作量均衡程

3

三峡大学-数学建模，2011

度的指标。相对于横向分析法，纵向分析更能达到优化目的。为此我们建立了模型二，即纵向多机床模型。

针对问题二，求解目标有一个：加工费用最小。虽然只有一个求解目标，但是为了更符合实际需求，我们对问题的求解做出优化，即在使得加工费用最小的同时又满足所用时间最短。因此，同样做出如下分析。

（1）横向分析：分析角度同样从四个工序出发，因为每件产品在加工时在两台机床之间的调度需要1小时，故工序更换时要考虑调度带来的费用；另外，6台机床每小时的运行成本不同，所以机床的运行时间决定了总费用的大小。最后运用模型一（横向单机床模型）求解总费用M的最小值。

（2）纵向分析：分析角度仍然是从五个任务出发，五个任务同时进行，四个工序A、B、C、D分别按顺序进行。求解时按照模型二（纵向多机床模型）进行，考虑在工序更换时产生调度费用，并且6台机床每小时产生不同的运行成本。对于运行成本，可以转化为5个任务的零件运行成本总和，而每个任务的零件运行成本总和又可转化为每个零件在4道工序中运行成本总和。另外，每个零件在每道工序中加工时，机床需要选择，因此可以构造一个逻辑函数Cj（只可取1,0两个值），来进行选择。 对于调度费用，每个零件在每道工序中是否需要调度，要看每个零件在相邻工序中选择机床是否是相同的，若相同，则无需调度，若不相同，则需调度。在此也可构造逻辑函数Pk来进行选择。

4 数据分析

4.1问题一原始数据的处理

由已知数据（见附录表1）可知，公司接到5个任务，每个任务是加工一定数量不同种类的零件数，所有的零件可分配给6台机床加工。每个零件要经过A,B,C,D共4道工序，并且是按顺序的。每道工序只能选择j(j<6)台机床中的一台加工。1-6号机床每道工序加工每个零件所需的时间，因此可构造矩阵,具体如下：

(0)(0)(0)(0) Ri?(r(1),r(2),...,r(gi))

其中i=1,2,...,5,为任务的编号，gi?1,2,...,4为工序的编号，R为每个零件在每道工序中被每台机床加工的时间。若机床可供零件选择，则时间就为对应的给出时间，若机床不可被零件选择，则时间就为?。如：

?5????7?????12???35???9?7?9????????????8??13? R1(0)

继续构造矩阵A,具体如下：

(0)(0)(0)(0) Ai?(a(1),a(2),...,a(gi))

其中i=1,2,...,5,为任务的编号，gi?1,2,...,4为工序的编号，A为逻辑函数，当零件在第gi道工序选择机床j时，则为1，否则为0 4.2 问题二原始数据的处理

4

三峡大学-数学建模，2011

由已知数据（见附表2 ）可知，每个零件在每道工序中只能选择j(j<6)台机床中的一台加工，而万一零件在换工序的同时换了机床，则还需调度费用，因此必须分调度还是未调度。

4.2.1 若调度了，则构造矩阵Q,具体如下：

Qi(0)?(q(0)(1),q(0)(2),...,q(0)(gi))

其中i=1,2,...,5,为任务的编号，gi?1,2,...,4为工序的编号，Q为机床在每道工序中加工每个零件运行所需的总费用，若机床可供零件选择，则运行总的费用就为对应的给出费用，若机床不可被零件选择，则费用就为?。如：

?10????10.5?????12?????912.6????????

?10.8????8??7.2?10.4?6? Q1(0)4.2.2若未调度：

则只有当相邻工序有相同机床的选择时，才可以进行调度。机床在每道工序中加工每个零件运行所需的总费用与调度时的相同。

5 问题一的解答

5.1 均衡度的定义

定义均衡度?为六台机床中的最大任务量与最小任务量差值与最大任务量的比值，

maxRj?minRj??

maxRj其中Rj(j?1,2,...,6)为第j台机床加工的零件的总次数。

模型一 横向单机床模型

5.2 模型一的建立 5.2.1确定目标函数

题目有两个目标，即零件加工的最小时间与任务分配的均衡度。 假设任务是按序完成的，零件在每个任务每道工序加工也是按序的，且零件未同时加工。加工零件所花总时间相当于求每个零件单独加工的总时间，表达式如下：

T????tijkCjwi

j?1i?1k?1654其中，i为任务的编号，j为机床的编号，k为工序的编号，wi为第i个任务的零件总数，tijk为第i个任务中的每个零件在第k道工序中利用机床j加工所需时间。当零件选择了机床j，则Cj?1，当零件未选择机床，则Cj?0。 5.2.2确定约束条件:

5

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新幼儿教育机床调度策略的设计 全文阅读和word下载服务。