任务分配到机床
摘要
本文解决的是机床生产调度的问题，目的是使产品加工路径的组合优化。对于本文所研究的机床任务的合理调度问题，由于生产方式的不确定，我们根据A，B，C，D这4道工序是否有序进行了分类研究，并分情况得到了最优解或近似最优解，制定出了不同情况下的合理调度方案。
对于问题一：在工序无序的情况下，问题转化为一个指派问题，以完成任务耗时最长的那台机床的运行时间作为指标，以该指标最小作为目标函数，建立了一个0-1整数规划模型，用Lingo求解得最短加工时间为233h各机床加工时间的均衡度为3.8%。
在工序有序的情况下，问题一转化为一个柔性作业车间调度问题，此时生产调度的任务就是：确定产品的加工路径和每一工序的加工开始时间，并使产品通过系统的时间（Makespan）最小。运用遗传算法建立模型，绘制出最佳调度的甘特图，并得到加工时间的近似最优解为250h，各机床加工时间均衡度为1.6%，均衡度很高；与无序情况所得最优解相比，其近似度为92.7%，具有较好的有效性。
对于问题二：在工序无序的情况下，该问题仍为一个指派问题，在加入调度费用与运行费用的条件下，我们利用理想点法将这两个指标的双目标问题转化为单目标规划模型来进行求解，建立了一个0-1整数规划模型，用Lingo求解得加工时间为510h，总费用为1784600元。
在工序有序的情况下，我们运用蚁群算法建立模型，经过选工序，计算加工工序k的机床的空闲时间段和加工序列，计算可选工序的EAPT和信息素的积累等过程，得到加工时间为441h,总费用为1799000元。为了进一步分析该算法的有效性，我们还进行了实例规模较大的计算机仿真试验。
我们在模型的改进和推广里对模型四提出了一种评价方法，力求使一群算法的精度进一步提高，以实现更大规模的应用。
关键词： 指派问题 柔性调度 理想点法 遗传算法 蚁群算法
1
1.问题重述
1.1问题背景
车间生产调度是制造系统的基础，生产调度的优化方法是先进制造技术的核心技术。其中，作业车间调度是一个加工资源分配问题，它根据现有约束条件，合理安排生产资源、加工时间、加工顺序等，以获得最优的成本或效率。在生产过程中，工件往往是成批生产的，因此研究批量调度的优化方法，对于先进制造企业的现代化具有重要的理论价值和实际意义。 1.2问题相关信息
现某工厂收到了5个客户提交的5种不同的加工任务订单，每种任务中的每一件产品在加工时都要经过A，B，C，D4道工序。这些工序由工厂的6台机床来完成，各项任务的每件产品的每道工序可供选择的加工机床编号及其所需要的完成时间均已知，具体数据见附件表1.1.这5个客户此次的任务订单量分别为：8,13,7,12,5。
1.3本文所需解决的问题
问题（1）假设你是该工厂的生产主管，为了将任务合理地分配到各机床要求：
①设计出一种用最短的时间完成订单的方案； ②同时保证各机床任务量尽可能均衡。
问题（2）假设每件产品在加工时在两台机床之间的调度需要1小时，每件的调度费用为1000元，6台机床每小时的运行成本分别为2000元,1800元,1500元,1200元，1000元，800元，此种情况下，再次设计合理的机床任务分配方案，保证生产费用最小。
2.模型的假设与符号说明
2.1模型的假设
假设1：工序的加工时间是确定的工序的装卸时间计算在加工时间内； 假设2：不同的工件之间没有前后约束； 假设3：每台机床同一时刻只能加工一个工件。 假设4：批量启动时间是确定的；
假设5：在零时刻，所有的工件都可以被加工； 假设6：工件的运输时间被考虑到批量启动时间内；
假设7：工件的生产批量原则是确定的，均与题中所给数据一致； 假设8：第一问中不考虑工件在机床间的调度时间和调度费用；
假设:9：工序一旦开始进行加工，中途即不再有任何意外情况使其中断。
2
2.2符号说明
符号 符号说明 表示是否由第i台机床去完成第j项任务 表示第i台机床完成第j项任务的时间代价 表示加工一件产品的机床数 表示所有机床的运行成本 表示所有产品的调度费用 表示第i台机床的运行时间 表示总的生产费用 表示第i台机床加工第k件产品的第m道工序 表示第i台机床加工第k件产品 表示加工第k件产品的机床数 表示生产第k件产品的调度费用 表示SPT规则的评价函数 表示LPT规则的评价函数 表示工序Oij的加工时间 xij tij n P Q Ti Y aikm bik ck qk fSPT?Oij? fLPT(Oij) Tij maxMachineTime(Oij) 表示与工序Oij同机床加工的加工时间最长的工序的加工时间 表示设备Mi上工件的加工次序 表示工件平均流通时间 表示工件平均延误时间 表示第j个零件的l+1道工序的开始加工时间 ci MFT MT tsj,l?1 3
3. 问题分析
本题研究的是柔性作业机床的任务分配和调度FJSP(Flexible Job-shop Scheduling Problem) 的数学建模问题，该问题的区别于一般作业机床调度问题JSP在于它取消了每道工序只能在一台机器上加工的限制。工作车间生产调度的目的是使工件加工路径的组合优化，以确保总加工时间最短，总生产费用最小，并且各机床任务量尽可能均衡。然而由于本题生产方式的不确定，并且5位客户的任务订单量都较小，根据生活实际经验，我们判断该产品的生产并非大批量流水作业，因此考虑A，B，C，D等4道工序既可能无固定加工顺序，也可能有固定加工顺序。故我们根据工序是否有序进行分类研究，从而分别得出最优解和最佳调度方案。 3.1问题一的分析
若此四道工序可无序进行加工生产，目标为完成任务时间最短，与此同时保证各机床任务量尽可能均衡。所有任务中共45个产品，每个产品需要加工4道工序，将每个产品的一道工序看做一个任务单元，则共有180个相同的任务单元，每个任务单元逐步筛选分配到各个机床。由此我们可以将其转化为一个指派问题，以完成任务耗时最长的机床运行时间为指标，以该指标最小作为目标函数，建立一个0-1整数规划模型进行求解。在该指标减少的同时，完成该指标的机床的工作量将被分配到工作量相对较少的机床上，由此以该指标最少作为目标，同时对各机床任务量均衡度进行优化。
若此四道工序须有序进行，则该问题即为一个较复杂的柔性制造系统中的作业车间调度问题，工序有序的FJSP问题可简单的描述为：n个产品在m台机床上加工。取生产调度的优化目标为：在加工一组产品时，产品通过系统的时间（Makespan）最小。此时生产调度的任务就是：确定每个产品的每道工序在哪台设备上加工，每台设备上各个任务单元的加工先后顺序，并使Makespan最小。此外生产调度还必须满足生产系统中的约束条件，约束条件包括：
（1） 每台机器同一时刻只能加工一件产品，而且必须在当前加工的产品完成后
才能加工其他产品；
（2） 每件产品由多道工序组成，加工工艺预先确定了各工序的先后顺序；同一
产品的工序存在先后顺序约束，不同产品的工序之间没有约束； （3） 每道工序可以在多台机器上加工，加工时间长短由机器的性能和功能决定；
据此，我们可以采用遗传算法、通过计算机仿真，得到相应问题的近似最优解。并以无序情况下在第一问中得到的结果作为下限做近似度分析。
4
3.2问题二的分析
若此四道工序可无序进行加工生产，目标为总费用最少，与此同时尽量减少工作时间。此问题的费用来源于机床的加工费用和每件产品在各台机床之间的调度费用。因此需要控制机床的运行时间和产品的调度次数来实现总费用最小，以完成任务的机床工作时间最少和总费用最小作为指标，利用理想点法将这两个指标的双目标问题转化为单目标规划模型来进行求解。
若此四道工序须有序进行，则仍为柔性制造系统中的作业车间调度问题。我们可以考虑运用仿生智能算法中的蚁群算法建立模型，采用一种新的启发信息：最早允许加工时间(EAPT)，并在模型中加入适量的随机信息，使模型避免陷入局部最小的陷阱。然后进行计算机仿真，用仿真表明算法的可行性，并比较采用传统启发信息与新的启发信息的仿真结果，以此表明新的启发信息的优点。
4.问题一的解答
4.1 数据处理
由各项任务的每件产品的每道工序可供选择的加工机床编号及其所需要的完成时间表：（见附录）
由题目表中所给数据可知，各任务每道工序可供选择的加工机床个数不同，为便于求解，将不能加工该任务该工序的对应加工时间记为无穷大，例如，对于任务1的工序A，可供选择的加工机床号为(1,3,5),对应的加工时间(5,7,12)，处理后的数据为：可供选择的加工机床号为(1,2,3,4,5,6),对应的加工时间为（5,?,7,?,12,?)。 指标一：任务总数
任务总数j的统计和计算：任务总数j=订单任务总量?工序数，即：
j=(8+13+7+12+5)?4=180
指标二：完成时间最长的机床
问题要求所有机床的最短完成时间，首先要找出最后完成任务的机床，则要求所有机床的最短完成时间就是求此最长时间的最小值。最长的完成时间为：
tmax指标三：最短完成总时间
?180??max ??xijtij? 1?i?6?j?1?我们用Z来表示总的预期时间效益，要求最短完成所有工序的总时间，则
minZ?max?tijtij为一个基本可行解中非零分量的系数?，由此：
5
?180?minZ? max ??xijtij?
1?i?6?j?1?4.2 模型一的建立：0-1整数规划模型（针对无序加工方式）
在工序无先后加工顺序的情况下，任务分配问题是一类典型的组合优化问题，不同的分配花费不同的代价，任务分配问题就是要找到一种所花费代价最小的分配方案。
4.2.1确定目标函数：
下面建立上述指派问题的0-1整数规划模型。我们用Z来表示总的预期时间效益，则minZ?max?tijti为一个基本可行解中非零分量的系数?。现有可完成j180项任务单元的6台机床A1,A2,…,A6,第i台机床和第j项任务单元之间的执行关系xij，即用xij表示第i台机床加工第j项任务单元，以及第i台机床完成第j项任务单元所需的时间tij（i?1,2,...,6;j?1,2,...,180）。若第i台机床完成第j项任务的时间tij?o，则可构成时间代价矩阵T?(tij)6?180。
据此建立目标函数（一）为：
?180?minZ? max ??xijtij?
1?i?6?j?1?4.2.2确定约束条件：
?1,表示第i台机床去完成第j项任务设xij??
?0,表示第j台机床不去完成第j项任务其中i?1,2,...,6;j?1,2,...,180，则分配问题即是求解任务分配阵X?(xij)6?180同时问题的约束有：对于一项任务来说，只可能被分配到一台机床上，即形成数学约束表达?xij,i?1,2,...,6。这里的约束条件是一个非线性规划，其目标函数
j?1180也即min Z=max{
tij,
tij为一个基本可行解中非零分量的系数}，，
tij?0,i?1,2,...,6;j?1,2,...,180xij?X,tij?T。
因此，总的约束条件为：
?6j?1,2,...,180??xij?1,?i?1 s..t?1,第i台机床去做第j项任务；?x???ij??0,第i台机床不做第j项任务。?6
4.2.3综上所述，得到问题一的0-1整数规划模型：
?180?minZ? max ??xijtij?
1?i?6?j?1?6?xij?1,??i?1? s..t?1,第i台机床去做第j项任务；?x???ij??0,第i台机床不做第j项任务。?
4.3模型一的求解：
我们采用启发式算法（近似）中的逐步改进算法对上述模型求解，具体算法步骤如下：
1）让每项任务由所需时间最少的机床来做；
2）计算出每台机床的完成时间，找出完成指派工作所需时间最多的机床（最繁忙者）与所需时间最少的机床（最闲暇者）；
3）若最繁忙者所做的工作均标有?，则停止，此指派方案即为一个近似最优方案；
4）求最繁忙者所做的每个工作的工作时间与最闲暇者的工作时间差，其绝对值最小的工作转给最闲暇者做。
5）若此二台机床完成时间的较大者变小，记录新方案，清除标记，转2)；否则，维持原方案，并将该工作记上标记?，转4）。
按逐步改进算法得到最优化结果如下表1： 机床1 任务1 8 A, 8 B 任务2 13 C 任务3 7 C 任务4 4 C 任务5 3 D 总时间/h 232 机床2 8 C 1 A ---- 12 B 5 D 233 机床3 ---- 12 A 5 B 4 C 5 A 233 机床4 ---- ---- 2 A, 7 D 12 A 5 C 231 机床5 8 D 13 B 5 A 9 D ---- 230 机床6 ---- 13 D 2 B 4 C 5 B 224 4.4模型一的结果分析：
表中数据的含义是某工序与该工序进行次数的乘积，如：8 A, 8 B表示在机床1上完成任务1的8道A工序与8道B工序；13 B表示在机床5上完成任务2的13道B工序……机床1完成任务的总时间为232小时，机床2完成所有任务的总时间为233小时，机床3完成所有任务的总时间为233小时，机床4完成所有
7
任务的总时间为231小时，机床5完成所有任务的总时间为230小时，机床3完成所有任务的总时间为224小时。
其中，机床2和机床3的总时间最大，均为233小时，因此问题一的最短时间即为233小时。 4.4.1均衡度计算
?0?max(Ti)?min(Ti)1?i?61?i?6maxTi1?i?6=233?224=3.8%
233据上面计算发现，?0仅为3.8%，值很小，均衡度较好，由此可见任务分配很均衡。
4.5模型二的建立：遗传算法模型
在工序规定了先后加工顺序的情况下，机床任务的调度即属于非常普遍的柔性生产调度问题。该类生产系统的特点是工件进入生产系统的入口和出口不固定，而且不同的工件有不同的加工工艺路线，同种工件也允许有不同的工艺路线。我们经过反复研究，将遗传算法与生产工艺结合，提出了一种新的遗传调度方法，通过设计适合表达不同加工机床上不同零件的加工顺序的染色体，，变随机生成染色体为有目的生成染色体，，加速了搜索最优解的速度，使得作业车间的柔性化制造系统（FMS）中最难解决的问题之一——车间调度得到比较可行的实施。 4.5.1遗传算法的基本思想：
模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，一个备选解被称为一个染色体，每个染色体由若干基因组成，每个基因表示一个数值，若干个染色体组成一个群体。运用遗传算法的过程就是对备选解进行迭代的过程，没爹带一次成为一代，在完成一次迭代后，利用一定的评价函数对当前的群体进行评估，并在此基础上产生下一代。初始群体可根据经验主观选取，群体容量为C。算法的容量如图1所示：
以上的迭代运算过程直到找到一个满意的解或者达到预先设定的迭代次数为止，算法中的评价函数主要作用是：对当前群体中的每个染色体性能进行评价，保留高性能的染色体，除去低性能的染色体，并通过遗传算子补充一些新的染色体，使群体的总性能不断得到改善，最后得到非常优秀的群体，满足问题的求解要求。
8
编码和初始群体的生成评价个体的适应度满足迭代终止条件N遗传操作Y结束产生新一代群体 图1 算法流程图
遗传算子主要包括选择、交叉和变异。选择操作的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代繁殖子孙。交叉就是利用优良个体进行杂交产生新个体的随机过程。变异模拟了生物进化中的基因突变过程。 4.5.2编码过程：
设5份订单的加工工序为：
ma,?P1:?P:m,2b??.?.?..???P5:mc,,md,,mgme,,mh... ...mf,,mi,生产调度的目标就是确定每台设备上各个工件的加工先后次序，以保证工件在系统中的通过时间最短。
根据这一目标，设计N组染色体，以表示每台设备上工件的加工次序，染色体Ci（i=1,2,?,6）表示设备Mi上工件的加工次序。
Ci:PPv,...,Pw u,其中，1?u,v,w?5,若取遗传群体为C，按照遗传算法应该首先随机产生C
9
组染色体，即：
?C11,C12?C,C2122??.?.?..???Cc1,Cc2..C16..C26........Cc6 （3）
公式（3）中的每一行表示一种在整个加工系统（6台机床）上工件的次序组合，展开来看即为：Pu1,Pv1,...,Pw1,Pu2,Pv2,...,Pw2,...,Pu6,Pv6,...Pw6，其余的c-1行按上面的形式依次展开。
计算每个染色体确定的加工次序的情况下系统的通过时间，据此选出当前一代染色体中最为优秀的若干组染色体作为繁殖后代的双亲，形成交配池，然后通过遗传算子产生新的染色体，形成下一代染色体的群体。
为了有效地寻找最优解，在染色体（2）的生成过程中，将充分考虑工件的加工工艺特点。由于每道工序必须在它的前面所有工序全部加工完毕的情况下才能加工，因此，为了减少设备的等待时间，应该尽量将工序靠前的工件安排在染色体靠前的位置加工，假设在设备Mi上有K件工件需要加工，每种工件Pi其前面的生产周期之和为ti，ti值越大，工件Pi在染色体中的位置越应后，令
T??tj （4）
j?1180T为所有K个工件前面所有工序生产周期之和，aj?(1?tj/T)，aj为工件Pj应该排在染色体前面的加权系数，其和：
?aj?1180j?170
据此可以计算每个工件排在染色体第一位的概率是：
Pj[1]?aj170j?1,2,...,180
在染色体生成时将以此还绿首先确定第一个工件，然后再计算各工件处于第2位的概率，即：
Pj[2]?aj180?aij?1,2,...,180 （6）
式中，设Pi为排在染色体第一位的工件，以（6）式确定排在第2位的工件，
10
同理，可以确定以后个工件的位置。这种确定染色体的方法将有利于减少群友的时间。
为了比较已经生成了的染色体的优劣，需要计算每一组染色体确定的系统的通过时间，即
tsmax?MAX?ts1,ts2,...,tsn?
上式中第i台机床加工完所有工件所用时间为tsi。由于车间生产系统中各设备可同时加工不同工件，表现为时间上的并行关系。因此，一般的程序设计方法很难解决生产过程的仿真问题，只有利用巡回扫描模式才能解决这个问题。即程序不是只执行一次，而是不断地循环执行，直到所有设备上工件都加工完毕为止。 4.5.3解码过程：
所谓解码算法就是根据染色体的编码和柔性调度问题的约束条件推导出可行的调度方案（问题的可行解），解码方法如下：
染色体：B?工序：11233221AAABBCCC...?3...
其含义为：在调度生成过程中，首先安排第2个工件的第1道工序，接着安排第1个工件的第1道工序，然后安排第1个工件的第2道工序，按这种方式，依次从左到右将染色体上的工序都安排完为止。最终生成的调度方案(问题的可行解)为：机床的加工顺序是2—1—3，机床2上的加工顺序是1—2—3，机床3上的加工顺序是1—2—3。 4.5.4交叉过程：
众所周知，对于调度问题，交叉操作是最棘手的难题，由于本算法用染色体确定工序的优先权，然后用一次通过优先分配启发式算法产生调度，因此不要求双亲和后代中部分调度的工序顺序一致，故采用简单的单断点交叉法。
在变异时可能产生非可行解(产生某个零件的某个工序所分配的加工机床为非加工机床),因此要进行解的可行性检查,如果产生非可行解,则不进行变异。本文使用规划-资源算子[4 ]作为交叉操作时的算子,规划-资源算子就是将零件、工序和机床作为一个操作单元进行交叉操作,同时改变零件、工及加工该工序所使用的机床,这样零件的加工顺序在交叉过程中不发生变化,避免了在交叉过程中破坏工序约束,因此不会产生非可行解。应用规划-资源算子的交叉操作如下：
11
交叉点
父本1：（1,1,1） （1,2,3） （1,3,4） （2,1,3）5 （2,2,3）（2,3,5）（3,1,1) (3,2,5)父本2：（1,1,3） （1,2,1） （1,3,3） （2,1,1）5 （2,2,1）（2,3,4） (3,1,1) (3,2,3)子代1：（1,1,1） （1,2,3） （1,3,4） （2,1,3）?（2,2,1） （2,3,4）（3,1,1) (3,2,3)子代2：（1,1,3） （1,2,1） （1,3,3） （2,1,1）?（2,2,3） （2,3,5）（3,1,1) (3,2,5)4.5.5评价过程：
本题我们采用的评价调度性能的指标是最小化零件平均流通时间(makespan)。Makespan是指完成一批零件所有n个工序需要的时间,这里主要采用资源负荷均衡和最小化零件平均流通时间作为评价指标,同时要求零件不超期。即在资源负荷平衡的前提下,尽量使makespan最小,同时使零件尽量不超期,还要满足零件工序的顺序约束。
对于超期零件则在性能指标中加入惩罚项。调度目标是使工件平均流通时间
MFT和工件平均延误时间MT的加权之和最小,其性能指标为：
)f1?minW(1?MT?WT2?MFMFT?maxLi
i?MMT???max(0,tcj?tdj)
j?Ntfj,l?tsj,l?1j?Nl?1,2,...,Oj?1
其中，W1,W2权值(W1?W2?1)，反映调度目标中MT和MFT的侧重诚度。Li为第i台机床完成该批工件所有操作的加工时间，包括工件加工时间和调度时间；
tcj，tdj分别为第j个工件完成加工的时间和交货时间，?为加权系数，tfj,l为第j个零件的第l道工序的加工完成时间，tsj,l?1为第j个零件的l+1道工序的开始加工时间，Oj为第j个工件的操作数。 4.5.6重迭调度：
根据FMS的资源情况和调度目标的要求,将生产任务分成不同的零件批次,每一零件批次都按顺序进入系统。系统的调度时间相应分成许多调度阶段,每一调度阶段对应一个零件批次。这样就把具体调度时间缩短了。调度时间缩短能够减轻系统的调度复杂程度,增加调度的准确性,有利于提高系统生产效率和资源
12
利用率,但是零件在系统中的流通时间仍然没有缩短。为了进一步缩短系统的流通时间,应用重迭调度[5]的方法安排相邻零件批次的加工过程。
重迭调度是在相邻两批零件的调度过程中,在安排一批零件的加工作业之前,就考虑前一批零件的生产安排情况,不等待前一批零件都完成加工才安排该批零件的加工,只要某台设备所承担的前一批次任务完成而且设备有空闲,下一批零件中分配到该设备的零件就可以进入系统进行加工。重迭调度后得到机床利用率如表2所示。
表2 机床利用率
重迭调度 否 是
机床1 0.417 0.444
机床2 0.522 0.556
机床3 0.504 0.537
机床4 0.539 0.574
机床5 0.422 0.449
机床6 0.537 0.526
4.6模型二的求解
为了对模型二进行求解，我们采用计算机仿真的方法，得到重迭调度后最小批量为5的最佳调度甘特图，如下：
机床6 机床5机床4 机床3 机床2机床1 05B5-3B1A4-5A53B3-3C49B22C4-2C52C3-D17D27D1-2D411A1-B15B4-C1C1-3C5-D34D37A2-B23B2-4B3-C46C42D3-4D46A2-B17B46C16D28A1-6A34B1-C22C2-4C36D4-5D54080120 160200240图2 重迭调度后最小批量为5的最佳调度甘特图时间
4.7模型二的结果分析
整理模型二得到的最佳调度甘特图，得到机床和任务匹配的对应结果，具体时间和费用列得下表2:
机床1 机床2 机床3 13 机床4 机床5 机床6
任务1 任务2 任务3 任务4 任务5 总时间/h 8A, 4B 13 C 6A, 4C 6 D 5 D 250 1B, 6C 6A, 6D ---- 7 B ---- 250 ---- 2 C 12A, 3B ---- 4B, 2D 1A,1C,5D 7C, 4D 11A, 5B ---- 3 C 247 246 8 D 10 B 2 C 1A, 2D 5A 248 3 B 7 D 3 B 5 C 5B, 2C 248 由表中数据得，最短总时间应为机床1和机床2的250小时，由于遗传算法得到的结果是近似最优解，我们因此以无序情况下的结果T0为下限，对其进行近似度分析如下：
?T?T0?近似度S0??1???100%T0?????250?233???1???100%
233?????92.7%根据以上近似度分析，该结果具有很好的近似度，可以判断遗传算法对此问题有可行性与有效性，优化组合效果较好。 4.8均衡度计算
?0?max(Ti)?min(Ti)1?i?61?i?6maxTi1?i?6=250?246=1.6%
250?0很小，可见任务分配很均衡。
5.问题二的解答
5.1模型三的建立：0-1整数规划模型（针对无序加工方式）
时间最短的目标函数为f1，最优解为f1*，费用最少的目标函数为f2，最优解为f2*，这是一个双目标问题，为同时使时间和费用都比较小，用理想点法将双目标转化为单目标求解，确定目标函数为：
f?(f1?f1*)2?(f2?f2*)2 5.1.1确定目标函数
在模型一的基础上，对于第二问中加入了调度费用的情况，据生产费用给出目标函数时，总生产费用Y被分为两部分：机床运行费用P和产品调度费用Q。即：
14
minY?P?Q
5.1.2确定约束条件
其中，P等于每台机床运行费用的总和，即每台机床每小时运行成本与运行时间乘积之：
P?2000T1?1800T2?1500T3?1200T4?1000T5?800T6
Q为所有产品的调度费用之和，即：
Q??qk （1）
k?145在（1）式中，qk为第k件产品的调度费用，等于第k件产品的调度次数乘以每次调度费用，而调度次数又为加工第k件产品的机床数ck-1，即：
，ck?1?0?1000，ck?2?qk=?ck?3 ?2000，?ck?4?3000，?1000(ck?1)而ck为加工第k件产品的机床数，用bik表示用第i台机床加工第k件产品，则：
?4aikm?0?1，?bik=?m=1?0， ?其他ck=?biki?16
其中aikm为第i台机床加工第k件产品的第m道工序的逻辑值，可表达为：
?1,第i个机床加工第k件产品的第m道工序 aikm???0,其他
因此，总的约束条件为：
15
??P?2000T?1800T?1500T?1200T?1000T?800T123456???1,第i个机床加工第k件产品的第m道工序a??ikm??0,其他???4?aikm?0?1，??bik=?m=1??0，?其他?6??s..t?ck=?biki?1??，ck?1?0??1000，c?2??kq=??k2000，c?3k?????3000，ck?4???1000(ck?1)45? ?Q??qk?k?1?5.1.3综上所述，得到问题二的0-1整数规划模型：：
minY?P?Q??P?2000T?1800T?1500T?1200T?1000T?800T123456???1,第i个机床加工第k件产品的第m道工序?aikm???0,其他???4?aikm?0?1，??bik=?m=1??0，?其他?6?s..t?ck=?biki?1??，ck?1?0??1000，ck?2???qk=?2000，ck?3???ck?4??3000，???1000(ck?1)
45??Q??qkk?1?16
5.2模型三的求解
与模型一的求解相似，我们依然采用启发式算法（近似）中的逐步改进算法对上述模型求解，具体算法步骤如下：
1）让第k件产品的第m道工序产品由所需费用最少的机床来做； 2）计算出每台机床的完成费用(运行费用与调度费用之和)，找出完成指派工作所需费用最多的机床（最昂贵者）与所需费用最少的机床（最廉价者）；
3）若最昂贵者所做的工作均标有?，则停止，此指派方案即为一个近似最优方案；
4）求最昂贵者所做的每个工作的工作费用与最廉价者的工作费用差，其绝对值最小的工作转给最廉价者做。
5）若此二人完成时间的较大者变小，记录新方案，清除标记，转2)；否则，维持原方案，并将该工作记上标记?，转4）。
按逐步改进算法得到最优化结果如下表2：
任务1 任务2 任务3 任务4 任务5 总时间 总费用 机床1 8 A, 8 B ---- ---- ---- ---- 64 机床2 ---- ---- ---- ---- ---- 0 机床3 机床4 ---- 8 C 13 A 13 C ---- 7 D ---- 12A，12B ---- 5 C 120 510 1784600 机床5 8 D 13 B 5A, 7C 12 D 5A,5D 441 机床6 ---- 13 D 7 B 12 C 5 B 322 5.3模型三的结果分析
表中数据的含义仍是某工序与该工序进行次数的乘积，如：8 A, 8 B表示在机床1上完成任务1的8道A工序与8道B工序；13 A表示在机床3上完成任务2的13道A工序……机床1完成任务的总时间为64小时，机床2不完成任何任务，机床3完成所有任务的总时间为120小时，机床4完成所有任务的总时间为510小时，机床5完成所有任务的总时间为441小时，机床3完成所有任务的总时间为322小时。
其中，机床4的总时间最大，为510小时，因此问题一的最短时间即为510小时，总费用为1784600元。
5.4模型四的建立：蚁群算法（针对有序加工方式）
此时柔性调度的网络图Q如图1所示（m=45,n=6）,图中一个节点对应一道工序，对图中的节点进行编号即对工序也进行了编号，例如图中节点1就对应工序O11。同时1号工序就是工序O11。Q?(O',A)，其中O'?O??O0?，O为所有
17
工序的集合，O0表示一个虚工序，它并不代表任何实际意义的工序，只是使得每个工件都有一个共同的开始工序。A为图中所有边的集合，包括：①每个工件按加工约束条件在所有机器上从开始到结束的加工路径如:1?4；②不属于同一个工件上的工序之间相互的边，如：1??2；③每个工件的第一个工序与O0之间的由O0到每个第一工序的单向边，如：0?1。图中每个边都有一定的权重，一般根据具体问题来选择权重。
从网络图的角度看，求解柔性调度问题就是要确定图中双向边的取向问题。可行解可表述为：①图中所有的双向边都确定为单向边；②最终的图中不包含回路。
求解柔性调度问题的难点在于：①解空间容量非常大，45个工件、6台机床的柔性调度问题包含(45!)6个解；②由于存在复杂的约束条件，使得解的构造非常复杂。
19118120m92182np
我们探索蚁群算法在柔性调度问题中的应用，提出采用一种新的启发信息：最早允许加工时间(EAPT)，并在算法中加入适量的随机信息，使算法避免陷入局部最小的陷阱。 5.4.1标志量的设计
设计一个好的标志量，可以使蚁群算法获得四大优点：①足够大的解空间或者可称为有效解空间；②解与解之间存在足够大的区分度；③获得较快的收敛速度；④获得在较快的收敛速度下得到较优解。
标志量P由下式计算：
18
90180270
????ij??ij???????izPj???izz?allowlist?0??若j?allowlistkotherwise
每条边的标志量由τ和η组成，τ为这条边上的信息素的量，η为来自问题本身的启发信息。根据SPT（Shortest Processing Time）及其反规则LPT（Longest Processing Time）排序，得：
fSPT?Oij??1?fLPT(Oij)?TijmaxMachineTime(Oij)Tij
maxMachineTime(Oij)其中，fSPTOij是SPT规则的评价函数； fLPT(Oij)是LPT规则的评价函数； Tij表示工序Oij的加工时间；
maxMachineTime(Oij)表示与工序Oij同机床加工的加工时间最长的工序的加工时间。 5.4.2算法的具体设计 Step1：选工序
按照蚁群算法计算每个可选工序的标志量：
?trailij?EAPTj???Pj??traill?s?il?EAPTl?j?s
其中，i为前一次算法循环所选出的工序。 Step2：计算加工工序k的机床的空闲时间段和加工序列
选中工序为k，设加工工序k的机床为h。
将工序k从G中删除。若工序k不是其所属工件的最后一道工序，则在S中用其后续工序代替工序k。 Step3：计算可选工序的EAPT
①计算工序k的后续工序的EAPT
②计算S中在机床h上所有未加工的工序的EAPT。
重复以上三步，直到G为空向量。得到向量MachTime和GetList，解为向MachTime中的最大值max(MachTime )。
19
Step4：信息素的积累
根据加工序列GetList，对trail(45?4)?(45?4)阵进行更新。 5.5模型四的求解
依次执行Step1、Srep2、Step3，直到走完所有的节点，然后执行Step4，进行信息素积累。直到完成所有循环，每次迭代的结果都要与前一次的结果作比较，取其中的较小值作为此次迭代的结果；再直至完成所有迭代，最后得到的较小值就是算法的结果。
得到此时最佳调度的甘特图，如下：
机床6 机床5机床4 机床3 机床2机床1 08A17A3-5A57B3-5B513B212C47C313D28D1-12D4-5D512A412B413C2-5C57D313A213B28C15C55D58B14080120 160200240时间
5.6模型四的结果分析
将最佳调度甘特图的结果制作成下表的形式，可以得到，完成任务的最短总时间为441小时，最小总费用是1799000元。 任务1 任务2 任务3 任务4 任务5 总时间/h 总费用/元 机床1 8A,8B ---- ---- ---- ---- 64 机床2 8C ---- ---- ---- ---- 56 机床3 ---- 13A,13B ---- ---- ---- 356 机床4 ---- 13C 7D 12A,12B 5C 438 机床5 8D ---- 7A,7C 12D 5A,5D 441 机床6 ---- 13D 7B 12C 5B 322 1799000 为进一步分析该算法的有效性，我们进行了实例规模较大的计算机仿真试验，逐步收敛以测试精度。经过四次仿真结果与最优解的误差比较，得到下图：
20
可以看到，随着问题规模的增大，算法的收敛速度随之减缓，此时迭代次数的选择应同时考虑本问题的精度要求和运算的代价，因此对于该算法在规模较大时的有效性有待提高。
5.模型的检验及分析
对模型一：
指派问题中的0-1整数规划模型对于解决关于“是”和“否”的决策问题 对模型二：
Fisher判定模型是需要在“总体”之间差异较大的基础上进行的判定，所以如果当两个“总体”的差异不是非常明显时就会影响最后的判定结果。所幸本题的两个总体之间的概念和内容完全相反，因此判别效果很好。
对模型三：
BP神经网络算法具有较强的容错能力，其实质体现了网络输入和其输出之间的一种函数关系。通过选取不同的模型结构和激活函数，可以形成各种不同的人工神经网络得到不同的输人输出关系式，并达到不同的设计目的，完成不同的任务。由于 BP神经网络有模拟推理和自动学习性，更接近人脑的自组织和并行处理能力，使其具有一定的智能性，并且 BP神经网络模型仿真性能较好，也说明了它在建模判定方面的能力优于其它方法.
对模型四：
21
6.模型的评价、改进与推广
6.1模型的评价
本文利用0-1整数规划、遗传算法、蚁群算法成功地解决了对所任务分配到机床的实际问题，从问题的分析到模型的建立求解再到模型的分析，逐步靠近问题的本质，在这些过程中克服了许多困难，模型有优点也有不足之处。 优点：
（1） 对无序和有序两种情况都建立了相应的模型，模型的通用性很强。 （2） 问题一中各机床完成任务时间的很均衡，对问题二用理想点法将双目标转化为单目标，得到了有效解。
（3） 在模型二中用遗传算法进行求解，通过动态调整产品的加工优先级并未每道工序分配最合适的机器进行加工，可迅速求得最满意的较优解。 缺点：
（1）由于我们对柔性机床调配问题使用的均为启发式算法，不太可能得到一定决定的最优解或最优方案，对程序的多次运行并不能得到一个稳定的结果。 （2）针对 Job-Shop 问题，虽然我们采用了新的启发信息和加入适量的随机信息可以使蚂蚁算法求解时得到很好的解，但从仿真结果可以看出，我们的结果与最优解始终有一定的差距，如何提高蚂蚁算法的精度，这一点值得深入研究。初步设想可在蚂蚁算法中融入其他算法的求解优点，对蚂蚁算法加以改进。 1． 6.2 模型的改进
不管是蚁群算法还是遗传算法都不能完美的解决柔性机床的调配问题，因此我们可以尝试几种算法混合，或者对其进行优化来得到更好的模型。 6.3 模型的推广
我们建立的0-1整数规划，遗传算法模型和蚁群模型可以比较合理和容易的解决工业，教育，经济领域上类似于本文的一些较实际的变量筛选的归类统计分析，也可用于其他资源，如面试的流程问题，人员调配问题。在这些领域我们通常会需要将一些案例或者是实际的事物的属性进行分析和归类，而这些属性往往是影响这些事物发展的关键性的因素。我们有信心将这三种模型运用到实际中，解决更多类似的难题。
参考文献
22
[1]宋来忠，王志明,数学建模与实验,北京：科学出版社,2005 [2]杨超，熊伟，白亚根，运筹学，北京：科学出版社，2004
[3]邵斌，蔡鸿明，姜丽红，一种柔性车间快速启发式调度算法,计算机应用软
件, 第26卷第3期，2009
[4]曾德山，娄臻亮，张浩翼，遗传算法在模具生产调度中的应用，模具工业，
总第275期，2004
[5]杨冬，蚂蚁算法在组合优化问题中的应用研究，[硕士]天津大学，2004;
23