（计算机应用技术专业论文）家纺企业生产调度模型及优化算法研究.pdf

浙江亡业人学硕七学位论文 家纺企业生产调度模型及优化算法研究 摘要 车间调度问题是家纺企业生产的核心问题。家纺企业是典型的小批量、多品种的生产 制造企业，生产方式灵活、操作柔性强。因此，研究家纺企业的车间调度问题，对于提高 企业的生产能力、提高企业的经济效益，有着重要的意义。 本文针对车间调度研究中建模及优化方法的不足之处，结合家纺企业的实际生产特 点，从以下几个方面对家纺企业生产调度问题进行了研究： 首先，针对家纺企业加工时间和交货期确定的生产调度问题进行研究，建立确定性问 题的数学模型。根据模型特点，提出了一种新颖的人工免疫算法对其求解，采用向量组编 码的方式进行编码，通过一种新颖的基于浓度的种群多样性更新选择方法保证种群多样 性。仿真结果表明，该算法能更快更准确地收敛到全局最优。 其次，针对家纺企业加工时间和交货期不确定性生产调度问题进行研究，采用模糊理 论，建立模糊完工时间最小与平均满意度最大两个模型。根据模型特点，提出自适应遗传 算法和改进人工免疫算法对其求解，仿真结果表明，提出的算法能取得比较满意的效果。 最后，以研究的算法为核心，设计并完成了一个小型调度系统，并将其嵌入到亿思家 纺企业e r p 系统中，取得比较理想的效果。 关键词：家纺企业，生产调度，人工免疫算法，遗传算法，模糊集 浙江工业人学硕十学位论文 r e s e a r c ho nm o d e la n da l g o l u t h mt o p r o d u c t i o ns c h e d u l i n gp r o b l e m si n t e x t i l em a n u f a c t r u i n gi n d u s t r y a b s t r a c t t h et e x t i l e m a n u f a c t u r i n gi n d u s t r y i sac l a s s i cm a n u f a c t u r i n go n ew h i c hh a st h e p r o d u c t i o nm o d e 晰mv a r i o u sp r o d u c t sa n ds m a l lb a t c h ，a n di t sc o r ep r o b l e m sa r et h ej o b s h o p s c h e d u l i n g f o rt h et e x t i l em a n u f a c t u r i n gi n d u s t r y ，i t sj o b - s h o ps c h e d u l i n gi s af l e x i b l e s c h e d u l i n gp r o b l e mf n a h a r d ) t h e r e f o r e ，i tw i l lb eh e l p f u lt oi m p r o v ei t sc o m p e t i t i v e n e s sa n d e c o n o m i e sf o rr e s e a r c h i n go nj o b - s h o ps c h e d u l i n go ft h et e x t i l em a n u f a c t u r i n gi n d u s t r y i nt h i s p a p e r , b a s e do nt h e c h a r a c t e r i s t i c so fj o b s h o ps c h e d u l i n go ft h et e x t i l e m a n u f a c t u r i n gi n d u s t r y ，t h ep r o d u c t i o ns c h e d u l i n gw i l lb es t u d i e df r o mt h ef o l l o w i n ga s p e c t s f i r s t l y ，a i mt ot h ep r o d u c t i o ns c h e d u l i n gp r o b l e m 、讲t l la c c u r a t ep r o c e s s i n gt i m ea n dd u e t i m e ，ag e n e r a ls c h e d u l i n gm o d e li sp r o p o s e d f u r t h e r m o r e ，an o v e la r t i f i c i a li m m u n ea l g o r i t h m ( i 灿) ，b a s e do nt h ei m m u n et h e o r y ，i sp r e s e n t e d t h ea l g o r i t h ma d o p t sav e c t o re n c o d i n g m e t h o d ，a n du t i l i z e san e wd i v e r s i t ya p p r o a c ht oe n h a n c et h ed i v e r s i t yo ft h ep o p u l a t i o n e s p e c i a l l y ，al o c a ls e a r c ha l g o r i t h mi su s e dt oi m p r o v et h eq u a l i t yo ft h ep o p u l a t i o n s i m u l a t i o n r e s u l t ss h o wt h a to u rp r o p o s e da l g o r i t h mi a ii se f f e c t i v ea n do u t p e r f o r m ss o m eo t h e r i m m u n e - i n s p i r e da l g o r i t h m s s e c o n d l y ，t h ep r o d u c t i o ns c h e d u l i n gp r o b l e m 、析t hf u z z yp r o c e s s i n gt i m ea n dd u et i m ei s s t u d i e d ，a n dt h u st w os c h e d u l i n gm o d e l s ，m i n i m i z a t i o no ff u z z ym a x i m u mc o m p l e t i o nt i m ea n d m a x i m i z a t i o no fa v e r a g es a t i s f a c t i o n , a l ep r o p o s e d f u r t h e r m o r e ，b a s e do nt h et w os c h e d u l i n g m o d e l s ，w ep r e s e n t st w on o v e la l g o r i t h m ，s e l f - a d a p t i v eg e n e t i ca l g o r i t h m ( a g a ) a n di m p r o v e d i a i ( i a i - i i ) ，f o re f f i c i e n t l ys o l v i n gt h e m f r o mt h es i m u l a t i o nr e s u l t s ，i tc a nb eo b s e r v e dt h a t a g aa n di a i i ib o t ha r ee f f e - c t i v ea n df e a s i b l e n 浙江j l ：业人学硕士学位论文 f i n a l l y ，am o d u l eo fp r o d u c t i o ns c h e d u l i n gi sd e s i g n e da n di m p l e m e n t e d t h i sm o d u l eh a s b e e na p p l i e dt os o l v ea c t u a lp r o d u c t i o ns c h e d u l i n gp r o b l e m sa sas u b m o d u l eo fe n t e r p r i s e r e s o u r c ep l a n n i n g ( i s e r p ) ，a n do b t a i n e db e t t e rr e s u l t s k e yw o r d s ：t e x t i l em a n u f a c t u r i n gi n d u s t r y ，p r o d u c t i o ns c h e d u l i n g ，a r t i f i c i a li m m u n e a l g o r i t h m ，g e n e t i ca l g o r i t h m ，f u z z ys e t 1 1 1 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 作者签名：多i j 久往日期：m 7 年f z ，月zz ，日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密d ，在年解密后适用本授权书。 2 、不保密正 ( 请在以上相应方框内打“) 作者签名：乒i j 夫往 导师签名：、南象今 日期：纱哆年，乙月易日 日期：m 7 年，月珐日 浙江工业人学硕士学位论文 第一章绪论 1 1 课题研究背景 我国纺织行业具有悠久的历史，是我国工业化进程中的传统支柱产业，为我国现代化 建设作出了巨大的贡献【l 】。首先，是一个就业的产业，目前纺织产业吸纳的就业人口达到 1 9 0 0 万，解决了大量富余劳动力人口的就业问题。其次，是一个创汇的产业，由于我国纺 织行业比较优势突出，使得我国成为世界上纺织品和服装第一大生产和出口国，纺织服装 产业成为我国贸易顺差的一个重要来源，仅2 0 0 8 年全国纺织品出口达1 8 5 2 亿美元。虽然 我国纺织行业取得了不错的成绩，但随着我国宏观经济快速发展，纺织行业的发展将面临 越来越多的资源、环境等方面的约束，人民币持续升值，贸易环境不确定性等因素增强也 是行业不可避免的挑战。面对诸多因素的变化，要求企业在抓产品质量的同时，更要抓生 产效率，节约成本，提高利润率，从而提高企业的竞争力。 家纺企业( 专门生产家用纺织品的制造企业) 是传统的纺织企业，目前大部分的家纺 企业生产调度方法还停留在手工调度的层面上，缺乏科学的指导。而在家纺制造业发生巨 大变化的今天，一方面电子技术、计算机技术快速发展，制造设备的自动化水平和加工能 力得到了极大的提高，制造过程自动化水平也逐渐提高，使得生产调度问题变得更加复杂， 往往超过人的j 下常决策能力。另一方面，随着市场竞争的激烈化和国际化，出现了各种制 造理念和模式，如集成制造、m r p ( 物料需求计划) 、j i t ( 及时制制造) 、o p t ( 最优生产 技术) 、约束理论等【2 3 4 , 5 , 6 1 】，它们的核心思想无一不是为了适应市场小批量、多品种和更 具个性化的要求，缩短供货周期，控制产品成本，提高产品质量，提高设备利用率。所以 传统的依靠人来指挥生产加工过程的模式已经远远不能适应新的家纺企业制造环境的需 要，迫切需要研究有效的生产调度方法和建立生产调度软件系统，使得生产过程能够更加 合理和高效运行。生产调度的理论和方法属于软科学，运用它既不需要增加投资和设备， 又不需要增加人员，就可以提高生产和工作效率。因此，研究家纺企业生产调度的理论和 方法，对于提高企业的生产能力、提高产品质量、减少库存、降低运行成本、提高企业的 经济效益、最终提高企业的综合竞争力，有着重要的意义。 浙江：1 ：业人学硕十学位论文 1 2 研究现状与趋势 1 2 1 家纺企业生产调度特点 家纺企业是典型的小批量、多品种的生产制造企业，生产方式灵活、操作柔性强，生 产流程由整经、织造和后整理三部分构成。企业的生产车间相应的分为准备车间、织造车 间、和整理车间，织造车间是主要的加工场所，织造车间的生产调度问题是企业的核心( 如 不特殊说明，以下提到的家纺企业生产调度均为织造车间生产调度) 。与一般的制造企业 生产调度相比，家纺企业的生产调度具有如下特点；非一致机。即设备带工艺约束，特 定的设备只能生产特定的产品。准备时间和等待时问。设备在一个产品生产完成之后， 开始下一个产品之前需对生产线进行一定的调整。产品只有一道工序。同一产品可以 在多台机器上同时生产( 独特的特征) 。产品具有优先级( 独特的特征) 。这是根据客户 对企业的贡献大小来决定的。每隔一段时间做一次调度( 独特的特征) ，时间的长短由 订单的多少以及车间的生产情况来决定。批量订单的调度，即将所有订单中的同一产品 进行统一调度。 1 2 2 家纺企业生产调度研究现状 目前针对家纺企业生产调度i 口- j 题的研究已有一些成果，如g a ojq 等1 6 j 学者就家纺企 业生产调度问题进行了研究，分析了家纺企业的生产特点，其一为机器是非一致机，即机 器不是等同的，其二，机器具有特殊工艺约束，即每个机器只能加工满足某工艺条件的产 品。并根据其特点建立了数学模型，以拖后时间最小为目标，运用并行遗传算法对其求解。 但根据家纺企业的实际生产情况，以上学者的研究还没有完全考虑家纺企业生产调度问题 的复杂因素，首先，家纺企业的客户是有优先级的，根据客户对企业贡献的大小，不同的 客户具有不同的优先级，而对于不同优先级的客户，优先保证高优先级客户产品的交货期 是必要的。其次，家纺企业的产品加工时间受到诸多因素的影响，如原料特性、机器故障、 工人熟练程度等等，致使无法确定产品的加工时问。最后，不同的客户对于产品的交货期 的要求是不一样的，这使得交货期也不是一个确定的量。这些问题均是研究家纺企业的学 者未能考虑到并予以解决的，从而需要更深入的对家纺企业生产调度问题进行研究，进而 有针对性的解决这些问题。 本人深入企业生产车间，花费数月时间在浙江省杭州奥斯坦布艺有限公司、浙江金达 布业有限公司等多家家纺企业进行实地调研，在调研中，发现有的家纺企业还没有调度软 件，依靠人工进行调度，效率低下，且无法保证生产的连续性。而有的家纺企业虽然已经 一2 一 浙江工业人学硕士学位论文 有了调度软件，但软件的智能化程度不够高，大部分的操作依然是依靠人在调度界面上进 行操作，软件只能显示产品的生产状况，而不能进行下一步的生产，这虽比传统的调度方 式要先进，但依然无法满足现今的家纺企业。企业常陷入产品拖期、设备利用率低等困境， 使得企业的竞争力不高。 1 2 3 相关生产调度问题研究现状 生产调度问题的研究始于2 0 世纪5 0 年代，j o h n s o n 7 1 提出了解决车间调度部分特殊问 题的优化算法，代表调度理论研究的开始。直至五十年代未期的研究，主要是针对一些特 殊情况和规模较小的单机调度问题，研究范围较小，但这些研究为以后的经典调度理论打 下了牢固的基础。六十年代，人们丌始用一些普通的方法来解决调度问题，主要是一些数 学规划的方法i s , 9 1 ，但由于数学规划方法无法处理大规模的调度问题，有学者开始研究启发 式算法1o ，j 。七十年代，人们开始注意并重视调度复杂性【1 2 ，1 3 j 问题的研究，提出了用于研 究算法有效性和问题难度的计算复杂度理论，许多调度问题被证明为n p 完全问题，一般 很难找到快速解决这些问题算法。这使得启发式算法成为求解调度问题的重要算法。 七十年代后期，经典调度理论取得了重要的进展，并且作为一门应用学科已经基本成 熟，但是实际调度问题与经典调度问题还有相当的距离。现有的调度理论和方法对于解决 实际调度问题仍然是不够的，需要重新考虑和进一步扩展；当然，严重阻碍经典调度理论 研究取得重大进展和突破的关键还是调度问题的n p 性质。而实际的调度问题是复杂的， 没有规律可循，因此，仅仅依靠经典调度理论中基于解析优化的技术和方法，试图解决属 于n p 和n p 完全问题的实际调度问题，不可避免地会遇到难以逾越的障碍。 八十年代初丌始，诸多学者丌始尝试并致力于解决实际调度问题，调度问题由理论研 究转向应用研究阶段，这使得许多跨学科领域的技术和方法被应用到调度问题的研究中 去，调度问题从而成为一种跨学科的研究领域。八十年代后期，r o d a m m e r l 6 0 j 等对生产调 度的理论和实践方面的进展进行了总结，他们从七个方面论述了有关生产调度的技术和方 法，包括传统的调度理论、控制理论、人工智能和离散事件仿真等，同时也讨论了m r p i i 、 j i t 、和o p t 等技术的应用情况，生产调度无论在理论还是实践上都已经打破传统的界限。 九十年代，人们对调度问题的研究进入高潮【6 2 , 6 3 , 6 4 , 6 5 】，各种研究手段得到了充分的发挥， 同时还不断有新的研究工具被应用到调度研究当中。比较有代表性的技术有：遗传算法、 人工免疫算法、模拟退火算法、禁忌搜索算法等【1 4 , 1 5 , 1 6 , 1 7 , 1 8 】，智能调度已成为调度研究的主 流方向。 一3 一 浙江丁业人学硕士学位论文 1 2 4 生产调度方法发展趋势 调度研究的核心内容和重点是调度方法。虽然对生产调度问题的研究已经有来几十年 的历史，提出了各种调度方法，但至今尚未形成一套系统的理论与方法，已有方法基本上 可以归结为三种类型：基于数学规划方法、基于启发式调度方法和基于人工智能的方法。 1 基于数学规划方法 数学规划方法主要有：线性规划、混合整数线性规划、动态规划、拉氏松弛法、分枝 定界法【1 9 】等，它们共同的特点是寻求调度特例多项式时间最优或近似最优算法，而且随着 研究对象规模的扩大以及约束条件的复杂化，计算时间将成指数增长，因此，它们不适合 处理较大规模的调度问题。 2 基于启发式调度方法 启发式调度方法1 2 0 因其易于实现、计算复杂度低等特性，能够用于动态实时调度系统 中，多年来一直是学者们主要研究的方法之一，并不断涌现出新调度规则。p a n w a l k a rs 总 结了1 1 3 条调度规则【2 ，并将它们分为了三类：简单规则、复合规则、启发式规则。但启 发式调度方法是局部优化方法，难以得到全局优化结果。 3 基于人工智能的方法 近年来，人工智能技术被引入生产调度领域，是解决调度问题的有效途径。人工智能 方法是采用人工智能研究领域提供的方法解决各类生产调度问题方法的总称，主要包括以 下几个分支： 启发式图搜索算法 启发式图搜索算法是经典人工智能领域中图搜索策略的一种。图搜索策略就是把问题 求解过程用图或树的结构来描述。该方法包括：宽度优先、深度优先、a 或a 算法。 人工神经网络 人工神经网络i 冽是模仿生物脑结构和功能的一种信息处理系统。虽然目前的模仿程度 还处于低级水平，但已显示出一些与生物脑类似的特点，如信息的分布式存储和并行处理， 具有良好的自适应，较强的学习、记忆、识别功能等。神经网络已经在信号处理、模式识 别、目标跟踪、组合优化和专家系统等众多领域中获得巨大的成就。但神经网络的效率受 训练影响很大，并且在问题规模较大时，存在计算速度慢与结构参数难以确定的弱点。 遗传算法 遗传算法1 是一种基于进化论优胜劣汰、自然选择、适者生存和物种遗传思想的随机 优化搜索算法，通过群体的进化来进行全局性优化搜索。它以其很强的并行性和很高的计 浙江= 业人学硕七学位论文 算效率日益受到人们的关注。王凌对遗传算法在调度领域的应用进行了比较全面的总结 2 4 1 。但遗传算法还有许多问题需要进一步解决，如避免早熟收敛的问题，处理复杂带有约 束问题的能力，算法参数选择等。 粒子群算法 粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 是由k e n n e d y 和e b e r h a r t 等，于1 9 9 5 年 丌发的一种演化计算技术，来源对一个简化社会模型的模拟。其中“群( s w a r m ) ”来源于粒子 群符合m i l l o n a s 在开发应用于人工生命( a r t i f i c i a ll i f e ) 的模型时所提出的群体智能的5 个基 本原则。而“粒子( p a r t i c l e ) ”则是一个折衷的选择，因为既需要将群体中的成员描述为没有质 量、没有体积的，同时也需要描述它的速度和加速状态。 由于p s o 算法概念简单，实现容易。短短几年时间p s o 算法便获得了很大的发展，并 在一些领域得到应用。在生产调度领域，也有一些学者开始采用粒子群算法解决生产调度 问题。如贾兆红人利用p s o 算法求解柔性车间调度系统，并取得不小的成果【2 5 1 。但粒子群 算法仍存在一些不足，像分析方法还不成熟、如何吸引其他进化类算法的优势来弥补自身 不足等问题仍然存在。 免疫算法 1 9 7 4 年美国诺贝尔奖获得者，生物学家、医学家、免疫学家j e m e 提出免疫网络理论 而引起广泛关注1 2 6 1 。继该文之后，f a m l e r 【2 7 1 、p e r e l s o n f z 引、b e r s i n i l 2 9 1 、v a 旺l a f 3 0 l 等理论免疫 学者分别在1 9 8 6 年、1 9 8 9 年和1 9 9 0 年发表了有关论文，在免疫系统启发实际工程应用方 面做出突出贡献；其他的研究学者如f a r m e r 关于免疫系统的研究是具有创造性和开拓性的 工作，他们的研究工作为建立有效的基于免疫原理的计算系统和智能系统的发展丌辟了道 路。另外v a r e l a 在1 9 8 9 年讨论了免疫网络以某种方式收敛的思想以及免疫系统能够通过 产生不同的抗体和变异适应新环境的思想，都为使免疫系统成为有效的解决工程问题的灵 感源泉做出巨大贡献。由此诞生了一个崭新的研究领域人工免疫系统【3 1 , 3 2 ，3 3 1 。 所谓人工免疫系统( 从工程和科学的角度讲) ，就是研究借鉴生物免疫系统各种原理 和机制而发展的各类信息处理技术、计算机技术及其在工程和科学中应用而产生的各种智 能系统的总称。免疫算法【蚓是伴随着人工免疫系统发展起来的一种新兴优化算法，是一种 模拟生物免疫系统功能的全局搜索智能算法，凭借快速的收敛能力和强大的全局搜索能 力，为调度问题的研究提供了新的思路。目前，国内外已有一些基于免疫算法的调度研究 方面的文献，但相比于其他应用领域，免疫算法在调度方面的研究和应用还相对较少，在 国外，o r h a ne n g i n l 3 5 l 等提出一种人工免疫算法解决混合流水生产调度问题， 浙江一：业人学硕 ：学位论文 m c h a n d r a s e k a r a n t 3 6 】等采用人工免疫算法对作业生产调度问题进行了研究，并对不同规模 的作业车间调度问题进行仿真，获得比较好的效果。r i n a a g r w a l 3 7 1 等对带资源约束生产调 度问题进行研究，并采用人工免疫算法对其求解。z x o n g 【3s 】等采用克隆选择算法解决柔 性作业车间调度问题，并对变异方式进行研究，取得较为理想的效果。m o s t a f ar a l 3 9 】对免 疫遗传算法进行研究，并应用于混合多任务调度问题中，结果表明要优于目f i 同类算法。 在国内，徐震浩、顾幸生【4 0 】对不确定条件下具有零等待的流水车间生产调度问题进行研究， 并提出了解决此类问题的免疫调度算法。常型4 l 】等将免疫原理引入遗传算法中，加快了进 化速度，并对典型车间调度问题进行求解，结果表明算法有效，钱海、王煦法1 4 2 1 等对人工 免疫算法进行研究，引入免疫记忆因子，提高算法的收敛性和鲁棒性，并应用在实际的生 产调度中。由以上文献可以看出，免疫算法在车间调度领域的研究国外学者的研究时间要 早于国内，同时研究成果也要比国内丰富。随着研究的深入，免疫算法已经成为国内外的 一个研究热点。然而免疫系统的机理非常复杂，现有的免疫算法还不能很好的满足时间需 要。故需要针对现有免疫算法存在的不足提出一些性能更好的改进免疫算法并积极应用于 调度领域。 、 1 3 章节安排 第一章：绪论。介绍了课题的研究背景与意义、家纺企业生产调度问题的研究现状、 目前生产调度问题研究存在的不足，为后面的研究明确的方向。 第二章：家纺企业确定性生产调度问题的研究。本章建立了家纺企业确定性生产调度 模型，提出了一种新颖的人工免疫算法对其求解，采用向量组编码的方式进行编码，通过 克隆、变异及一种新颖的基于浓度的种群多样性更新选择方法，并与多种算法进行比较， 仿真结果表明，该算法能更快更准确地收敛到全局最优。 第三章：家纺企业不确定性生产调度问题的研究。在研究确定性生产调度问题的基础 上，对具有模糊加工时间和模糊交货期的调度问题进行深入研究，将模糊加工时间最小与 客户满意度最大作为目标。并针对模糊车问调度问题的特征，分别采用自适应遗传算法和 改进人工免疫算法对其求解。仿真结果表明，提出的算法能很好的处理家纺企业模糊调度 问题。 第四章：生产调度系统的应用。将前面家纺企业生产调度问题的研究成果，做了个简 单的应用，集成到家纺企业生产调度中。 第五章：总结与展望。对本文的研究工作进行总结，并对迸一步的研究作了展望。 一6 一 浙江1 ：业人学硕+ 学位论文 第二章家纺企业确定性生产调度研究 2 1引言 家纺企业确定性生产调度问题是指在加工时问和交货期确定的情况下，对车间生产进 行调度。由于家纺企业的生产模式是面向批量订单的生产模式，即企业是根据订单来安排 生产，每张订单有几种甚至几十种产品，每种产品要求的数量较小，生产时将不同订单的 相同产品进行统一调度，且产品具有特殊工艺约束和优先级约束等，这些客观因素提高了 问题的复杂性。这使得一般的调度算法无法在家纺企业车间调度中取得理想的效果。 目前专门针对家纺企业生产调度问题的研究还不多见，但类似的研究已有不少的成果。 如赵韩等提出了一种改进的自适应免疫遗传算法，对多目标柔性车间调度问题进行求解 1 4 3 j ，雷德明、吴智铭利用粒子群优化算法解决多目标作业车间调度问题 4 4 1 ，王自强，冯博 琴以最小完工时间为目标，提出一种免疫算法求解f l o ws h o p 调度问题1 4 5 】等等，这些成果 虽然能解决特定的车间调度问题，但从实际应用上看，仍然满足不了家纺企业实际实际生 产调度问题的需要。由于家纺企业的加工机器是非一致机，对于不同的机器，所能加工的 布料的宽度不一样；同时机器加工受还受特殊工艺的约束，即不同机器所能加工的花饰不 一样；特别是，产品具有优先级。对于家纺企业来说，产品的优先级不是传统意义上工艺 的先后顺序，而是由于客户级别的差异而产生的。一般说来，企业会根据多年来客户订单 数量及客户本身企业规模的大小等因素将企业客户分成不同的级别，客户级别越高，客户 所下的订单级别就越高。相比级别低的订单，要求级别高订单的产品拖期概率小。企业这 样做的目的是在保证级别高客户前提下，尽量挽留住级别低的客户，提高企业竞争力。 家纺企业的车间调度问题在数学上是n p 完全问题，即使是对单一优化指标的问题，当 设备单元数或产品数目较多时，用数学方法求解也是很困难的。虽然一些随机算法如模拟 退火算法具有较好的求解结果，但由于家纺企业车间调度问题具有高度组合性，这种算法 所需计算时间较长，特别是在问题规模较大时表现更为突出。本章采用提出的新颖的人工 免疫算法对问题进行求解，并与相关文献中提出的各种算法进行比较，仿真表明，本章提 出的算法是有效的。 浙江 ：业人学硕士学位论文 2 2 家纺企业确定性车间调度模型 根据家纺企业的实际生产情况，家纺企业的确定性生产调度模型可描述为：假设 j v = l ，2 ，a 玎 为产品集合，m = 1 ，2 ，a 聊 为机器设备的集合，每个产品仅需一道工序，可由此 m 台机器中的某一台完成生产任务，每台机器一次只能加工一个产品。此m 台机器可生产 的产品类型受限制，所有能加工产品，的机器集合为q ，0 = 1 ，2 a 刀) ，且每台机器上的加工 时间确定，p o 表示产品在机器i 上的加工时间。t 表示单位时间机器f 的损耗，厂( 歹) 表 示生产产品歹所需要的原料成本，c _ ，和嘭分别表示产品歹的完工时间和交货期，且交货期 时间确定。口，为产品_ ，的单位提前惩罚系数，若产品，提前生产，则对产品进行惩罚， 惩罚值为口，m a x ( 0 ，d j c ，) ，乃为产品的单位拖后惩罚系数，若产品拖期，则对产品，进 行惩罚，惩罚值为色m a x ( o ，巳一d j ) 。产品之问有着一定的优先生产顺序，但不是工艺上的， 乃表示产品的优先级系数，当且仅当产品拖期时，z 对拖期惩罚值起加权作用。w 表示 单位时间人工成本。问题就是在满足约束条件下，寻找一个最优调度方案，实现产品成本 最小、总拖期时间最短或完工时间最短等目标，问题的总表达式表示为： 而们2 ：又a 妙m a x u ( 0 d 写景a p m ，a x 耽( 0 0d a 范 c 2 m + 2 口f ， ，一c f ) +3 z ，c ，一f ) + a 4 ：；l c7 而且问题满足如下条件 ( 1 ) 每台机器每次只能加工一个产品，且每个产品只能由一台机器加工 ( 2 ) 加工一旦开始，在加工未完成前，中途不能中断。 ( 3 ) 产品只能由本身可加工机器集合中的机器加工。 以上条件用数学表达式表示为 三。x 妒= 1 ( 2 2 ) 以= o 或1i mj n( 2 3 ) 所0 当且仅当f = q ( 2 4 ) a j = 0 或1i ( 1 4 )( 2 5 ) 在表达式( 2 1 ) 中，目标函数为4 、a 2 、a ，、a 。的自由组合，对于不同的目标，彳，、 浙江1 ：业人学硕士学位论文 a 2 、a 3 、彳。的取值不同，如完工时间最短，贝t ja , 、a 2 、a ，、a 。的取值为0 、0 、0 、l ， 又或者拖后时间最短的同时兼顾完工时间最短，n a z 、以、a 3 、以的取值为0 、0 、l 、1 等等。表达式( 2 2 ) 和( 2 3 ) 表示产品只能由一台机器加工，表达式( 2 4 ) 表示产品具 有工艺约束，只能由指定的机器加工，表达式( 2 5 ) 表示4 只能取0 或者1 。 2 3 算法设计 人工免疫算法是受免疫系统的启发而设计的一种具有全局搜索能力的优化方法，具有 自适应性、高度并行和分布性等特点。目前人工免疫算法虽然在调度领域已有一些应用， 但仍存在一些需要深入探讨的问题，这些问题在不同程度上影响算法的性能：编码方式。 目前存在的编码方式很多，有二进制编码、格雷码编码、实数编码等等，不同的编码方式 具有不同的优缺点，采用何种编码方式将对算法性能产生至关重要的影响。局部搜索算 法。局部搜索算法是提高搜索速度，实现快速搜索，减少搜索时闻的方法，而不同的局部 搜索算法对算法性能的影响也不一样。采用何种方法产生新抗体也会对算法性能造成影 响。若完全由免疫算予产生新抗体，这将使得新抗体的产生不具备随机性，从而使得算法 的多样性无法保证，在经过n 次迭代以后，该算法仍然有可能陷入局部极值而不能收敛到 全局最优。采用何种选择方式，也将对算法造成影响。若仅以个体亲和度为选择指标， 这容易使得亲和度值较小的抗体很难进入下一代，而种群中相似亲和度抗体增加，导致算 法多样性差，使算法陷入未成熟收敛。所以需要对选择方式进行研究。 上面已经对一些影响免疫算法性能的地方进行讨论，所以在这里我们对一般人工免疫 算法进行改进，首先从编码问题入手，为避免二进制与十进制的相互转换致使计算量增加， 采用实数的向量组实数编码；其次提出一种局部搜索算法加快搜索速度，从而减少收敛时 间；最后采用一种新的种群更新方法，在保证种群质量的同时保证种群多样性。算法的的 基本框架如图2 1 。具体步骤如下： 步骤l 随机产生满足约束条件的初始抗体群，设定抗体规模为，记忆细胞群体为地 步骤2 评价种群。对所有抗体的适应值进行计算。 步骤3 克隆和变异。对种群中的每个抗体进行克隆操作，克隆尺寸大小为n c s ；而后， 对每一个克隆，进行变异操作。每一个克隆，变异后的子抗体与原抗体进行竞争，且仅有 一个个体存活。若产生的后代中最优个体优于原抗体，则用此最优个体替代种群中原抗体， 否则种群中原抗体不变。 一9 一 浙江工业人学硕士学位论文 步骤4 局部搜索。对种群中的每一个抗体，进行局部搜索，寻找更优抗体。 步骤5 计算相邻两次迭代的种群的平均适应值，如果差的绝对值小于预先设定的阀 值万，则执行步骤6 ，否则转向执行步骤2 。 步骤6 种群多样性更新选择。 步骤7 重复步骤2 n 步骤6 的过程，直到达到了设定的收敛标准为止。 初始化种群 评价种群 皇 克隆 皇 变异 皇 一 选择执体 篁 硒部搜索抗体 两代种群甲均适应值的 的绝对值是否小。j ：6 土! 种群多样性 一，一一 组成新种群 爨景囊雾鼍 卜!终j 卜条件 免疫记忆 图2 1算法土流程框架 2 3 1 编码设计 由予免疫算法的优化过程不是直接作用于问题参数的本身，而是在一定的编码机制对 应码空间上进行的，因此编码方式的选择是影响算法性能与效率的重要因素。本章根据问 题的求解特征，采用基于向量组的编码方法。编码设计如下：对每个产品_ ，。o n ) ，如加 工的机器为岛 q 岛，则定义基因为二维向量g ；= 匕 ，于是个体的基因编为 浙江1 ：业人学硕士学位论文 k 。，g ：a ，g 。】= 叠j p ：2 人a 乏 ，其长度等于待加工产品的总数万。 抗体的译码步骤为： ( 1 ) 令i = l ； c 2 ，读取基因位g ；= 耋 ； ( 3 ) 将工件z 依次分配到机器q 上； ( 4 ) i = f + 1 ； ( 5 ) 如果i 1 0 | 6 0 - 1 0 据规模 幽2 - 8i a i 、a i s 刊c s a 算j 圭的运行时间对比嘲 山表2 3 可知，i a i 算法计算的最优值和平均值都要优于其他四个算法，并且随着数据 规模的扩大，i a i 算法所具有的优势更加明显；由图2 8 丁以看出，虽然髓着问题规模的扩 大i a 算法、a i s 算法跟c s a 算法所需要的计算时间都在增长，但可以看到i a i 算法的运 算时问相对于问题规模的埔长率明显要比其他算法要米的小。综上所述可知，对于小同规 模的家纺企业确定性生产调度问题，i a i 算法是有效的。 2 4 3 参数敏感性分着r 通过以上实验发现，i a i 算法的性能受局部搜索最大次数s 和多样性参数占的影响， 不同的参数的设置将影响算法的收敛速度和算法计算时问，为了确定局部搜索最大次数 s 一和多样性参数引拊取值，这里来对参数s 和参数d 进行分析。这里先束讨论局部搜 索的交换次数s 一，如果局部搜索次数，一设置的过犬，虽然能够获得较大的几率得到更 优的解，但将花费更多的计算时间在局部搜索j ：，而如果将s 啮设置的过小，义势必使得 种群的收敛速度过慢。所以这罩埘j 一进行分析，尽量找出最适合交换次数，j 郴 满足收 -a 浙江l 业大学硕十学位论文 敛速度和计算时间的要求。 这晕设置种群的数量为5 0 ，记忆细胞为种群数量的3 0 ，迭代次数为5 0 参数占为 0 0 1 ，采用的数据规模为l o o x l 0 ，分9 4 对5 一为0 ，1 0 ，2 0 ，3 0 ，4 0 ，5 0 t 6 0 时进行仿真， 每个参数，一都将运行1 0 次，然后取平均值。仿真结果如图2 - 9 所示，从陶中可知，随着 s 一的增大，拖后时自j 在减小，即随着s 的增人，算法的收敛速度在加快；不难发现，o - 1 0 区间的变化率是最快的，然后依次变缓，在4 0 6 0 的区间拖后最优值基本没有变化，在2 0 4 0 i 式r j 的变化也不是很大。虽然当s 啡等r6 0 的时候，能够取得极小的蛀优值，但这势必要 增加大量的计算量，从而增加计算时唰，综合考虑收敛速度与计算时间的园索，j 设簧应 该保持在15 - 3 0 这个| 1 l j ，然后根据具体的数据规模稍加变动。但根据实验效果，这晕推 荐5 。设置为2 0 。 4 0 0 3 5 0 3 0 0 2 5 0 尽 督2 0 0 埋 耀 1 5 0 1 0 0 5 0 2 03 0 4 0 5 0 局部搜索次数 目2 - 9局部搜索次数对算法的影响 对于参数引竹分析，这毕同样采用卜面对s 的分析方法，进行相同的参数设簧，其中 j 设置为2 0 t 然后分别对d 为0 0 0 0 0 1 ，0 0 0 0 0 5 ro 0 0 0 l ，0 0 0 0 5 ，0 0 0 1 - 0 0 0 5 ，0 0 1 ， 0 0 5 ，01 ，0 5 时的拖后母优值进行计算，计算结果如图2 1 0 所示，山图中可知当占大 2 3 浙江j 业大学硕+ 宁位论文 于0 0 1 且小于0 5 时，拖后最优值处于一种递增的状态，而当占大于。且小foo l 的时候， 拖后虽优值处于下降的趋势，即当j 为0 0 1 的时候，能够取得极小最优值。所以这里设置 6 为o0 1 。 1 1 0 一一 1 1 l l 厘8 0 营 也 耀7 0 2 5 本章小结 i f 莳r 百i _ 百i r 百i _ 、焉面而r 五5 多样性挣制参数 幽2 - 1 0 参数占对掉法的影响 本章针对家纺企业车叫调度问题，建立确定性车自j 调度模型，并根据家纺企业牛产调 度问题的特性，设计了一种新颖的人工免疫算法，确立了适合调度问题的编码方法，给出 了抗体和抗原的评价雨数，设计了变异算子及局部搜索算法。并与改进遗传算法算法、免 疫遗传算法、选择克降算法以及人工免疫算法进行对比分析，仿真结果表明，本章所提出 的算法足有效的。 浙江1 业人学硕士学位论文 第三章家纺企业不确定性生产调度研究 3 1引言 上一章已经对家纺企业确定性车间生产调度问题进行研究，但在实际的生产过程中， 家纺企业除了确定性的生产调度问题，还有不确定性的生产调度问题，即产品加工时间和 产品交货期不确定的生产调度问题。这是出家纺企业的特殊性造成的，如原料特性、操作 工人的熟练程度、机器设备老化等等，都将影响产品的加工进度，使得加工时间不确定， 而同一批产品可能来自不同的订单，不同订单的交货期往往是不一样的，从而导致产品的 交货期不同。 目l j ，对于不确定的生产调度问题，已有一些研究成果。在模糊加工时间方面，程八 一等建立模糊批加工时间和模糊批间隔时间的制造模型，并对其求解h 7 1 ，王莉【4 8 1 等对带有 交货期窗口的模糊加工时间的f l o w - s h o p 调度问题进行了研究。卢冰原1 4 9 j 等对具有模糊加 工时间的柔性作业车自j 最小化制造跨度问题进行了研究，并采用粒子群对其求解，实例验 证了算法的有效性。j p 采用混合遗传算法对模糊加工时间下并行机调度问题进行研究i 5 们。 在模糊交货期方面，吴会江对模糊交货期的单机调度问题进行了研究【5 。柳毅、叶春明对 制造业在模糊交货期下的准时制生产调度问题进行了研究，并运用微粒子群技术对其求解 1 5 2 】。t a d a h i k om u r a t a 等对模糊交货期下的多目标流水调度问题进行了研究【5 3 l ，谢源对一类 模糊交货期和混合优先约束下的单机调度问题进行了讨论1 5 4 j ，同时以最大化模糊交货期和 混合优先约束的最小满意程度为目标，通过搜索非支配解，得到最优调度。沈兵虎等针对 模糊交货期下的流水调度问题【5 卯，提出了一种改进的微粒算法对其求解，具有更好的全局 最优性和收敛性。除了上面这些对模糊加工时间和模糊交货期分开研究的问题，也有不少 学者针对模糊加工时间以及模糊交货期这样的混合问题进行研究，m a s a t o s h is a k a w a 是国 际上比较早研究该问题的学者之一，他对在模糊加工时间和模糊交货期条件下的作业车间 调度问题进行研究，并提出一种改进遗传算法对其求解 5 6 , 5 7 。李富明等【5 3 1 在m a s a t o s h i s a k a w a 工作的基础上，不仅考虑模糊加工时间和模糊交货期，还考虑了工件的某道工序有 多台机器可以选择，提出了极大化最小客户满意度为目标，并给出了算法设计。雷德明等 研究了具有模糊加工时间和模糊交货期的多目标作业车间调度问题，以最大化最小一致指 2 5 浙江工业大学硕十学位论文 标和最小化模糊最大完成时间为目标，并设计了算法对其求解【5 引。由以上这些文献可以知， 现在在车间调度领域，针对模糊车间调度问题的研究，主要集中在作业车间的模糊调度问 题，且大部分是对模糊加工时间或模糊交货期单一情况进行研究，虽然也有些学者对加工 时间和交货期进行研究，但他们的满意