实用标准文档

文案大全 任务分配到机床

摘要

本文解决的是机床生产调度的问题，目的是使产品加工路径的组合优化。对于本文所研究的机床任务的合理调度问题，由于生产方式的不确定，我们根据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.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符号说明 实用标准文档

文案大全 符号 符号说明

ijx 表示是否由第i台机床去完成第j项任务

ijt 表示第i台机床完成第j项任务的时间代价

n 表示加工一件产品的机床数

P 表示所有机床的运行成本

Q 表示所有产品的调度费用

iT 表示第i台机床的运行时间

Y 表示总的生产费用

ikma 表示第i台机床加工第k件产品的第m道工序

ikb 表示第i台机床加工第k件产品

kc 表示加工第k件产品的机床数

kq 表示生产第k件产品的调度费用

SPTijfO 表示SPT规则的评价函数

()LPTijfO 表示LPT规则的评价函数

ijT 表示工序ijO的加工时间

max()ijMachineTimeO 表示与工序ijO同机床加工的加工时间最长的工序的加工时间

ic 表示设备iM上工件的加工次序

MFT 表示工件平均流通时间

MT 表示工件平均延误时间

,1sjlt 表示第j个零件的l+1道工序的开始加工时间 实用标准文档

文案大全 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） 每道工序可以在多台机器上加工，加工时间长短由机器的性能和功能决定；

据此，我们可以采用遗传算法、通过计算机仿真，得到相应问题的近似最优解。并以无序情况下在第一问中得到的结果作为下限做近似度分析。

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

指标二：完成时间最长的机床

问题要求所有机床的最短完成时间，首先要找出最后完成任务的机床，则要求所有机床的最短完成时间就是求此最长时间的最小值。最长的完成时间为：

180max161max ijijijtxt

指标三：最短完成总时间

我们用Z来表示总的预期时间效益，要求最短完成所有工序的总时间，则minmaxijijZtt为一个基本可行解中非零分量的系数，由此：

180161min max ijijijZxt 实用标准文档

文案大全 4.2 模型一的建立：0-1整数规划模型（针对无序加工方式）

在工序无先后加工顺序的情况下，任务分配问题是一类典型的组合优化问题，不同的分配花费不同的代价，任务分配问题就是要找到一种所花费代价最小的分配方案。

4.2.1确定目标函数：

下面建立上述指派问题的0-1整数规划模型。我们用Z来表示总的预期时间效益，则minmaxijijZtt为一个基本可行解中非零分量的系数。现有可完成180项任务单元的6台机床1A,2A,…,6A,第i台机床和第j项任务单元之间的执行关系ijx，即用ijx表示第i台机床加工第j项任务单元，以及第i台机床完成第j项任务单元所需的时间ijt（1,2,...,6;1,2,...,180ij）。若第i台机床完成第j项任务的时间ijto，则可构成时间代价矩阵6180()ijTt。

据此建立目标函数（一）为：

180161min max ijijijZxt

4.2.2确定约束条件：

设1,0,ijijxjj表示第台机床去完成第项任务表示第台机床不去完成第项任务

其中1,2,...,6;1,2,...,180ij，则分配问题即是求解任务分配阵6180()ijXx同时问题的约束有：对于一项任务来说，只可能被分配到一台机床上，即形成数学约束表达1801,1,2,...,6ijjxi。这里的约束条件是一个非线性规划，其目标函数也即min Z=max{ijt, ijt为一个基本可行解中非零分量的系数}，0,1,2,...,6;1,2,...,180ijtij，,ijijxXtT。

因此，总的约束条件为：

611,1,2,...,180..1,0,ijiijxjstijxij第台机床去做第项任务；第台机床不做第项任务。

4.2.3综上所述，得到问题一的0-1整数规划模型：