面向离散制造业的生产调度算法研究与系统设计

姜 康，庄怀天，咸 凯

(合肥工业大学 交通运输工程学院，合肥 230009)



面向离散制造业的生产调度算法研究与系统设计

姜 康，庄怀天，咸 凯

(合肥工业大学 交通运输工程学院，合肥 230009)

针对离散制造业的单件、小批量生产模式，分析其特点与企业需求，设计合理的系统流程和功能组成。构建以生产批次为单位的，基于时间和成本约束的多目标优化模型，利用改进的遗传算法求解调度模型的最优解。开发出符合离散生产模式的调度管理系统，通过实例验证其有效性及可行性。

遗传算法；时间和成本；设计开发；调度管理系统

0 引言

车间计划与调度是企业车间管理的重点和难点，良好的计划与调度系统对缩短生产周期，提高经济效益十分有效[1-2]。近年来，越来越多的企业和学者投入大量的精力来研究车间调度。目前，研究方向主要分为两个方面：一个就是调度系统的设计开发；另一个主要集中在调度模型的建立及调度算法的改善。如邵佳楠等在我国中小型离散制造业基础上，研究适用的车间生产调度模式[3]；李鑫等人着重分析调度系统的结构、需求和功能组成，对系统的关键技术进行了深入的研究[4]；金峰等对生产调度的问题及解决方法做出了系统的归纳总结[5]。在调度模型及算法设计方面成果突出，如李京生等人在云制造技术面向服务思想的启发下，构建了基于动态资源能力服务的分布式协同调度并取得了良好的效果[6]；崔维伟等人综合考虑生产调度与设备维修，构建了基于周期性维护的最大加工时间最短的数学模型[7-9]。

目前对流程工业及大批量生产的调度系统研究已经非常成熟了，但对于离散企业的调度问题，还一直是难点。本文通过计划管理的分批操作实现单件小批量生产，将处理后的小批量作为整体进行生产调度，并建立基于时间和成本的调度模型，通过遗传算法优化目标函数。最终设计开发出能够适应于单件小批量生产模式的调度系统。

1 系统整体设计

1.1 系统需求分析

离散制造业由于其特有的生产模式，使其在计划制定与车间调度方面还存在许多问题。此外，车间生产现场的多变性也增加了调度执行的难度，所以在采用计算机调度的同时还应保留计划员工的经验操作。对超期的生产计划，系统应能够提供在更改车间及设备生产日历的前提下进行重调度。

1.2 系统流程设计

根据企业生产实际，详细设计任务指派子模块的实现流程；同时生产现场变化多端，没有任何一种计算机调度算法可以完全取代员工的作用，而且完全依赖计算机的调度并不能满足生产实际。综合考虑，本系统的主要流程如图1所示。

图1 系统流程图

1.3 系统功能设计

结合生产实际和系统功能需求分析，最终确定系统的功能组成包括系统管理及任务指派两个部分。系统管理以实现用户添加、信息修改及车间与设备工作日历的制定等功能；任务指派主要目的是管理车间计划及对任务调度，具体如图2所示。

图2 系统的功能模型图

2 调度建模与算法设计

2.1 调度的数学建模

为了方便车间调度问题，现做出如下假设：

(1)同一批次工件集中的各工件加工工艺相同、加工时间及成本都相同，并忽略各工件间的准备时间；

(2)车间中所有设备均完好，且能够加工所有任务，只是时间和成本不同；

(3)同一时间，某个工件集的某个工序只能在一台设备上加工；

(4)同一时间，某台设备只能加工某个工件集的某个工序。

(1)

(2)

(3)

(4)

∀α1≥0，∀α2≥0

(5)

0≤i≤l，0≤j≤ki，0≤n≤m

(6)

模型的说明如下：

式(1)为基于时间和成本约束的目标函数；式(2)为变量的取值范围；式(3)保证每个工序任务只能分配一次，且只能分配到某一个设备；式(4)保证任务的加工顺序是按照工艺要求的；式(5)为加权值，为保证目标函数中时间和成本的量纲一致，α1的单位为分钟，α2的单位为元；式(6)为各下标的取值范围。

2.2 算法设计

本文采用改进的遗传算法来求解调度最优解，算法设计如下：

(1)编码和解码

本文采用基于设备的编码方式，每个染色体代表的是分配到设备上的工序任务和任务开始的先后顺序。

(2)适应度函数

本文将求解式(1)的最小值作为适应度函数，即g(x)=Min f(x)。

(3)选择、交叉和变异

采用比例选择算子的方式来执行选择操作，将概率大的个体的基因尽可能的保存下来。只对表示设备编号的基因位进行交叉，表示任务顺序的基因位仍采用随机生成发。而变异的过程中，则考虑设备编号和任务顺序各自单独变异。

2.3 调度实例

将5个工件集合理分配到5台设备上加工，每个工件集包含3个工序任务。表1和表2分别表示在不同设备上工序任务消耗的时间和成本。

表1 不同设备加工不同任务的时间消耗

表2 不同设备加工不同任务的成本消耗

结合生产实际，参数设置如下：α1=1，α2=1，初始种群为20，交叉和变异的概率分别为0.7与0.08，迭代次数为500。仿真得出在迭代132次左右的时候消耗最小，约为149.1。对应的工序任务分配顺序如表3所示。

表3 任务分配顺序

当只考虑时间时，虽然完工时间提前，但总消耗却增加了很大，出现了局部最优的情况，充分说明了该调度模型的优越性。考虑到设备5仅执行了一个任务，若将其取出，通过仿真可以发现，所有任务完成是的总消耗反而增加了，这说明任务较多时设备数足够多反而可以降低消耗。

3 系统应用实例

本文中设计的生产调度系统采用B/S结构体系，利用Java及Oracle11g相关技术，在Eclipse开发平台上开发适应于离散制造企业的调度系统。以下为该系统的应用实例：

(1)系统管理

系统管理的主要功能包括用户添加删除及修改角色权限、车间日历制定和设备日历制定与修改，如图3、图4所示。

图3 用户管理

图4 车间日历制定与修改

图3是用户管理，主要提供给系统管理员添加用户、修改用户信息等功能；图4是车间日历管理和制定车间日历，通过图3用户可以查询该车间工作日和休息日及工作日的工作时间段，图4即制定某一车间的工作日历，剔除非工作日及安排每天工作时间；设备日历的管理与制定与实例图4，这里就不再累述。

(2)任务指派

任务指派是该系统的核心模块，其中车间生产调度就包含着该模块中。任务指派主要有车间计划管理、生产资源准备、加工计划调度、加工计划审核与生产任务派工。各功能的实现实例如图5～图8所示。

图5 车间计划管理与资源准备

图6 加工计划调度

图7 加工计划审核

图8 生产任务派工

图5是计划管理与资源准备的应用实例，这里包括对计划分批处理，主要是每批次需加工的数量、开始结束时间等，还可以对计划分批的详情作一定的修改。资源准备，主要是指毛坯的准备情况，对于不足的资源应尽快下达外购指令或者寻找替代品。图6是调度模块，该部分内嵌算法，通过自动调度将各计划按照工艺文件自动分解并合理安排加工设备及起始时间，对于超过交货期的任务可以调整设备日历或者任务的优先级，重新调度直至满足交货期为止。调度时还可以查询设备的负荷率，以促进设备利用率的提高。调度时优先考虑优先级，其次考虑目标函数，即总消耗最小。图7是加工计划审核，可以录入审核人员对计划审核的意见。图8主要实现的是生产任务派工，对通过审核的调度及资源准备计划，可以生成派工单下达到车间生产加工。

4 结论

本文主要内容是设计面向离散制造业的车间生产调度系统，对系统的需求、流程及功能组成进行了详细的分析。研究针对单件小批量生产模式的调度模型及算法，建立了以批次为单位的基于时间和成本的多目标优化模型，用改进的遗传算法验证模型的有效性。最后，在前文研究基础上，开发出所设计的调度系统，通过某离散企业的实际试用证明系统的可行性和有效性。

[1] MESA International. The Benefits of MES: A Report From The Field[R]. MESA International White Paper,1997.

[2] Sieberg J, Walter R. A scheduling and resource optimizing MES for the semiconductor and MEMS industry [J]. Advanced Semiconductor Manufacturing Conference and Workshop, 2003: 101- 105.

[3] 邵秋楠，耿也.中小型离散制造企业车间生产调度模式的设计[J].组合机床与自动化加工技术，2011(3)：105-107.

[4] 李鑫，夏莜筠，常晓芳.企业车间生产调度MES系统的设计与研究[J].组合机床与自动化加工技术，2010(8):109-112.

[5] 金峰，吴澄.大规模生产调度问题的研究现状与展望[J].计算机集成制造系统，2006，12(2)：161-167.

[6] 李京生，王爱民,唐承统,等.基于动态资源能力服务的分布式协同调度技术[J].计算机集成制造系统，2012，18(7)：1563-1574.

[7] 崔维伟，陆志强，潘尔顺.基于多目标优化的生产调度与设备维护集成研究[J]. 计算机集成制造系统，2014，20(4)：1398-1404.

[8] 王桂娜，俞秉昊，潘尔顺,等.成组生产条件下考虑学习和遗忘效应及设备维护的调度策略[J].上海交通大学学报，2013，47(5)：723-727.

[9] 黄方明，陆志强，崔维伟.平行机系统生产调度与维护计划联合优化[J].工业工程与管理，2013，18(4)：49-55.

(编辑 李秀敏)

Scheduling Algorithm Research and System Design for Discrete Manufacturing Industry

JIANG Kang, ZHUANG Huai-tian, XIAN Kai

(School of Transportation Engineering, Hefei University of Technology, Hefei 230009, China)

On account of discrete manufacturing industry’s single piece and batch production mode, the paper analyzed its characteristics and demand, and the system process and functional composition were designed. Built multi-objective optimization mode in consideration of time and cost based on batch production, then used genetic algorithm to seek for the optimal solution. Exploited a scheduling management system which is fit for discrete industry, a example was taken to verify its validity and feasibility.

genetic algorithm; time and cost; design and develop; scheduling management system

1001-2265(2016)11-0154-03

10.13462/j.cnki.mmtamt.2016.11.041

2016-01-08

国防基础科研重大项目资助(A1120131044)；国防技术基础项目资助(JSBZ2014210A005，JSBZ2014210b007)

姜康(1974—)，男，山东文登人，合肥工业大学副教授，研究生导师，研究方向为数字化设计与制造、信息与控制；通讯作者：庄怀天(1989—)，男，安徽宿州人，合肥工业大学硕士研究生，研究方向为数字化设计与制造，(Email)zhuanghuaitian@126.com。

TH162;TG65

A