（计算机软件与理论专业论文）线束行业的分级调度算法及信息可视化研究.pdf

线束行业的分级调度算法及信息可视化研究 摘要 面向订单的多品种、小批量生产模式，正在成为中小型线束企业的主导生 产方式。但该模式所带来的企业生产产品种类多、时间紧、生产过程作业轮换 频繁等情况，极大地加重了车间作业调度的负担。同时，对于繁杂的生产调度 所引起的大量相关信息的感知和理解也变得愈加困难。 本文针对以上问题，以合肥得润家电线束生产车间为研究对象，采用基于 q 学习和模拟退火遗传算法相结合的分级调度策略进行作业排产，并通过多种 可视化方式从不同角度展示生产调度信息，为公司管理者掌握生产状况，工作 人员快速获取有益信息，进而加快信息处理能力提供了有效途径。本文研究工 作主要包括以下三个方面： ( 1 ) 根据得润车间作业排产实际情况，建立分级调度模型：对于粗粒度的前工 序、后工序，采用q 学习算法计算最迟交期；对于前、后工序内部的工序 调度只考虑由上层调度得出的当日须安排的作业，采用模拟退火遗传算法 按交期优化排序。鉴于实际情况的复杂多变，允许人工干预，调整系统调 度结果，直至满足生产需要，安排生产。 ( 2 ) 生产调度信息的可视化显示。基于生产调度信息独有的错综复杂关系、含 类别型层次结构的特点，采用星状图来展现作业调度中各种信息及其关联 关系；运用甘特图，来展现车间各作业任务调度结果；仿真车间生产现场， 实时掌握更细粒度的生产信息；使用诸如条形、折线、扇形等统计图统计 分析生产数据，为企业分析问题、发现问题提供基础。 ( 3 ) 设计实现生产调度信息可视化系统。针对得润车间的实际生产现状，采用 三层b s 模式构架，实现了车间作业自动排产和人工辅助调整相结合的调 度方式，并结合多种可视化方式反馈、展示生产调度信息，在提高企业生 产效率、透明化管理方面取得了良好效果。 关键词：分级调度；信息可视化；q 学习：模拟退火遗传算法：星状图 本论文主要工作得到了国家自然科学基金项目“科学计算中面向建模的多态机理研 究”( 6 0 6 7 3 0 2 8 ) 、安徽省高等学校优秀青年人才基金项目“功能模型创新推理过程的可视 化方法研究”( 2 0 1 0 s q r l 0 1 3 z d ) 莉1 合肥市科技局项目“基于信号量机制的生产调度及其 可视化”( 2 0 0 8 1 0 0 4 ) 的共同资助。 r e s e a r c ho nh i e r a r c h i c a ls c h e d u l i n ga l g o r i t h ma n d i n f o r m a t i o nv i s u a l i z a t i o ni nw i r i n gh a r n e s se n t e r p r i s e a b s t r a c t m u l t i 。v a r i e t i e s s m a l l b a t c hp r o d u c t i o ni sb e c o m i n gt h ed o m i n a t em o d ef o r m e d i u ma n ds m a l le n t e r p r i s e s h o w e v e r ，m o r ek i n d so fp r o d u c t i o n ，t i g h ts c h e d u l e a n df r e q u e n ts w i t c h i n go ft h ep r o d u c t i o np r o c e s so p e r a t i o n sb r o u g h ta b o u tb yt h e m o d e ，g r e a t l yi n c r e a s e st h eb u r d e no fj o bs h o ps c h e d u l i n g a tt h es a m et i m e ，t h e p e r c e p t i o na n du n d e r s t a n d i n go fal a r g en u m b e ro fr e l e v a n ti n f o r m a t i o nc a u s e db y c o m p l e xp r o d u c t i o ns c h e d u l i n gh a sb e c o m em o r ed i f f i c u l t t os o l v et h ea b o v ep r o b l e m ，t h ed i s s e r t a t i o nm a i n l yt a l k sa b o u tt h ew i r e h a r n e s sp r o d u c t i o nw o r k s h o po fh e f e id e r u ne l e c t r o n i cd e v i c e sc o ，l t d a h i e r a r c h i c a ls c h e d u l i n gp o l i c yb a s e do nq l e a r n i n ga n ds i m u l a t e da n n e a l i n gg e n e t i c a l g o r i t h mi sa p p l i e d ，a n dt h ep r o d u c t i o ns c h e d u l i n gi n f o r m a t i o ni sd i s p l a y e df r o m d i f f e r e n ta n g l e st h r o u g hav a r i e t yo fv i s u a l i z a t i o nm e t h o d s ，w h i c hp r o v i d ea n e f f e c t i v ew a yo fk e e p i n ga b r e a s to ft h ep r o d u c t i o ns t a t u sf o rc o r p o r a t ee x e c u t i v e s ， i n c r e a s i n gt h e i ra b i l i t yt oa c c e s sa n dd e a lw i t he f f e c t i v ei n f o r m a t i o nf o rs t a f f t h e m a i nr e s e a r c hw o r ki sl i s t e da sf o l l o w i n g ： ( 1 ) a c c o r d i n gt ot h ea c t u a ls i t u a t i o no fj o bs h o ps c h e d u l i n gi nd e r u n ，a h i e r a r c h i c a ls c h e d u l i n gm o d e li sb u i l t ：f o rt h ec o a r s e g r a i n e dp r o c e s sb e f o r e a n da f t e r ，ql e a r n i n gi su s e dt oc a l c u l a t et h el a t e s td e l i v e r y ；f o rt h ep r o c e s s s c h e d u l ei n s i d eo fp r o c e s sb e f o r ea n da f t e r ，o n l yc o n s i d e r i n gt h ew o r kn e e d e d t ob ea s s i g n e do nt h a td a y , s a g ai su s e dt os o r tb y d e l i v e r y i ft h es c h e d u l i n g r e s u l tc a n tm e e tt h ea c t u a ln e e d so fp r o d u c t i o n ，m a n u a li n t e r v e n t i o ni s a l l o w e dt oa a ju s tt h es y s t e ms c h e d u l i n gr e s u l t ( 2 ) v i s u a l i z a t i o nd i s p l a yo fp r o d u c t i o n s c h e d u l i n gi n f o r m a t i o n s t a rd i a g r a mi s u s e dt od i s p l a ya l lk i n d so fi n f o r m a t i o na sw e l la st h e i ra s s o c i a t e dr e l a t i o n s ； g a n t tc h a r ti su s e dt os h o wjo bs h o ps c h e d u l i n gr e s u l t s ；f i e l ds i m u l a t i o ni s u s e dt or e f l e c tr e a l - t i m ep r o d u c t i o ni n f o r m a t i o n ；s t a t i s t i c s ，s u c ha sb a r ，l i n e ， p i ec h a r t s ，i su s e dt oa n a l y z ed a t a ，t h e r e b yf i n dp r o b l e m s ( 3 ) d e s i g n a n d i m p l e m e n t a t i o n t h e p r o d u c t i o ns c h e d u l i n g i n f o r m a t i o n v i s u a l i z a t i o ns y s t e m a i m i n ga tt h ea c t u a lp r o d u c t i o ns i t u a t i o ni nd e r u n ， b a s e do nt h r e e - t i e rb ss t r u c t u r et h es y s t e mc a nf i n i s ha u t o m a t i cp l a n n i n ga n d m a n u a la d ju s t m e n t s ，c o m b i n e dw i t hf e e d b a c kf r o mav a r i e t yo fv i s u a l i z a t i o n m e t h o d sw h i c hd i s p l a ys c h e d u l i n gi n f o r m a t i o n t h es y s t e ma c h i e v e sg o o d r e s u l t si np r o d u c t i o ne f f i c i e n c ya n dt r a n s p a r e n c ym a n a g e m e n t k e y w o r d s ：h i e r a r c h i c a ls c h e d u l i n g ；i n f o r m a t i o nv i s u a l i z a t i o n ；ql e a r n i n g a l g o r i t h m ；s i m u l a t e da n n e a l i n gg e n e t i ca l g o r i t h m s t a rd i a g r a m ； 图1 1 图1 2 图1 3 图1 4 图1 5 图1 6 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 插图清单 家电、汽车线束1 j a v ac o l l e c t i o n sf r a m e w o r k 成员构成描述3 j a v ac o l l e c t i o n sf r a m e w o r k 成员构成图示3 合肥得润业务流程图8 生产调度信息可视化设计流程图9 生产调度相关信息示意图9 某线束生产流程1 3 任务前驱图1 5 基于m e t r o p o l i s 规则的q 学习算法流程图1 9 选择策略示意图2 1 s a g a 算法流程图2 2 前后工序调度问题的t p g 2 3 任务关系约束图2 5 信息可视化流程参考模型2 8 星状图3 0 星状图的可视化元素配置示意图3 0 星状图的动态布局3 l 节点拖拽示意图3 2 节点伸缩示意图3 3 车间部分作业调度甘特图3 4 示例统计图j 3 5 其他示例图3 5 系统架构设计图3 8 服务器端体系结构3 8 订单录入3 9 车间生产任务3 9 当日作业调度甘特图3 9 单个作业调度时刻表3 9 某作业调度星状图3 9 星状图信息节点切换示意图4 0 现场仿真示意图4 0 统计图4 1 表2 1 表2 2 表2 3 表2 4 表2 5 表2 6 表2 7 表2 8 得润车间某日某组生产任务列表2 2 各作业相关生产参数列表2 3 任务乃在处理机j p i 上的平均运行时间死i 2 4 算法性能比较表2 4 当日需开始作业列表2 4 作业乃在处理机p j 上的平均运行时间乃j ( h ) 2 5 各算法计算参数比较表2 6 部分调度结果表2 6 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得 盒壁些太堂 或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示谢意。 学位论文作者签字：枉罗拐签字日期：砂乒年月酷日 学位论文版权使用授权书 本学位论文作者完全了解 金胆王些太堂 有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权 金g 巴蚤些态堂 可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名： 签字日期：说年 ( 彩琢 彩月名日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 签字日期： 电话： 邮编： 致谢 值此论文完成之际，首先要感谢刘晓平教授。刘老师一丝不苟的作风、严 谨求实的态度、踏踏实实的精神，不仅授我以文，而且教我做人。刘老师治学 严谨、学识渊博，他对学科发展的前瞻性认识、敏锐独到的眼光，都给我以深 远的影响。在此向刘老师表示最诚挚的感谢和敬意，并送上我最真诚的祝福。 感谢v c c 实验室的诸位老师，你们对问题的分析能力，对研究方向的把握 能力都给我留下了深深的印象。徐老师、路老师对本文工作的指导提出了许多 独到的建议和宝贵的意见，在此对两位老师的谆谆教诲表示由衷的感谢。 感谢石慧师姐在科研上和生活上对我的帮助。她对问题的分析和解决能力 给我留下了深刻的印象。 感谢实验室的唐益明、金灿、沈冠町、余烨、陈欣、李丹、彭军、李忠泽、 王晓静、季浩、阎峰、谢文军、吴敏、钱晶晶等同学，与你们共同学习使我受 益匪浅。 感谢我的家人，他们在精神上和生活上给予我莫大的支持和鼓励。 最后，向未提及的其他所有关心和支持我学业的老师、同学和朋友表示最 真诚的感谢和祝福。 作者：杜琳 2 0 1 0 年3 月2 2 日 第一章绪论 11 研究背景 1 1 l 线柬行业概述 电子产品或汽车的设计功能要在使用过程中最充分地展示出来，全靠强劲 的动力和各种信号的指挥。线束就是产品动力和各种信号分配系统的传输载体， 是产品电路的网络主体。特别是汽车线束，素有汽车神经之称。随着电子技术 和汽车工业的发展线束产业也蓬勃兴起。线柬是指将电线电缆与端子( 连接器) 压接后，两端再插上注塑件形成的连接电路的组件【”，如图11 所示，广泛应 用于汽车、航天工业、地铁轻轨、船舶、家用电器、计算机和通讯设备、各种 电子仪器仪表等各个方面，在我国具有强劲的市场需求和广阔的发展前景。 图11 家电、汽车线柬 目前，国内约有大大小小几百家汽车、家电线束加工厂，其规模太小、水 平高低各不相同，主要分布在上海、北京、天津、东北地区、浙江、江苏、广 东、福建、山东、安徽、重庆等省市。他们大部分为中小型企业，具有自己独 特的特点1 2 】： ( 1 ) 中小型线束企业比大型的线束企业面l 临更激烈的市场竞争，企业要想凭借 利润率不高的线束产品在市场上占有一席之地，就必须大幅降低成本、加 大产量、提高生产率来获取一定的利润。 ( 2 ) 随着轿车家庭化、家用电器平民化，对汽车、家用电器等整机的配置要求 也将愈来愈多样化、复杂化、非标准化，线束厂生产几万套、甚至几十万 套完全一样线束的局面将被打破。线束生产呈现出“多品种，小批量”的 特点线束产品和服务都在走向定制化。 ( 3 ) 由于客户需求变化越来越快，线束企业的订单变化频繁、物料替代复杂。 ( 4 ) 线束作为汽车、家用电器的中枢神经，对质量要求比较高，很多整机厂对 线束企业的质量要求苛刻到小于l p p m 。而且一旦线束产品出现质量不符 合事件，很难修复使用，高质量事故直接导致企业过多的浪费。 f 5 1 线束产品相对简单，工艺路线也不是很复杂。 ( 6 ) 中小型线柬企业的自动化程度偏低，企业内人员素质总体水平不高，企业 的资金和技术力量相对薄弱。 ( 7 ) 中小型线柬企业正处于成长阶段，企业的内外部环境处于不断的变化和发 展中，与整机厂有一定的附属关系。 随着全球生产制造集成化和信息化潮流的涌动，线束行业正面临着一场新 的挑战。如何利用高速发达的信息化建设，先进便捷的自动化设备，在激烈的 市场竞争中降低生产成本，提高工作效率，增强企业灵敏度，已经成为线束行 业发展的关键。而生产调度作为组织完成生产作业任务的重要手段和控制协调 生产过程的直接操作，正是企业生产实现低成本、高效率、高柔性和高可靠性 的保障。事实证明，有效实用的调度方法和优化技术的研究与应用已成为先进 制造技术实践的基础1 3 j 。因此，生产调度问题的研究是历来企业发展过程中不 可逾越的关键。 1 1 2 信息可视化 信息时代，网络的快速发展使得大量的信息涌向人们生活的各个方面。无 论是居家休闲还是在办公室工作，也无论是在商场购物还是在股票交易所进行 交易，人们都要面对大量的信息和数据。这些信息给人们带来了前所未有的方 便，使得人们能够更全面地获取自己所需的有价值的资源。同时，这些海量的 信息也使人们为之焦虑。除了需要对这些海量数据进行存储、传输、检索及分 类外，人们更迫切需要了解数据之间的相互关系及发展趋势。实际上，在激增 的数据背后，隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析， 以便更好地利用这些数据。信息可视化技术正是在此背景下应运而生。 所谓信息可视化，就是利用人们对可视模式的自然识别，将数据、信息以 及知识转化为视觉形式的过程【4 】。在这个过程中，信息可视化主要采用视觉形 式对信息进行选择、变形、替代等操作，将抽象的信息转换为一种人类熟知的 视觉形式，使检索和理解信息的人机交互行为变得方便简单。 作为人类认知能力的一种重要外部辅助工具，信息可视化主要服务于两个 相互关联但是完全不同的目的【5 j 。一个目的是为了交流想法。人们常说“一图 胜千言”，语言往往在思想交流时会造成各种歧义，而将想法描绘成图形更易于 为人所理解。如图1 2 、1 3 所示，同样在诠释i a v a 语言中c o l l e c t i o n sf r a m e w o r k 成员构成，图1 2 采用文字形式，冗多枯燥乏味，不利于人们记忆掌握；而图 1 3 采用的图形展示显而易见且清晰直观，它使得信息的表达丰富多彩，从视 觉、使用上提供了良好的用户体验，从情感上给用户带来了积极情感，促进人 们对于信息的接受和理解。信息可视化的另一个目的就是采用图形的手段去创 造或发现想法本身，即利用视知觉的特殊属性去解决逻辑问题。正所谓“用视 觉去思考 。因此，信息可视化不仅仅只是提供给人们一种浏览信息，交流想法 的有效方式，更重要的是让图形自身来发现问题、解决问题。信息可视化就是 为信息的处理提供了一种非常有效的解决方案。 2 纂器蕊麓瓣 一一一口 t ，e 图12j a v ac o l l e c t i o n sf r a m e w o r k 成员构成描述 一! 曼、熏哮t 夸、一霄垫掣 高昱髫l 鳖嚼 一璺-目 国粤 啬 勰 酬 一巨i 鞫l = = ， 图13j a v ac o l l e c t i o n sf r a m e w a r k 成员构成图示 12 问题的提出 国内绝大多数中小型线束生产企业已步入面向订单的多品种、小批量生产 模式，根据客户的订单进行生产，生产的品种具有不同的质量规格、交货期、 数量和价格等。该模式下线柬企业的产品种类多、批量小、生产重复度低、 工艺过程经常变更、生产计划的稳定性较差n 导致生产过程中作业轮换频繁， 生产调度任务量紧，由此更加重了生产过程中作业调度的负担。而生产调度作 为企业实现现代化生产管理的重要方法之一，是对企业生产全过程直接进行控 制和协调的一项具体工作，是组织完成生产作业计划的重要手段，是使生产系 统能够持续、协调、稳定、高效运行的重要保证 7 】。面对复杂的市场变化，生 产调度纯粹依赖有经验的调度人员己经成为企业提升竞争力的瓶颈之一。因为 在竞争激烈的经济全球化时代，一个企业对市场变化的反应速度是衡量一个企 业竞争力的重要标志之一。因此，线束行业如何在多品种小批量生产模式下对 各作业任务进行快捷有效的调度和控制已成为企业发展至关重要的问题。 其次，线束企业的生产调度中存在着有大量复杂的信息，包括生产状态信 息、工序约束信息、人员最备信息、订单任务信息、物料库存信息等。作为企 业的管理者，在进行生产调度决策时必须实时地对相关信息加以掌握和分析， 咀确保企业在进行产品调度时不至于顾此失彼。然而，随着企业的发展壮大， 客户订单的激增，生产调度过程所涉及的相关信息将呈指数级增长，面对浩如 烟海的信息，管理者如何从中去粗取精、把握其中关键，快速做出正确决镶， 就显得极为重要。信息可视化方法正是解决这个问题的一个行之有效的方法。 它利用可视化技术形象地表示各类生产信息，通过生动合适的组织方式使人们 能更直观快速地获取对已有用信息，有效增强人脑吸收和处理信息的能力，从 而提高企业管理和操作效率。在准确传递信息的同时信息可视化方法还提供各 种交互的功能，帮助人们完成过滤、控制、选择、变形等操作，引导用户发现 问题、总结规律，提高认知能力，实现用户的个性化需求。 1 3 国内外研究现状概述 1 3 1 生产调度方法研究现状 在过去的几十年中，人们对调度问题进行了大量的研究工作。从上个世纪 5 0 年代起，调度问题的研究就受到应用数学、运筹学、工程技术等领域科学家 的重视，科学家们利用运筹学中的线性规划、整数规划、目标规划、动态规划 及决策分析方法，研究并解决了一系列有代表意义的调度和优化问题。2 0 世纪 7 0 年代，经典调度理论取得了重要进展，但是实际调度问题与经典调度问题还 有相当的距离。其关键因素在于调度问题的n p 性质【7 1 ，实际调度问题往往都 是非常复杂的，没有确定的物理和自然规律可循，因此是非常难解的，并且大 多是没有精确解的。若仅仅依靠经典调度理论中基于解析优化的技术和方法， 试图解决属于n p 完全问题的实际调度问题，不可避免地会遇到难以逾越的障 碍。 因此，从2 0 世纪8 0 年代开始，调度研究由理论研究转向应用研究。在这 样的背景下，应用人工智能、计算智能和实时智能研究成果，解决实际问题的 智能方法就走上历史的舞台。 目前，尽管调度方法逐渐走向复杂化和多元化，但是它们基本上可以归结 为4 种类型：基于运筹学的方法、启发式调度方法、基于仿真的方法和基于人 工智能的方法一j 。 基于运筹学的方法。 基于运筹学的调度方法是针对传统的调度问题，主要有：线性规划、混合 整数线性规划、动态规划、拉氏松弛法、分枝定界法等【1 0 】【1 1 】【1 2 】【13 1 ，它们的共 同特点是寻求调度特例的多项式时间最优或近优算法，而且随着研究对象规模 的扩大以及约束条件的复杂化，计算时间将呈指数化增长，因此它们主要适合 于处理较小规模的调度问题。 启发式调度方法。 启发式调度方法因其计算复杂度低、易于实现等特性，能够用于动态实时 调度系统中，许多年来一直受到学者们的广泛关注，并不断涌现出许多新调度 规则。但启发式规则一般不具备全局优化的特点【1 4 】。常用的启发式规则可分为 简单规则、复合规则、启发式规则三类【1 5 j 【16 1 。 基于仿真的方法。 仿真调度方法是通过对仿真模型的运行来收集数据，并运用这些数据对实 际系统进行性能和状态方面的分析，从而对系统采用合适的控制调度方法【1 7 】。 纯仿真法虽然可以考虑解析模型无法描述的因素，并且可以给使用者提供一个 调度性能测试的机会，但应用仿真进行作业调度的费用高，仿真的准确性受程 序员判断能力和技能的限制，并且很难从特殊的试验中提炼出一般规律。 基于人工智能的方法。 4 人工智能应用于调度系统的标志是1 9 8 3 年c a r n e g i em e l l o n 大学的mf o x 在博士论文中开展基于约束传播的智能调度【1 8 】。人工智能调度方法是基于人工 智能技术和人类调度专家经验对调度问题进行建模并求解的方法总称，主要包 括以下几个分支： ( 1 ) 启发式搜索算法，该方法包括宽度优先搜索、深度优先搜索、b e a m 搜 索、a 或a 宰算法。 ( 2 ) 专家系统，它根据系统当前的状态和给定的优化目标，对知识库进行 有效的搜索并进行模糊推理，选择最优的调度策略，为在线调度提供智能支持。 调度专家系统可以产生复杂的启发式规则，利用定性和定量知识，具有智能性。 但是开发周期长、费用昂贵且所需的经验和知识难以获取【1 9 】【2 0 1 。 ( 3 ) 基于a g e n t 的调度方法，该方法是针对日益广泛的分布式调度而兴起 的一种新型有效调度技术，吸引了众多学者的目光。尤其是m a s 技术增强了 调度理论在实际应用中的灵活性，其不足之处就是在理论上有待进一步完善， 标准化工作不够，导致重复劳动【1 8 1 1 2 1 】【2 2 1 。 ( 4 ) 基于神经网络的方法，它是在对人脑组织结构和运行机制认识理解的 基础上模拟其结构和智能行为的一种工程系统。人工神经网络具有自学习能 力，且易于分类。但在实际生产中的应用不是很多，而且存在学习效率比较差、 难以表达符号知识以及其他知识、计算速度比较慢等缺点，这些都需要进一步 改进【2 3 】。 ( 5 ) 基于模糊数学的方法，它的核心思想是运用数学手段，仿效人脑思维， 对复杂事物进行模糊处理【2 4 1 。模糊系统的显著特点是能够直接地表示逻辑，适 于高级知识表达，具有较强的逻辑功能。但它没有本质的获取知识的能力，模 糊规则的确定也比较困难，通常需要领域专家知识的指导，因此如何实现模 糊规则的自动提取和模糊变量隶属度函数的自动生成及优化，一直是一个难题。 ( 6 ) 禁忌搜索算法，它通过引入一个灵活的存储结构和相应的禁忌准则来 避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样 化搜索以便实现全局优化。然而禁忌搜索算法的搜索性能完全依赖于邻域结构 和初始解。 ( 7 ) 模拟退火算法，它是根据液态和固态材料中粒子的统计力学规律与复 杂组合优化问题求解过程的相似之处而提出来的，被赞誉为解决许多高难度调 度和组合优化问题的“救星 i 2 引。模拟退火算法显示出了求解优化问题的强大 威力，它可以突破局域搜索的限制，转移到代价较高的解答，而且如果选择参 数得当，会在很快的时间内收敛。但是，模拟退火算法在实际应用中往往不能 产生较优的结果，而且各个参数选择起来比较困难，如果选择不得当，就会使 得计算时间很长，而且可能得不到好的结果。模拟退火算法和其他算法结合使 用会得到很好的效果，如和遗传算法、人工神经网络结合等。 ( 8 ) 遗传算法，它是h o l l a n d 教授基于自然遗传进化模型提出的并行优化搜 索方法，它的最大优点是利用群体间的相互作用，保持已经搜索到的信息；搜 索过程具有并行性，非常适合于大规模并行分布处理；且优化不受限制性条件 的约束。遗传算法已成为近年来解决作业调度问题的最主要方法。但是遗传算 法也有其明显的不足之处：对初始种群很敏感，初始种群选择不好会影响解的 质量和算法效率；搜索过程会出现早熟收敛的情况。为了进一步改进遗传算法， 人们主要从两方面入手：一是对遗传算法本身进行改进；二是与其他算法结合， 取长补短。 ( 9 ) q 学习方法，是一类通过引入期望的延时回报，求解无完全信息的 m d p ( m a r k o vd e c i s i o np r o c e s s ，m d p ) 类问题的方法，即基于时差策略的强化学 习方法【2 6 1 。q 学习可以看作一种增量式动态规划，它通过直接优化一个可迭代 计算的动作值函数qd ，圳来找到一个策略使得期望折扣报酬总和最大。这样， a g e n t 在每一次的迭代中都需要考察每一个行为，可确保学习过程收敛。q 学 习在计算规模较小时有出入意料的表现，但当状态空间增大到一定程度，更新 效率明显减慢，学习效率不高。 综上所述，调度方法的研究并没有一套统一既定的方法和理论。相对而言， 智能化调度方法成为目前解决生产调度方法的趋势。但理论研究与实际应用之 间还存在着很大差距。实际应用中的一些调度方法能够响应系统的动态变化， 但不能保证得到好的调度；一些理论上的最优化方法能提供最优调度，但由于 计算复杂性，并且忽略了很多实际因素，离实际运用还有较大距离。因此，生 产调度方法的研究还有待人们进一步的探索。 1 3 2 线束行业生产调度系统 很多大型线束企业在全球生产制造集成化和信息化潮流的带领下，采用先 进的生产经营管理模式和信息系统，利用高速发达的信息技术协调各部门的业 务活动，提高企业经营效率和市场占有率。大量中小型线束企业，随着业务规 模的快速增长和海外订单的逐渐增多，也开始规划和实施先进的生产与管理信 息系统，并呈现出越来越多的需求【27 1 。 为减少浪费，大量中小型线束企业积极引入先进的精益生产管理模式，通 过包括“看板 在内的一系列手段管理和组织生产，有效控制整个制造过程中 在制品和原材料的库存量，但企业对市场的反复变化并不能做出快速而有效的 回应。为提高企业的业务效率和信息透明度，获得与国际客户合作的机会，他 们也开始实施e r p 系统。国内著名的用友、金蝶e r p 软件在业界获得了良好 的反映。但e r p 系统重在企业业务流程的管理控制，对于生产现场数据的采集、 管理、控制则无能为力，常出现所谓的生产现场“黑箱操作”。 m e s 系统则在车间作业的现场控制方面具有显著优势。国外有h o n e y w e l l 、 a s p e nt e c h 等多家从事m e s 软件开发与推广的公司。国内如北京和利时公司、 6 东北大学自动化研究中心，浙江大学工业控制技术实验室以及华东理工大学都 在m e s 的研究与开发取得了一定成果，并且成功应用于钢铁企业、石化企业 和选矿企业等生产实际。但鉴于线柬生产的特点，m e s 系统很难满足线束企业 需求。( 1 ) 现有的m e s 系统要求在每个工作岗位设立条形码扫描设备。在单人 单岗的劳动密集型企业中，工作岗位数量巨大，实施m e s 系统成本昂贵。( 2 ) 大量不确定的调度信息又使m e s 系统实施困难，如材料不良、设备损坏、紧急 订单等，导致m e s 缺乏足够的敏捷性与智能性。( 3 ) m e s 操作复杂，对于单人 单岗劳动密集型的线束企业，操作工人的文化水平不高，系统培训困难，不利 于系统的推广。( 4 ) m e s 与e r p 系统常由不同公司开发，两个系统的整合难度 大，使用效果很难达到预期。 目前，大部分线束企业主要依靠经验丰富的调度员手工安排调度计划。对 于调度问题比较简单的情况下这种办法还是可行的，然而，在调度任务规模较 大且动态多变的环境中，单纯的手工调度就显得低效甚至无能为力了，况且， 对于企业来说，经验丰富的调度员本身就是一种稀缺资源。显然，充分利用目 前已取得的理论研究成果，设计一个运行高效、使用简单的车间调度系统，帮 助企业提高排产效率，对于线束行业有着重要的现实意义。 1 - 3 3 生产调度信息可视化 现今国内外已有大量的生产调度系统应用于实际生产，并取得了显著效益。 法国i l o g 公司是世界上提供企业优化和可视化软件的主要供应商，其产品 i l o gc p l e x 、i l o gs o l v e r 、i l o gs c h e d u l e r 等都是一些用来求解车间作业调 度的优秀软件。s a p 公司的r 3 管理信息系统中生产计划模块使用的就是i l o g 公司开发的优化调度工具。类似的还有b m c 公司的业务集成调度解决方案 c o n t r o l m c ，a r i m a 公司的s y n c r u n 调度软件等。 国内从2 0 世纪8 0 年代开始，也出现了一些相对成型、成熟和有规模、有 影响的国产生产调度可视化系统。例如中国铝业总公司生产调度系统，实现了 总部对分布于全国不同地区的各分公司生产过程的统一管理；通过数据报表、 图形报表、专题图、趋势图等多种形式进行统计和分析，达到辅助决策的功能。 2 0 0 8 年投入运行的宝钢分公司冷轧薄板厂生产调度监控系统，实现了工作人员 在大屏幕前指挥生产的突破技术。但有关线束行业的生产调度可视化软件还未 见到。 在生产调度产品走向市场的同时，我们也注意到目前的调度系统多集中在 冶金、化工等实力相当的行业，生产调度电视监控系统虽然满足了生产信息反 馈准确、实时的优点，但它最显著的特点也是其不足之处在于资金投资大，科 技含量高，实施改造工程量大，非一般中小型企业所能承受的。而在展现相关 调度信息方面，报表的形式出现居多，相对单一且不易于比较，而趋势图、比 例图等则有较好的展示效果。文献【2 8 】 2 9 】采用了甘特图表示车间各作业生产进 7 度，使得生产安排情况一目了然，提高了信息获取效率，适宜线束行业的使用。 1 4 生产调度信息可视化研究框架 l _ 4l企业及业务流程简介 台肥得润电子器件有限公司( 以下简称舍肥得润公司) 是深圳市得润电子 股份有限公司和香港得润投资发展有限公司共同投资组建的合资公司。该公司 成立于2 0 0 1 年1 1 月，注册资金2 5 0 0 万元，目前年产值近2 亿元，主营各类电 子连接器产品，包括家电连接器线束总成、精密电子接插件、精密模具及精密 组件等，是合肥海尔、美菱集团、美的、荣事达、江淮等知名企业的a 级供应 商。在连接器领域中有着极为宽广的市场与良好的销售前景。 本课题以台肥得润公司的家电线束生产车间为对象对车间生产作业计划 和调度状况进行了研究，在充分考虑家电线束的加工特点和工艺特征的基础上， 采用分级调度策略，并通过相关信息可视化显示，辅助管理者对生产过程进行 控制和调整，实现有效的生产作业调度，从而提高企业的生产效率。 图14 给出了合肥得润公司的基本业务流程图。该公司是典型的面向订单 式多品种小批量企业，当其接受客户订单后，经过一系列的评审( 包括工艺、 物料、产能等方面的评审) ，审核通过，则进行生产排程，最终交付客户。本文 所研究的生产调度信息可视化系统即位于图中虚线框标识的部分。 暑0 圃惠盛 一一。 参伍 圃童争怔杰尊 图l4 台肥得润业务流程图 142生产调度信息可视化系统 生产排程，也即车间生产的作业调度，是企业提高运行管理质量中最具伸 缩性的因素之一p 。一个符合实际高效的生产调度策略将解决企业发展的瓶 颈，为企业的快速发展提供良好保障。同时，对降低生产成本、缩短制造周期、 提高生产效益均具有重要的意义。在合肥得润这类多品种小批量生产的制造车 间中，管理上层按照订单加工任务制定生产作业策略，把生产任务具体地、合 理地分配到生产的各个环节和各个生产单元包括车间、工作中心、加工设备以 至操作者上，以组织和协调它们之间的生产活动，使各有关单元有机地配合起 来，均衡生产，力求保证按期、按质、按量完成生产任务。更直接地说，作业 调度需要确定所有工件在加工设备上的加工顺序，阻及加工设备加工每道工序 的开始时间和完成时削，最大限度地保证每个工件的交货期。但由于实际情况 的复杂多变，使得己经生成的车间作业计划不一定完全适合实际生产状况，因 此需要根据实际情况，对车间作业计划进行及时修改和调整，这就需要及时准 确的信息反馈，以及便于人员操作的可视化界面。 如图15 所示，生产调度信息可视化系统在新的任务信息加入后立即结合 剩余未生产任务信息和当前生产状态进行调度策略的计算，生成新的调度结果， 并将其以合适的可视化形式展现出来，方便工作人员的查看与调整。若调度结 果不能满足需求，譬如交货逾期、机器负载不平衡等，工作人员可予以手工调 整，或加班赶工，或变换机器工作时间等。反之，则安排生产。 。i ? 笙二蟊 气i ，辅， 1 5 课题来源与论文内容安排 1 5 1 课题来源 论文主要得到了国家自然科学基金项目“科学计算中面向建模的多态机理 研究”( 6 0 6 7 3 0 2 8 ) 、“安徽省高等学校优秀青年人才基金 ( 2 0 1 0 s q r l 0 1 3 z d ) 和合肥市科技局项目“基于信号量机制的生产调度及其可视化”项目的共同资 助。 1 5 2 内容安排 论文的主要内容安排如下： 第一章绪论部分介绍了当今线束行业的发展概况与信息可视化技术的现 状，在基于目前企业多品种小批量模式下，生产调度所存在的问题，提出信息 可视化需求。针对生产调度方法、线束行业的生产调度系统及其中信息可视化 的应用进行了国内外研究概述，最后阐明了本课题的研究框架。 第二章介绍了研究中使用的分级调度算法。根据得润车间作业排产实际情 况，建立分级调度模型：对于粗粒度的前工序、后工序，采用q 学习算法计算 最迟交期：对于前、后工序内部的工序调度只考虑由上层调度得出的当日须安 排的作业，采用模拟退火遗传算法按交期优化排序。最后通过得润车间某日某 组的实际生产任务排程验证了算法的有效性。 第三章结合车间生产调度的特点以及作业调度结果，有侧重地介绍了几种 信息可视化方法。星状图以其兼具树状结构和网状结构的优势，用来综合展现 生产调度中错综复杂的各类信息，本文从可视化元素配置、布局策略以及交互 方式三个方面予以详细阐述；甘特图作为经典作业排序工具，依然必不可少， 用以展现车间各作业任务调度结果，不仅成为实际生产排产的依据，也是上层 管理者了解车间具体生产状态的直接窗i z l ；统计图用来展现已有信息、数据间 的关系，其中条形图、折线图、扇形图等表现侧重点各不相同。 第四章是生产调度实例的介绍。以合肥得润家电线束车间的实际生产情况 为例，通过基于q 学习和模拟退火遗传算法相结合的分级调度方法进行生产排 产，并以多种方式从不同角度对生产调度信息进行可视化显示，实现生产向上 透明化。诸如甘特图，直观显示各作业调度结果；星状图，反映相关生产资源 调度情况，以及辅助用户手工干预调度结果；工作现场仿真；各种数据统计图。 第五章为论文工作的总结与展望，在总结论文工作的同时对后续工作进行 展望。 l o 第二章基于q 学习和遗传算法的分级作业调度 车间生产过程的调度问题，是整个先进生产制造系统实现管理技术