基于遗传算法的企业订单双边匹配调度研究

刘绘珍，廖丽平

(1.郑州航空工业管理学院 管理科学与工程学院，河南 郑州 450015;2.广东技术师范学院 管理学院，广东 广州 510665)

基于遗传算法的企业订单双边匹配调度研究

刘绘珍1，廖丽平2

(1.郑州航空工业管理学院 管理科学与工程学院，河南 郑州 450015;2.广东技术师范学院 管理学院，广东 广州 510665)

订单是企业生存的根本，是生产经营活动的源动力，因此，有效地对订单进行调度是企业生产管理工作的重要组成部分。在订单交货期模糊和加工时间随机分布的条件下，权衡订单成本和客户满意度，提出基于遗传算法的双边匹配调度模型，并利用算例对该模型进行检验。仿真结果显示：该模型对订单调度是有效的；与单目标优化相比，多目标优化是对多个目标的折中，从整个系统来看，多目标优化具有全局性的特点。

订单调度;双边匹配;模糊数;遗传算法

一、引 言

订单任务调度合理与否不仅影响企业能否发挥最大产能、生产经营活动能否顺利开展，还关系能否按质、按量、按期满足顾客满意度，进而对未来能否赢得更多订单造成重大影响。因此，柔性制造系统中研究订单任务调度，对提升柔性制造系统的总体管理水平和市场竞争力具有非常重要的现实意义。

相对传统确定性订单调度问题，实际调度问题中存在一些不确定因素。这些不确定性因素主要体现在两个方面：一是加工时间的不确定性，二是产品交货期的不确定性。前人文献中对此也做了很多研究。Ahmadi(2007)研究快速响应下的订单任务调度问题，研究证实最小化总加权完工时间和交货时间的订单任务调度问题是NP-hard，并提出了用启发式算法解决该问题。[1]刘兰兰等 (2012) 考虑供应商制造资源利用状况和制造资源的性能，建立了订单分配多目标规划模型, 并利用基于模糊逻辑的遗传算法对模型进行求解。[2]Ish iih(1992)首次提出应将交货期视为模糊数，并对双机调度问题进行研究。[3]Chanas等(2001)研究了单机模糊调度问题。[4]Murata等(1999)研究了模糊交货期下的多目标调度问题。[5]Sakawa (2000)研究了单件作业的多目标模糊规划问题。[6]Wang(2004)研究项目调度问题时交货期采用六角梯形模糊数。[7]Lam等(2002) 研究单机调度时用L-R模糊数表示的模糊加工时间和模糊交货期，同时提出了基于期望距离的拖期惩罚函数。[8]Ribaric等(2002)用模糊交集面积的方法度量和比较用三角模糊数和梯形模糊数表征的时间参数。[9]杨斐(2007)在研究多品种混合装配线订单排序中提出一种基于模糊决策模型改进的混合遗传禁忌搜索算法。[10]潘伟等(2009,2010)根据订单目标和约束条件的不确定性和模糊性，构建了一个包含模糊目标和随机约束的订单分配模型。[11][12]郑永前(2013)研究大规模订单生产中的动态订单调度问题，考虑到大规模订单调度中产品种类多、调度复杂等特点，提出一种基于模糊核聚类的重调度方法。[13]

订单合同在设定期望交货期的同时也约定了对违约行为的惩罚，即若实际交货期超出设定的期望交货期则要支付一定的违约费用。因此，用模糊变量描述交货日期比较切合实际。产品的加工时间被描述为服从正态分布的随机变量。综上，本研究在订单交货期为模糊数、加工时间随机分布的柔性制造系统中，提出基于隶属度函数的双边匹配调度算法，并用算例验证该算法的有效性。

二、模糊数的表示和比较

根据时间的确定性，订单交货期可分：确定性交货期和模糊性交货期。确定性交货期问题中交货期是一个明晰的正实数；模糊交货期问题中交货期是一个模糊数，存在一个时间窗口。

(一)模糊数的表示

模糊数的一般表示形式：

(1)

式(1)中，L(x)为增函数，右连续，且0≤L(x)≤1；R(x)为减函数，左连续，且0≤R(x)≤1。

两种常见的特殊模糊数：三角模糊数和梯形模糊数。本研究采用梯形模糊数表示订单交货期及其对应的满意度和惩罚函数。

实践中，通常把订单的交货期设定成两个值：提前交货边界值el和拖期边界值dll，当订单完成时间小于el时，关于交货期的客户满意度为0；当订单完成时间大于el时，客户满意度随着订单完成时间推延而增大，当订单完成时间位于[ell，dl]时，客户满意度为1；当订单完成时间超过交货期窗口最大值dl时，客户满意度随着订单完成时间推延而减少，当订单完成时间超过dll时，客户满意度降为0。综上，与交货期相关的客户满意度如式(2)，其对应图1。

(2)

本研究假设制造企业为了增大客户满意度，提前完工(即完工时间早于ell)时将成品存入库房暂不交货，而等到ell时才交货，因此，梯形满意度函数退化为半梯形，如式(3)，其对应图2。

(3)

与交货期相关的费用有三部分：(1)成品库存成本，提前完工且不交货而存入成品库存的订单(产品)产生的库存成本，即完工时间小于ell，其与提前完工时间成正比；(2)惩罚费用，若一订单完工时间超过了期望交货时间，即完工时间大于dl，则要受到惩罚，惩罚费用与延迟时间成正比；(3)违约费用，若订单完工时间超过了截止交货时间，即完工时间大于dll的订单，除支付延迟惩罚费用之外，还要一次性支付一定数量的违约费用。完工时间位于ell和dl之间的订单只有正常的加工成本，没有与交货期相关的费用。综上，与交货期相关的费用函数如式(4)，其对应图3。

(4)

(二)模糊数的比较

在模糊调度环境下，确定调度方案的优劣涉及模糊数的比较。目前已有多种方法可以用来比较模糊数，基本上可分为概率分布法、均值面积度量法与λ均值面积度量法。本研究采用概率分布法对梯形模糊数进行比较，概率分布法也称重心法，包括如下两个指标：

(5)

(6)

m(M)和σ(M)分别为模糊数M的均值(重心/期望)和方差。

对于梯形数M=(a,b,c,d)，有：

(7)

(8)

计算结果见表1。

概率分布法的实质是：直觉上，人们通常偏爱均值较大而方差较小的模糊数，因而该方法更符合人们的思维模式。

三、基于遗传算法的双边匹配调度模型

实践中，订单调度问题的目标往往不止一个，而是需要同时考虑多个目标，比如订单的加工时间、加工成本、最长完工时间、总拖期时间、完成订单需要的人工/机器总负荷等，因此，订单调度问题属于多目标优化问题。订单驱动的柔性制造系统中，订单对系统运行起着决定性的作用，因此客户的满意度和企业的生产成本(主要是与交货期相关的成本)是订单任务调度中两个关键性的目标。基于上述两个目标，本研究采用遗传算法进行双边匹配调度。

(一)以制造企业成本最小的订单调度和遗传算法

本研究采用式(4)的成本函数，以成本最小为目标进行订单调度。

一个柔性制造系统可生产多种产品，假设可归为四种标准产品，根据产品种类可对订单进行拆分使一个订单只有一种产品，因此，一个订单对应一种产品，对应一个客户。假设四种标准产品分别按相同的加工顺序由四个作业小组加工完成，不妨设标准产品j在四个作业小组的标准加工时间表示为：ttj=[ttj1,ttj2,ttj3,ttj4]。

(9)

式(9)作为目标函数，采用遗传算法求解该函数的极小值。用一个大的正数M修正(减去)式(9)，使其转换为求极大值的问题且保证取值为正。

遗传算法的设计内容：

(1) 编码与解码方法，本研究采用整数编码方式，N个订单对应编码空间是从1到N的整数。每个订单对应一个值，考虑到在交叉或变异过程中不同订单的编码值可能相同，解码时按照编码值大小对订单进行排序，排序结果即对应订单的调度结果，同时将该结果赋予对应的基因使其在没有重复编码的情况下进行下一代进化。该编码方式有针对性地得到订单调度的次序。

(2) 适应度函数的构建，根据目标函数设计该函数，适应度值是对解的一种度量，表明个体或解的优劣性。依据订单中产品的种类(对应各个作业小组的标准工时)和数量，柔性制造系统工人数量及其效率，仿真得到每个订单的实际完工时间，再根据式(4)计算每个订单与交货期相关的费用，并计算式(9)的值，即为适应度值。

(3) 遗传算子，包括选择、交叉和变异。用轮盘赌的方式和精英保留策略对种群选择进化。交叉和变异参数采用Matlab遗传算法工具箱中默认的配置：pc=0.8,pm=0.05。

(4) 控制参数，主要指种群规模、最大迭代次数等。本研究根据决策变量的空间大小设置不同的控制参数，决策变量越多，种群规模和迭代次数的设置越大。种群规模一般取500-800个，最大迭代次数设置为1000次。

(二)以客户满意度最大为目标的订单任务调度

本研究采用式(3)的半梯形满意度函数，以客户满意度最大为目标对订单进行调度。

(10)

由于现实中，制造企业通常对客户的重要程度进行划分，划分依据是客户的历史记录，比如历史订单的利润和频率，合作的紧密程度以及客户回款及时率、退货率、对账准确率等记录。依据上述记录，企业可采用多指标综合评价的方法评价客户重要性等级，可将客户分为五种：长期战略伙伴、较重要老客户、重要新客户、一般老客户和一般新客户，重要性权重依次减小，不妨用表示客户j的重要性权重，其对应值为：[1.2，1.1 1，0.9，0.8]。对式(10)加权得式(11)：

(11)

式(11)作为目标函数，采用遗传算法求解该函数的极大值。

(三)基于隶属度函数的双边匹配调度

把订单调度问题转换成制造企业的制造顺序和客户(订单)相匹配的问题，即双边匹配决策问题，如图4所示，制造企业一侧的节点[O1,O2,…,On]表示生产的次序，客户一侧的节点[CU1,CU2,…,CUn]表示每个客户(订单)。若O1和CU2相匹配，即连线表示客户CU2对应订单的调度次序为1。左图表示可能的匹配对，加工次序为1的节点O1可能与任何一个订单相匹配，表示任何一个订单的调度次序均可能为1；而右图为确定的匹配对，加工次序为1的节点O1匹配第二个订单CU2，即第二个订单的调度次序为1。匹配过程中，需考虑制造企业的利益和客户的满意度，前者指与交货期相关的总成本，根据上文阐述的方法可得到总成本最小情况下匹配策略；后者指所有客户满意度之和，根据上文阐述的方法可得到总客户满意度最大情况下的匹配策略。然后基于隶属度函数对二者进行双边匹配，给出合理的匹配结果。

不妨用0-1变量表示第k个订单的调度次序是否为i，取值1表示第k个订单调度次序为i，取值0表示第k个订单任务调度次序不为i。匹配变量xik对应一个调度顺序，根据该次序进行仿真即可得到单目标函数式(9)和式(11)的值，同时以企业利润为目标构建另外一个目标函数式(12)，以客户满意度为目标构建另外一个目标函数式(13)。

(12)

(13)

(14)

(15)

式(12)为目标是以制造企业为主进行匹配决策，式(13)为目标是以客户为主进行匹配决策。式(14)和式(15)约束订单和生产次序之间一一对应，即是一对一的匹配问题。

该模型为多目标优化问题，为求解该模型，采用基于隶属度函数加权和的方法，将目标函数转化为隶属度函数的形式，并采用遗传算法进行求解。g2max和g2min对应以交货期相关的成本极大和极小为目标的最优值，和对应以客户满意度极大和极小为目标的单目标问题，则两个目标的隶属度函数ug1和ug2可分别定义为：

(16)

(17)

用α1和α2作为ug1和的权重(α1和α2均取1)，则通过隶属度函数的加权和方法建立新目标函数：

max g=ug1×α1+ug2×α2

(18)

约束条件同式(13)和式(14)，原多目标问题变换成单目标问题，可采用本文阐述的遗传算法求解。

四、算例分析

通过算例验证双边匹配调度模型。算例中，柔性制造系统以及订单的参数假设如下。

订单中产品需求量服从参数为λ的泊松分布，取值按照24%、22%、20%、18%和16%的概率分别取200、400、600、800和1000。依据重要客户的需求较多，按照24%、22%、20%、18%和16%的概率分别生成客户重要性权重：1.2、1.1、1、0.9和0.8。

假设柔性制造系统中四个作业小组对应的工人数量分别为[w1,w2,w3,w4]，且每个工人都是熟练工，均能达到标准效率。工人的加工速度具有一定随机性，掌握小组i的工人加工产品种类n的速度服从均值为ttni，方差为0.1×ttni的正态分布。根据四种标准产品在四个作业小组需求的标准工时和订单中产品种类和需求量的随机性，四个作业小组需求的总工作量相同，因此每个作业小组配备两个工人。每个工人掌握两项技能，向后工序延续形成技能链，以相互协助平衡生产。

以待调度10和20个订单量为例进行双边调度。10个订单量的单目标调度得到最大成本、最小成本、最大满意度和最小满意度分别为：1383.6、122.3087、9.5037和3.301，基于成本与满意度双边匹配的目标值2.0002(其中最小成本和最大满意度分别为：122.5843 和9.5065)；最大成本、最小成本、最大满意度、最小满意度和双边匹配调度结果分别为：[2, 9, 10, 8, 5 ,7 ,4, 1, 6, 3](该向量的第一个值2表示第一个订单任务调度次序为2，第二个值9表示第二个订单任务调度次序为9，其他值的含义相似)、[8, 3, 2, 4, 1, 5, 6, 9, 7, 10]、[8, 3, 2, 4, 1, 5, 6, 9, 7, 10]、[2, 7, 4, 8, 3, 6, 9, 5, 10, 1] 和 [8, 3, 2, 4, 1, 5, 6, 9, 7, 10]。结果显示以最小成本为目标、最大满意度为目标和双边匹配调度的结果相同，原因是：遗传算法求解的是满意解而不是最优解，三个目标虽不完全相同，但也不是相悖的目标，大体方向一致，因此，对于特定订单调度时三个不同的适应度函数也可能使遗传算法在多种随机因素的影响下进化得到相同或相近的结果。

20个订单量的单目标调度得到的最大成本、最小成本、最大满意度和最小满意度为：5388.4、539.1465、19.3351和7.0478，基于成本与满意度双边匹配的目标值为1.9393(其中最小成本和最大满意度分别为：518.6627和18.5372)；最大成本、最小成本、最大满意度、最小满意度和双边匹配调度结果分别为：[19,14, 1, 10, 11, 18, 5, 2, 15, 6 ,8, 3, 9, 7, 4, 20, 13, 12, 16, 17]、[10, 2, 18, 8, 4, 1, 19, 13, 5, 15, 16, 17, 11, 20, 14, 9, 7, 3, 12, 6]、[6, 2, 16, 8, 3, 1, 18, 14, 4, 15, 12, 17, 10, 9, 13, 9, 7, 20, 11, 5]、[18, 8, 3, 13, 9, 4, 6, 19, 10, 1, 14, 5, 16, 2, 20, 17, 11, 7, 15, 12]和[10, 3, 17, 8, 4, 1, 18, 14, 5, 15, 16, 19, 11, 20, 13, 9, 6, 2, 12, 7]。比较以最小成本为目标和最大满意度为目标的结果与双边匹配的结果，双边匹配的优化得到的成本比单目标优化的还小，双边匹配优化得到的满意度比单目标优化的小，一方面可能由于遗传算法寻找的是满意解，另一方面可能是多目标需综合考虑多个因素，不同适应度函数使遗传算法进化得到不同的优化结果。

五、结论与展望

本研究在订单交货期模糊和加工时间随机分布的条件下，权衡订单成本和客户满意度，构建了基于遗传算法的双边匹配调度模型。利用Matlab遗传算法工具箱编程，从而进行仿真实验，仿真结果显示：该模型对订单进行调度是有效的；与单目标优化相比，多目标优化是对多个目标的折中，从整个系统来看，多目标优化具有全局性的特点。

本研究在对订单调度中仅仅考虑了两个目标，而实际生产中需考虑更多目标；同时生产系统经常面临着一些不可预料的动态随机事件，比如：紧急插单、交货期变更、临时撤单等订单的动态调度问题，有待今后进一步深入研究。

[1]Roza Ahmadi, Uttarayan Bagchi, Thomas A.Roemer. Coordinated scheduling of customer orders for quick response [J]. IIE Transactions, 2007(39): 899-909.

[2]刘兰兰,张 胜,叶飞帆.李国富制造资源驱动的产业集群订单分配研究[J].宁波大学学报(理工版).2012,25(1):119-124.

[3]Ish iiH, TadaM, M asuda T. Two scheduling problems with fuzzy due Dates [J].Fuzzy Sets and Systems.1992:46 (3):339-347.

[4]Chanas S, Kasperski A. Minimizing maximum lateness in a single machine scheduling problem with fuzzy processing times and fuzzy due dates[J].Engineering Applications of Artificial Intelligence.2001,14 (3):377-386.

[5]T. Murata, Hisao Ishibuchi, Mtsuo Gen. Multi-Objective Fuzzy Scheduling with the OWA Operator for Handling Different Scheduling Criteria and Different Job Importance[C].IEEE International Fuzzy systems conference Proceedings.August.1999, 22-25.Seoul,Korea.

[6]Masatoshi Sakawa. Fuzzy Programming for Multi-objective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithms [J]. European Journal of Operational Research.2000 (120):393-407.

[7]Juite wang. A fuzzy robust scheduling approach for product development projects [J].European journal of operational research. 2004 (152):180-194.

[8]S. S. lam, X. cai. Single machine scheduling with nonlinear lateness cost functions and fuzzy due dates [J].Nonlinear Analysis: real world Applications. 2002 (3):307-316.

[9]Slobodan ribaric,bojana dalbelo basic,lada males. An approach to validation of fuzzy qualitative temporal relations[C].24th int. Conf. information technology interface ITI2002, June 24-27.cavtal, Croatia.

[10]杨 斐,阚树林,钱 峰,许 洁,张赋杰,王 越.基于多目标模糊决策的混流装配线排序算法[J]. 机械设计与制造，2007(12):209-211.

[11]潘 伟,汪寿阳,华国伟,张金隆.基于模糊权重的多目标订单分配模型[J]. 中国管理科学，2009,17(2):80-85.

[12]潘 伟,余乐安,张金隆,汪寿阳.模糊多目标订单分配模型[J]. 武汉理工大学学报(交通科学与工程版)，2010,34(3):472-475.

[13]郑永前,郭延陀,力立安.基于模糊核聚类的大规模订单生产重调度方法[J].工业工程与管理，2013,18(2):1-5.

[14]Hopp W J, Tekin E，Van Oyen M P. Benefits of skill chaining in serial production lines with cross-trained workers [J]. Management Science. 2004, 50, 83-98.

责任编校：陈 强，王彩红

Study on Two-Side Matching Order Scheduling Based on Genetic Algorithm

LIU Hui-zhen1， LIAO Li-ping2

(1.Zhengzhou Institute of Aeronautical Industry Management, Zhengzhou 450015, China；2. School of Management, Guangdong Polytechnic Normal University, Guangzhou 510665， China)

Order is the fundamental survival for a business, and it’s the driving force of production and operation activities, thus it is one of the most important work of enterprise production management to order scheduling effectively. In the condition of fuzzy order delivery time and random processing time, considering order cost and customer satisfaction, this paper puts forward the two-side matching scheduling model based on genetic algorithm. The simulation result shows that compared with the single objective optimization, multi-objective optimization has the characteristics of integrity and global.

order scheduling;two-side matching;fuzzy set;genetic algorithm

2014-10-03

国家自然科学基金项目(71271060)；国家自然基金项目(71173051)；广东省哲学社会科学资助项目(GD12XGL03)；河南省政府决策项目(2014152)

刘绘珍，河南开封人，管理学博士，主要从事系统工程、工业工程研究。 廖丽平，福建厦门人，副研究员，博士，研究方向为技术创新管理、工商企业管理等。

F273.7

B

1007-9734(2015)01-0057-06