多订单项目生产任务并行调度的遗传算法研究

谈 健

(上海交通大学机械与动力工程学院,上海 200030)

多订单项目生产任务并行调度的遗传算法研究

谈 健

(上海交通大学机械与动力工程学院,上海 200030)

在MTO(Make to Order)生产模式的制造企业中,经常存在多订单项目并行的情况。以满足资源约束为前提,优化多订单项目生产任务并行调度过程,成为该类企业关心的焦点问题。针对这一问题,根据任务并行调度的特点,建立了任务调度的目标函数,并采用一种改进了的遗传算法求解目标函数。该遗传算法用矩阵式染色体表示资源与生产任务之间的调度关系,采用突变机制来解决进化过程停滞问题,提高算法的搜索能力,并保留父代种群的优秀染色体,防止遗传过程中祖代优秀染色体丢失。

并行调度;遗传算法;多项目;资源调度;M TO生产模式

MTO(Make to Order)是现代制造企业中常见的一种生产模式。这种生产模式下,生产任务的安排根据销售订单施行,可以最大限度地减少库存,盘活资金流,降低风险。但是,这种生产模式对生产调度水平的要求很高,如何在多个销售订单并行的情况下,满足不同客户(订单)的目标需求,又能够兼顾企业内部的资源约束,进一步压缩生产成本,优化全局任务调度计划,是这类企业关注的焦点问题。传统的生产任务调度方法,已经不能满足日益加快的市场变化。因此,很多研究学者将目光聚焦到了项目管理领域,期望通过项目化的管理,寻求一种可行的理论方法。本文针对M TO制造企业实际生产过程,对多项目资源并行调度过程进行了建模,并且融合了两种改进遗传算法的优点,对该数学模型进行优化求解。该模型及遗传算法更符合M TO制造企业生产任务调度过程特点,通过较短的运算时间得到较优的解,从而解码成为实际生产过程中的任务并行调度方案,为该类企业的生产调度提供依据。

1 问题描述

基于M TO生产模式的制造企业,其终端产品通常并非标准化产品,但是,区别于D TO(D esign to O rder)生产模式,企业并不需要对产品进行全新设计,而是采用模块化的简单组合,形成满足客户需求的终端产品。因此,其订单项目实施过程相对固化,除对物料需求量的不同,从投料、加工制造、装配到调试试验等过程都不会因为订单不同而有所调整。在企业内部资源有限的实际情况约束下,要同时满足所有订单的要求,并非简单。当销售订单成立,转化为生产任务单,管理部门能够通过成熟的项目实施路线,快速形成项目网络图,资源需求表,并计算得到项目中各任务的松弛时间Tr,管理部门将所有该订单涉及的所有生产任务插入原生产任务调度表中。由于资源约束,项目任务的执行并不能按照理论时间节点进行。显然,这里面存在一个调度优化问题。原有项目未完成任务和新项目任务合成一张庞大的网络图。某任务J对某项资源r的占用,必然延缓其他任务对该资源的使用,从而造成任务调度的延迟。任务在资源r上的排序,存在多种可行调度方案,在企业生产环境中,考虑到全局资源调度方案,这些组合形成了一个N P2hard问题,这种问题的优化,依赖于一些智能算法,本文将通过一种改进的遗传算法来实现此类问题的优化。

2 数学模型

企业对生产任务调度计划的优化,其目标是满足客户需求。在调度计划中能够体现的就是项目的工期,也就是订单的交付时间。企业希望能够完全满足所有客户的需求,但是,由于实际生产过程的复杂性,以及一些突发事件的存在,订单延误也是可能存在的。对所有订单的交付日期的综合评价,成为调度计划水平的考核标准。本文通过对项目工期进行加权平均,期望优化过后的调度计划,能够使加权平均工期极小化。假设共有N个项目,M种资源,资源不可拆分,最大可用量为1。建立如下数学模型:

Ti为项目i的工期;Sti,j项目i中任务j的开始时间;Eti,k为项目i中任务k的结束时间,任务k属于任务j的紧前任务集合Aj;It为t时刻正在进行的任务集;Bi,j为项目i中任务j;ri,j,m为Bi,j对资源m的占用量。

式(2)和式(3)表示的是满足目标函数式(1)的约束条件。式(2)是紧前关系约束,式(3)是资源约束,每种资源可用量为1。

3 遗传算法优化求解

3.1 编码与解码

考虑到在同一时刻,可能释放出多个资源,这时候,可以多个任务并行调度,因此,文献[1]中所提到的利用满足紧前关系的可行任务链表编码的方法,不能准确表示调度过程。参照文献[2]中提到的编码方式,构造二维矩阵式染色体。染色体行表示某资源满足紧前关系的可行任务链表,其行数由资源数决定;染色体的列数由所有资源中,执行任务最多的资源决定,列数等于其执行的任务数。执行任务数少的染色体行,末尾补足0。

解码的时候,按行检索任务。由于在染色体行中对任务进行了排序,因此,某些任务在实际调度过程中受到资源约束,新加了一些前置任务。对所有紧前任务结束时间已定的任务赋予开始时间,并计算结束时间。循环搜索染色体矩阵,直至所有任务的开始时间和结束时间赋值结束,最终形成完整的并行调度方案。

编码和解码过程如图1所示。

图1 项目网络图Fig.1 Project network diagram

图1中所示网络图,虚任务1和任务11可以不编入染色体,其染色体编码如表1:

表1 矩阵式染色体编码Tab.1 Matrix chromosome coding

编码以后发现,由于资源约束,任务的紧前任务集发生了变化,如表2:

表2 资源约束下的紧前关系Tab.2 Resource2limited FS logical relationship

解码过程如下:

任务号为0的任务不调度。

Step1任务2可调度,开始时间0,结束时间3;

Step2任务5可调度,开始时间3,结束时间7;

Step3任务7不可调度,终止检索r1行;

Step4任务6可调度,开始时间0,结束时间2;

Step5任务8可调度,开始时间7,结束时间9;

Step6任务3可调度,开始时间7,结束时间8;

Step7任务9不可调度,终止检索r3行;

Step8任务10不可调度,终止检索r4行;

Step9任务7可调度,开始时间7,结束时间10;

Step10任务4可调度,开始时间10,结束时间14;

Step11任务9可调度,开始时间10,结束时间11;

Step12任务10可调度,开始时间14,结束时间15;

最终得到所有任务的调度时间参数。绘成甘特图如图2所示:

图2 资源受限情况下的资源计划Fig.2 Resource 2 limited schedule

3.2 适值函数

遗传算法的适值函数是对染色体适应能力的评价函数,一般要求适值函数值非负、与目标函数值对应、二者具有相同的极值点。本文根据优化调度数学模型中的目标函数,建立如下的适值函数:

3.3 初始种群的产生

对所有任务进行检索,获得所有资源上的任务列表。按照一定的优先调度规则,进行随机调度,形成基于某资源的任务链表。对这一任务链表进行前置任务检验,不合格的重新调度。这里的前置任务不仅仅是紧前任务,而是在任意任务链中,某任务的所有前置任务。当所有资源都获得了满足前置关系的可行任务链表,按照编码规则,就可以获得一条二维矩阵式的染色体。如此重复多次,获得初始种群PO P0。算法如下:

W H ILE剩余任务集AR非空

检索任务Bi,j,根据Bi,j.resource,将Bi,j加入到资源Rm的任务列表ARm

算法中,getPRI()函数输入是资源的任务集合,过程是一定优先规则随机调度任务,输出值是新的任务链表。

3.4 复制

按照以下概率,从父代种群中挑选两个染色体进行交叉变异:

3.5 交叉

按照复制规则,得到两个父代染色体popk,x和popk,y。对父代染色体当中的对应资源行依次进行交叉。交叉的位置pos随机产生。生成两个新的染色体popkx+1,x,popk+1,y。交叉算法不会改变资源行中的紧前关系。

3.6 变异

对新染色体popk+1,y,popk+1,y中各资源行按照变异概率pm进行变异。变异算子为:

随机生成两个位置pos1和pos2

交换popk+1,x[m][pos1]和popk+1,x[m] [pos2],生成新的pop′k+1,x[m]

对pop′k+1,x[m]进行紧前关系检验,不合格,则恢复成popk+1,x[m]

END FOR

生成新的pop′k+1,x

相同过程生成新的pop′k+1,y

3.7 保优策略

经过复制、交叉、变异N(N=popsize/2)次以后,形成了新一代的pop′k+1,y。从popk+1,y和pop′k+1,y中挑选2N个适值较高的个体,最终形成pop″k+1,y,作为新一代的种群。

3.8 算法结构

多订单项目生产任务并行调度的遗传算法机构如下:

Step1 初始化,获得popsize,gen,pm

Step2 生成初始种群PO P0

Step3 通过复制、交叉、变异、保优获得PO Pk,k=1,2,……,gen

Step4 重复step3,直至形成最终形成PO Pgen

Step5 从PO Pgen中挑选出适值最高的染色体作为最终的解

Step6 将最终解解码成并行调度方案

4 改进设想

在实际生产过程中,将会碰到很多复杂的情况,在本文的数学模型和算法中做了一些忽略。下面列举一些常见现象,作为以后改进的方向。

(1)有一些紧急的订单项目,原网络图中某些任务的松弛时间为负,为了缓解企业内部的资源受限程度,可以通过外协,外购等手段,可以缩短工期,减少资源占用,但是成本增加。

(2)如现象1中所述,除了订单项目内部出现通过企业内部资源无法完成的任务外,订单项目间为了争夺某项资源,出现资源冲突现象,即满足了项目A的任务要求,不能满足项目B,反之亦然。这种情况在原网络图中无法体现,难于判断,只有在调度过程中才会发现。如果在数学模型中加入限制条件,使所有项目的终止时间都要早于交付时间,那么一旦出现现象2,将会使进化中断,始终无法获得满足所有约束条件的染色体。针对这种现象,可以设计新的模型,使模型目标值带有超期惩罚性质,从而在调度方案比较的时候能够排挤超期惩罚大的调度方案。

(3)实际生产中,会有一些任务是按照一定的周期进行,例如,热处理过程,由于无法随时中断设备进行任务更新,任务需要等待到下一次设备开启时间,才能开始执行。这一现象也没有在本文的数学模型中体现。

Research on Genetic Algorithm for Concurrent Production Scheduling in Multi-order-projects

TAN Jian
(School of Mechanical Engineering,Shanghai Jiaotong University,Shanghai 200030,China)

MTO mode manufacturing enterprises often meet multi-order-projects scheduling problems. Currently,these enterprises focus on how to optimize production scheduling formulti-projects,which will be based on constraint of resources.To resolve this kind of scheduling problems,according to the characteristic of concurrent scheduling tasks,a mathematical model will be built in the paper.Then,a modified genetic algorithm is put forward to solve the model.This modified genetic algorithm uses a matrix chromosome to express the scheduling relation between resources and production tasks.A mutation strategy, which can avoid the prematurity,is founded to improve the optimizing capability for optimal scheduling. And to avoid missing the excellence chromosomes from father-generation,those excellence ones will be reserved to next generation directly.

concurrent scheduling;genetic algorithm;multi-projects;resource scheduling;MTO production mode

TP30116

A

1671-7880(2010)03-0063-04

2010-04-27

谈 健(1981— ),江苏无锡人,研究生,研究方向:项目管理。

[1] 刘士新.项目优化调度理论与方法[M].北京:机械工业出版社,2006.

[2] 张金标.并行设计任务调度的遗传算法研究[J].机械工程师,2008(1):61-62.

[3] 王万良,吴启迪.生产调度智能算法及其应用[M].北京:科学出版社,2007.

[4] 陆虎进.动态多项目资源配置及其改进方法[D].南京:东南大学,2005.