需求量不确定条件下单台机生产调度问题

吕 恒 肖 汉

摘要:研究了需求量不确定条件下带有交货期窗约束单台机的生产调度问题,模糊需求用三角模糊数来表示,模糊交货期用半梯形模糊数来表示,建立了以满意度最大作为优化目标的模糊调度数学模型,并给出了基于遗传算法的优化方法,通过仿真试验验证了方法的有效性。

关键词:不确定性;单机调度;遗传算法

中图分类号:F273文献标识码:A

Abstract: In this paper, scheduling for single machine with uncertainty demand is considered, which includes due-data windows for orders. A triangular fuzzy number is used to represent the uncertainty demand, and a half-trapezoid one to represent fuzzy due-data. We use the maximum agreement index as optimized object, and genetic algorithm is adopted to find the optimal sequencing. Simulation results illustrated the efficiency of the proposed model and algorithm.

Key words: uncertainties; single machine scheduling; genetic algorithm

0引言

生产调度问题的研究源于20世纪50年代,由于该问题的实用性和重要性,随之在运筹学和工业工程等学科中形成一个独立的分支方向。直到目前,专家学者仍然在研究不同情况下生产调度问题。由于现在的生活节奏加快,产品的周期越来越短,随之对产品的需求预测也成为现在生产的一个重要问题。企业在不能准确预测市场需求情况下如何更好地安排生产、更快地占领市场已经成为挑战。因此,在市场需求不确定的情况下更好地安排生产对企业的发展有重要的意义。

许多学者对需求量不确定条件下的生产问题进行了研究,苏生[1]等人研究了不确定需求和能力约束下的多目标多工厂生产计划问题;孙光圻[2]等人研究了相关、不确定需求下生产计划的优化问题;李初福[3]等研究了需求不确定下炼油企业的生产计划优化问题,这些研究主要集中在宏观的生产计划方面的不确定性,对需求量不确定条件下的生产调度研究不多。顾幸生[4]在研究不确定性条件下的生产调度问题时提出不确定性包括外部环境的不确定性,如产品的需求量、产品的价格、能源等,随后又研究了需求量不确定条件下连续过程生产调度问题。目前需求量的不确定性主要有两种表达形式:概率模型和模糊数。本文主要研究单台机生产调度问题,考虑市场对产品需求量的不确定性,采用三角模糊数来描述不确定性因素[5]。

1模糊函数

模糊集合是用隶属函数来刻画元素对集合属于程度的连续过渡性,隶属函数是0,1区间内的一个实数函数,当隶属函数u x的图形如图1所示,则模糊数 =A ,A ,A 称为三角模糊数,其中A 、A 、A 均为非负实,u x的函数表达式如式(1);当隶属函数u x的图形如图2所示,则模糊数 =B ,B 称为半梯形分布的模糊数,其中B 、B 均为非负实,u x的函数表达式如式(2)所示[6]。

u x=(1)

u x=(2)

设两个三角模糊数=A,A,A和=A,A,A,实数?鄣,则满足以下关系:

+=A+A, A+A, A+A

-=A-A, A-A, A-A

+?鄣=A+?鄣, A+?鄣, A+?鄣

?鄣=?鄣A, ?鄣A, ?鄣A

2问题描述

本文考虑将订单集J=J ,J ,J ,…,J 中的n个订单安排到一台机器上加工,由于市场需求的不确定性,订单J 的需求量用三角模糊数表示,=D,D,D;订单J 的交货时间用模糊数表示,=T,T;机器的生产率用P 表示;定单J 的实际交货时间用模糊数表示,=t,t,t;订单的重要程度用w 表示;客户对订单J 满意度用Z 表示,客户满意度Z 则为订单实际交货时间隶属函数与期望交货时间隶属函数的交集所围成的图形面积与订单实际完成交货时间隶属函数所形成的图形面积之比[5],即Z =area∩areaarea,如图3所示。

假设:(1)各订单经过其准备时间后即可开始加工,加工的优先级一样;(2)每一时刻机器只能加工一份订单;(3)加工过程为不间断,缓冲区容量为无限大;(4)操作允许等待,即前一个操作未完成,则后面的操作需要等待;(5)当订单提前于客户需求时间,则需在仓库等待,仓库容量无限大。

本文以客户总的满意度Z最大为目标函数,建立数学模型为:

MaxZ=Max w Z(3)

s.t.

=+(4)

P ≤P ≤P(5)

w =1 (6)

Z =(7)

由于需求量是模糊的,所以订单的实际交货时间也是模糊的,式(4)为实际交货时间;式(5)为机器的能力约束;式(6)将订单的重要程度归一化处理;式(7)是不同情况下满意度的计算。

3算法设计

目前,解决生产调度问题的有效算法是遗传算法(GA),它主要是借用生物进化中的“适者生存”的规律,在竞争的过程中保留优良的个体。本文将模型中的模糊数通过客户满意度转化成实数,采用遗传算法进行最优排序。

(1)染色体编码:采用自然数编码,用自然数表示订单,如有10个订单,则分别用自然数1,2,3,…,10来表示。

(2)初始值的产生:由于是单机生产调度问题,为了能遍历所有的排列,则采用随机产生初始种群,即令订单随机排列生产顺序,群体的规模为订单数量的1～2倍。

(3)适应函数:用目标函数来计算各个染色体目标值,然后将同一群体中的m个染色体按目标函数的从小到大排列,直接取分布概率为:Pk= , 1≤k≤m。

(4)遗传运算:随机产生一个同染色体有相等维数的不变位向量,每一个分量产生0或1,1表示不变,0表示变,需要变化的基因分别按对方的基因顺序选取不重基因顺序排列。如:向量10010101

父A15687324——子A16782354

父B36874215——子B36815724

(5)变异运算:采用随机变换两个基因的方法,将染色体的一个基因与另一基因交换位置。如:父15687324——子13687542

在遗传变异过程中,为了更快地得到最优个体,将遗传后的子代与父代进行比较,选择子代与父代中优良的染色体作为下次遗传的父代,最优个体不参加交叉及变异,每次种群的规模保持一致。

4仿真分析

假设某企业收到20个订单如表1所示,为了计算方便,生产率取1。利用上述算法,采用C语言编程进行仿真,初始种群个体数为30,迭代次数为200,交叉概率为0.6,变异概率为0.03。

通过仿真可以得到图4、图5。图4反映了目标函数值随迭代次数增加的变化趋势,从图中可以看出,在130代之前目标函数值不断增加,130代之后开始处于稳定,表明基本接近了最优值。采用其它的交叉变异概率,选择不同的迭代次数,虽然订单的排列顺序不同,但最终目标接近一致。由图5可以得到这一段生产周期内每个订单的生产顺序,进而可以合理的安排生产任务,进行物料的准备。

5结论

本文对模糊需求情况下的单机生产调度问题进行了较为深入、全面研究,运用模糊数学的理论建立了生产调度模型,考虑模糊需求量和模糊交货期的模糊流水车间调度模型,采用所有客户满意度最大为目标函数,使用遗传算法搜索到最优加工顺序。本文提出的算法通过仿真研究验证了其有效性,为模糊环境下生产计划与调度问题的研究提供了一种方法与途径。

参考文献:

[1] 苏生,战德臣,李海波,等. 不确定需求和能力约束下的多目标多工厂生产计划[J]. 计算机集成制造系统,2007,13(4):692

-697.

[2] 孙光圻,赵娜,包红. 相关、不确定需求下生产计划的优化[J]. 辽宁师范大学学报:自然科学版,2007,30(3):273-276.

[3] 李初福,何小容,陈丙珍,等. A Hybrid Programming Model for Optimal Production Planning under Demand Uncertainty in Refinery[J]. Chinese Journal of Chemical Engineering, 2008,16(2):241-246.

[4] 顾幸生. 不确定性条件下的生产调度[J]. 华东理工大学学报,2000,26(5):441-446.

[5] Masatoshi Sakawa, Ryo Kubota. Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms[J]. European Journal of Operational Research, 2000(120):393-407.

[6] 彭祖赠,孙韫玉. 模糊数学及其应用[M]. 武汉:武汉大学出版社,2002.

注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文