（系统理论专业论文）基于微粒群算法的车间调度问题研究.pdf

摘要 随着社会经济的飞速发展，市场竞争日趋激烈，顾客需求的多样化、个性化增 加了企业生产计划运行的不确定性和动态性因素，使得现代企业面临着严峻的挑战， 对供应链的管理也提出了更高的要求。进入2 0 世纪9 0 年代以来，供应链管理成为 当今国际上企业管理理论研究和实践应用的一个热点。在此环境下，为了提高盈利 水平和核心竞争力，企业开始注重合理配置和高效利用自己的内外资源。基于供应 链的调度模型将供应链管理和生产调度问题紧密结合起来，研究在供应链管理的环 境下如何更有效地解决分布环境下车间生产调度与协调问题，最终实现节点企业供 应链管理与车间调度的双重优化，从而具有一定的理论价值和实际意义。 微粒群优化算法是一种新型的群体智能算法，源于对鸟群捕食行为的研究，是 一种基于迭代的优化技术。系统初始化为一组随机解，通过迭代搜寻最优值。目前， 微粒群算法已广泛应用于函数优化、神经网络训练、数据挖掘及其它应用领域。 本文围绕着微粒群算法及其应用，就如何改进传统微粒群算法性能及该算法在 车间调度、供应链调度领域的应用展开了深入研究。首先介绍了本文的研究背景及 目的意义，给出了车间调度问题的分类、特点以及近年来研究车间调度问题的主要 方法。其次介绍了遗传算法及其在车间调度问题中的应用，并引入正交试验来确定 算子，提出了基于正交试验的免疫遗传算法并用该算法求解作业车间( j o b s h o p ) 调度 问题，通过比较得到了令人满意的仿真结果。然后对微粒群优化算法的现状及未来 研究方向进行了描述，给出了微粒群算法在车间调度问题中的应用，使用了基于粒 子坐标值排列编码，通过与遗传算法比较，仿真实验表明了微粒群算法在求解作业 车间调度问题的优越性和有效性。接下来介绍了供应链和供应链管理的概念及特征， 给出了在供应链环境下生产系统的协调控制及车间调度问题。文章最后描述了无等 待供应链在线调度问题，提出了基于最小位置值排列编码方法，在不改变已有工件 调度的情况下，对顾客下达的紧急订单尽早制定生产方案。在流水车间( f l o w - s h o p ) 及作业车间调度问题背景下，给出了求解在资源可用时间区间上在线调度紧急订单 的算法，使用该算法可以迅速求出订单完工时间并通过电话或互联网将交货期反馈 给顾客，对制造商的实际生产供应链管理具有一定的指导意义。 关键词：微粒群优化；供应链；调度；实时 a b s t r a c t w i t ht h ef a s td e v e l o p m e n to fs o c i a le c o n o m y , c o m p e t i t i o ni nt h em a r k e tb e c o m e s i n c r e a s i n g l yi n t e n s e t h ed i v e r s i f i c a t i o na n dc u s t o m i z a t i o no ft h e c u s t o m e r s n e e d i n c r e a s et h eu n c e r t a i n t ya n dd y n a m i s mi nt h ep r o d u c t i o np l a no ft h ee n t e r p r i s e ，m a k i n g t h em o d e me n t e r p r i s ef a c es e v e r ec h a l l e n g e sa n dm a k i n gg r e a t e rd e m a n d so ft h es u p p l y c h a i nm a n a g e m e n t a f t e re n t e r i n gt h e19 9 0 s ，t h es u p p l yc h a i nm a n a g e m e n ta l r e a d y b e c o m e so n eo ft h ef o c u s e si nt h es t u d ya n dp r a c t i c eo ft h ee n t e r p r i s em a n a g e m e n tt h e o r y a n dp r a c t i c ei nt h ei n t e r n a t i o n a ls o c i e t y i nt h ec i r c u m s t a n c e s ，i no r d e rt oi m p r o v et h e p r o f i tl e v e la n dt h ec o r ec o m p e t i t i v ea b i l i t y , t h ee n t e r p r i s eb e g i n st of o c u so nr a t i o n a l l y a l l o c a t i n ga n de f f i c i e n t l yu t i l i z i n gi t si n n e ra n do u t e rr e s o u r c e s t h es c h e d u l i n gm o d e l s t u d yb a s e do nt h es u p p l yc h a i nc o m b i n e st h ep r o b l e mo ft h es u p p l yc h a i nm a n a g e m e n t a n dt h ep r o b l e mo ft h ep r o d u c t i o ns c h e d u l i n gt os t u d yh o wt om o r ee f f e c t i v e l ys o l v et h e j o b s h o ps c h e d u l i n ga n d c o o r d i n a t i o np r o b l e mi nt h ed i s t r i b u t e de n v i r o n m e n t ，a n d u l t i m a t e l y r e a l i z et h ed o u b l eo p t i m i z a t i o no ft h en o d e e n t e r p r i s e ss u p p l y c h a i n m a n a g e m e n ta n dt h ej o b - s h o ps c h e d u l i n g ，b o a s t i n g c e r t a i nt h e o r e t i c a la n dp r a c t i c a l s i g n i f i c a n c e p a r t i c l es w a r mo p t i m i z a t i o n , an e ws w a r mi n t e l l i g e n c ea l g o r i t h m ，o r i g i n a t e sf r o m t h ei n v e s t i g a t i o no ft h eb i r ds w a r mp r e y i n gb e h a v i o r i ti sa no p t i m i z a t i o nt e c h n o l o g y b a s e do ni t e r a t i o n s y s t e mi si n i t i a l i z e di n t oag r o u po fr a n d o ms o l u t i o n sa n do p t i m i z a t i o n v a l u ei ss e a r c h e db yi t e r a t i o n n o w , p a r t i c l es w a r mo p t i m i z a t i o ni sa p p l i e di n t of u n c t i o n o p t i m i z a t i o n ，n e u r a ln e t w o r kt r a i n i n g ，d a t am i n i n ga n d o t h e ra p p l i c a t i o nf i e l d t h ep a p e rf o c u s e so nt h ea l g o r i t h ma n da p p l i c a t i o no ft h ep a r t i c l es w a r ma n dm a k e s d e e ps t u d yo ni m p r o v i n gt h ep r o p e r t yo ft h et r a d i t i o n a lp a r t i c l es w a r l na l g o r i t h ma n do i l t h ea p p l i c a t i o no ft h ea l g o r i t h mi nt h ef i e l d so ft h ej o bs h o ps c h e d u l i n ga n dt h es u p p l y c h a i ns c h e d u l i n g t h eb a c k g r o u n d ，a i ma n ds i g n i f i c a n c eo ft h ep a p e ra r ei n t r o d u c e df i r s t ， f o l l o w e db yt h ec l a s s i f i c a t i o na n dc h a r a c t e r i s t i c so f t h ej o bs h o ps c h e d u l i n g ，a sw e l la st h e m a j o rw a y so fs t u d y i n gt h ej o bs h o ps c h e d u l i n gp r o b l e m t h e n , t h ep a p e rd e s c r i b e st h e g e n e t i ca l g o r i t h m sa p p l i c a t i o n i nt h ej o bs h o ps c h e d u l i n gp r o b l e m t h eo r t h o g o n a l e x p e r i m e n ti si n t r o d u c e dt oi d e n t i f yt h eo p e r a t o r s ，a n dt h ei m m u n eg e n e t i ca l g o r i t h mi s p u tf o r w a r do nt h eb a s i so ft h eo r t h o g o n a le x p e r i m e n tt os o l v et h ej o bs h o ps c h e d u l i n g p r o b l e mw i t ht h ea l g o r i t h m ，a c h i e v i n gas a t i s f a c t o r ys i m u l a t i o nr e s u l tb yc o m p a r i s o n a f t e ri t ，t h ep a p e rd e s c r i b e st h ep r e s e n ts t a t u sa n dt h ef u t u r et r e n df o rs t u d yo ft h ep a r t i c l e s w a f l 1o p t i m i z a t i o na l g o r i t h m t h ea p p l i c a t i o no ft h ep a r t i c l es w a l ma l g o r i t h mi sg i v e n , u s i n gt h ec o d i n gm e t h o db a s e do np a r t i c l ep o s i t i o n t h r o u g ht h ec o m p a r i s o n 、析t 1 1t h e g e n e t i ca l g o r i t h m ，t h es i m u l a t i o nr e s u l t ss h o wt h es u p e r i o r i t ya n de f f e c t i v e n e s so ft h e p a r t i c l es w a r ma l g o r i t h mi ns o l v i n gt h ej o bs h o ps c h e d u l i n gp r o b l e m ，f o l l o w e db yt h e i n t r o d u c t i o no ft h ed e f i n i t i o na n dc h a r a c t e r i s t i c so ft h es u p p l yc h a i na n dt h es u p p l yc h a i n m a n a g e m e n t c o o r d i n a t e dc o n t r o la n ds h o ps c h e d u l i n gp r o b l e mi ns u p p l yc h a i na l eg i v e n a tl a s t ，t h eo n - l i n en o - w a i ts c h e d u l i n gi nt h es u p p l yc h a i ni ss t u d i e d t h ec o d i n gm e t h o d o ft h es m a l l e s tp o s i t i o nv a l u ei su s e di nt h i st h e s i s t h ep r o d u c t i o np l a nw i l lb em a d et o t h ec u s t o m e r su r g e n to r d e rw i t h o u tc h a n g i n gt h es c h e d u l e dj o b s p r o c e s s i n go r d e r s i n t h eb a c k g r o u n do ff l o ws h o pa n dj o bs h o ps c h e d u l i n g ，t h ep a p e rg i v e st h ea l g o r i t h mt o o n l i n es c h e d u l et h eu r g e n to r d e ri nac e r t a i nt i m ei n t e r v a lw h e nr e s o u r c e sa l ea v a i l a b l e m a k i n gu s eo f t h i sa l g o r i t h mw i l lo b t a i nt h ec o m p l e t i o nt i m eo ft h eo r d e ri nn ot i m e ，a n d p r o p o s ead e l i v e r yt i m eo nt h ep h o n eo ro nt h ei n t e m e t i ti s o fc e r t a i ng u i d i n g s i g n i f i c a n c et ot h em a n u f a c t u r e r sp r a c t i c a lp r o d u c t i o ns u p p l yc h a i nm a n a g e m e n t k e yw o r d s ：p a r t i c l es w a r m - e p t i m i z a t i o n ；s u p p l yc h a i n ；s c h e d u l i n g ；r e a l - t i m e 青岛大学博+ 学位论文 学位论文独创性声明、学位论文知识产权权属声明 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人的成果，均己做出明确标注或得到许可。论文内容未包含法律意义上 已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成 果。 本人如违反上述声明，愿意承担由此引发的一切责任和后果。 论文作者签名：、申1 # 缸琦 日期：p 彤年月 日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校 后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为 青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密故 ( 请在以上方框内打“4 ”) 日期：钞昭年月7 日 会确肋 彬溆翱亏 名z 彳 躲琵 者卒 怍 文弓披弓 青岛大学博士学位论文 1 1 问题的提出 1 1 1 研究背景 第一章绪论 进入九十年代以来，随着信息技术的发展，全球性生产能力过剩和“产品形成 的决定权转移给消费者趋势的发展，极大地削弱了传统大规模生产的竞争优势， 这也预示着消费者需求多样化时期的到来。企业迫切需要新的经营管理模式，供应 链管理( s u p p l yc h a i nm a n a g e m e n t ，s c m ) 应运而生。 随着世界经济一体化进程的加剧，企业之间的合作、竞争关系不断加深，打破 了传统的单一化供应链模式，使之向网络化、结构化、集成化方向发展，从而大大 提升了生产能力、生产效率和服务水平。 供应链结构的复杂性决定了其管理运作的复杂性，由于现实中供应链各协作成 员之间具有相对独立的经济利益和复杂的协作与竞争关系，因而资源在各成员之间 的合理分配至关重要，这是供应链调度( s u p p l yc h a i ns c h e d u l i n g ，s o s ) 过程所应解 决的关键问题之一瞄1 。车间生产过程的调度问题，是制造系统管理技术、运筹技术 和优化技术发展的核心。有效的调度方法已成为先进制造技术实践的关键和基础， 同时也是提高企业快速响应市场变化能力的关键。在企业开展供应链管理的同时， 应当对于企业内部生产制造过程层次中的物流、信息流和资金流，结合企业所处的 外部供应链环境，即供应链管理层次的物流、信息流和资金流，进行有机的集成， 使车间生产调度信息和外部供应采购信息沟通与互动，最终达到供应链管理和车间 生产调度的双重优化。 供应链调度问题是供应链管理的核心问题之一，供应链调度过程是一个典型的 随机、动态过程，其动态性的突出表现是由客户订单的不确定性而引起的需求随机 性。现代信息技术的发展使得客户可以通过网络或电话直接与制造商或供应商对话， 要求整个供应链对客户的需求作出个性化、快速准确的响应。在理论界，抛开供应 链这一前提，对于经典的车间调度问题，国内外已有很多学者进行了深入探索，但 对于供应链调度的相关问题目前研究甚少，因而，深入研究供应链调度问题具有重 要意义，本文就是以此作为选题和研究的切入点，研究了微粒群算法在车间调度及 供应链调度问题中的应用。 第一章绪论 1 1 2 本文的研究目的和意义 经济全球化给企业带来了新的挑战和机遇。企业要想在激烈的竞争中生存下去， 必须以最快的速度、最好的质量、最低的成本及最优的服务来响应市场。生产调度 是影响企业生产能力发挥的重要因素，所以如何组织协调生产、调配资源，对企业 建立现代化企业制度，提高客户的个性化定制服务水平，提高竞争力具有至关重要 的作用。生产调度的核心问题是模型和算法，其中有效的调度算法是生产调度领域 的重要研究内容。微粒群算法是一种基于群智能的进化类算法，也是一种模拟鸟群 觅食的仿生算法，具有显式的计算模型，操作和实施简单。本文围绕微粒群优化算 法在车间调度和供应链环境下的调度展开研究。论文的研究意义在理论上是对微粒 群优化算法和供应链调度问题的一种探索，实践上，则是为了提高供应链调度水平， 以增强企业的核心竞争力。 1 2 生产调度问题概述 随着人类社会生产力水平的不断提高，人类的生产等社会活动对资源的需求量 急剧上升，资源的有限性逐渐摆在了人们面前，如何合理配置、优化资源已成为必 须要解决的问题，同时也是一项具有挑战性的难题口1 。该问题贯穿于社会生活的每 个角落，从一个国家的宏观经济活动到企业的微观经济活动，无不受到资源条件的 制约。所以，人们开始从不同的领域，不同的行业开展对它的研究。其中，在制造 业的生产领域产生了一个非常重要的理论一生产调度理论。 生产调度就是在一定的时间内，进行可用共享资源的分配和加工任务的排序， 以满足某个或某些特定的生产指标。共享的生产资源包括：原料、人力、资源、加 工设备、存贮设备等。加工任务是在指定时间内生产特定的产品，这些产品可以是 用户定购的产品，也可以是根据市场需求计划生产的产品。生产指标制定的目的是 为了尽可能获得最大的经济效益和较好的社会效益。所以生产指标一般定为成本最 低、库存费用最少、生产周期最短、生产切换最少、设备利用率最高等。 生产调度作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹技 术、优化技术、自动化与计算机技术发展的核心。有效的调度方法和优化技术的研 究与应用，是实现先进制造和提高生产效率的基础和关键。改善生产调度方案，可 大大提高生产效益和资源利用率，进而增强企业的竞争能力。 生产调度理论从诞生至今，经过几十年的研究和探索，已逐渐发展成为一个比 较完整的科学理论，在企业的生产中得到了广泛应用，而且其研究成果的应用也已 2 青岛大学博士学位论文 经从制造业的车间扩展到了物资、能源、交通运输和社会服务等诸多行业。生产调 度理论是目前国际上发展最迅速、研究最活跃、成果最丰硕、前景最诱人的学科领 域之一钔。 生产调度最热门的话题是车间调度( j o b s h o ps c h e d u l i n g ) 、存贮控制( i n v e n t o r y c o n t r 0 1 ) 、间歇生产调度( b a t c hs c h e d u l i n g ) 和动态调度( d y n a m i cs c h e d u l i n g ) 隅1 等。 车间调度问题概述 车间调度问题是调度问题的一个子集，实际上是一个资源分配问题，这里的资 源分配主要指设备资源。问题的求解目标主要是找到一个将一组任务安排到设备上 去，以使作业可被“最优完成的方案。车间调度问题是n p 问题，也是最困难的 组合优化问题之一。 早在1 9 5 4 年，j o h n s o n 研究了两台机器有序加工型的调度问题，提出了一种以 工件加工完成时间极小为目标函数的最优排序分析解法，从此开始了对调度问题的 研究呻1 。由于调度问题的复杂性，不同的研究者从不同的角度研究某一方面问题， 对具体问题的提法也不全相同。典型调度问题的提法是：有m 台不同的机器，每台 机器可加工工件的若干工序，并在不同机器上这些工序可以不同。有胆个不向类别 的工件需要加工，每个工件又有若干工序，要求将工件合理地分配到各机器，并合 理安排工件的加工次序和时间，使约束条件被满足，同时使一些性能指标得到优化。 在工件调度中要考虑的要素很多，如工件的安装时间、加工时间、等待时间、”搬运 时间等。总的说来，调度问题可表述为在等式或不等式约束下，求目标函数的优化 【5 】 o 1 3 1 车间调度问题的分类 考虑以个工件在m 台机器上加工的问题。假设每个工件不能同时在两台以上的 机器上加工，每台机器也不能同时加工两个以上的工件。每个工序加工时间预先给 定。一般的，根据研究对象的复杂性，刀xm 作业车间调度问题可分为以下几类： ( 1 ) 单机调度问题 加工系统只有一台机器，待加工的工件也只有一道工序，所有工件都在该机器 上加工。 ( 2 ) 并行机调度问题 加工系统具有一组功能相同的机器，待加工的工件都只有一道工序，可任选一 台机器来加工工件。 3 第一章绪论 ( 3 ) 流水车间调度问题 加工系统有一组功能不同的机床，待加工的工件包含多道工序， 台机器上加工，所有工件的加工路线都相同。 ( 4 ) 作业车间调度问题 加工系统有一组功能不同的机床，待加工的工件包含多道工序， 台机器上加工，零件的加工路线互不相同。 每道工序在一 每道工序在一 单机调度问题是最简单的调度问题，当生产车间出现瓶颈机器时的调度就可视 为单机调度。作业调度问题是最复杂的调度问题，生产车间的大多数是作业调度。 1 3 2 车间调度问题的特点 ( 1 ) 离散性 车间生产系统是个典型的离散系统，其中工件的加工发生在不同的时间和资源 上，并且任务的到达、订单的更改、设备的增添等等都是离散事件。解决该问题的 方法通常是使用数学规划、离散系统建模与仿真等方式，通过排序理论进行车间调 度研究。 ( 2 ) 动态随机性 车间调度中有很多随机和不确定的因素。如工件到达时间的不确定，实际工件 加工时间的不确定等。系统中也经常会有突发事件发生，如机器损坏、紧急工件加 工等。 ( 3 ) 多目标性 车间生产中，不同的加工任务对应着不同的调度目标。a l is k i r a n 等人将目标 分为三类盯1 ：基于工件加工完成时间的目标，基于工件到期时间的目标和基于生产 成本的目标，文中他们列举了几十种目标。这些目标之间往往是有冲突的。如何使 车间调度系统适应不同的任务类型和规模，一直是车间调度中面临的难题。 ( 4 ) 计算复杂性 车间中的工件、机床、操作人员、物料传送系统和缓冲区之间相互影响，相互 制约。如一个工件的加工除了要考虑它的加工时间、安装时间及操作顺序外，还要 考虑操作人员熟练程度、刀具数量、系统缓冲能力和各种动态事件的影响。在这些 条件的综合影响下，车间调度问题实质上是一个在若干等式和不等式约束下的组合 优化问题，从计算时间复杂度看是一个n p 难问题，随着问题规模的增大，计算量 急剧增加，因而求解非常困难。 ( 5 ) 多约束性 4 青岛大学博士学位论文 资源的数量、缓存的容量、工件到期时间以及工件的操作顺序等都是约束，另 外还有一些人为方面的约束，如操作人员熟练程度、机器上负荷要平衡等。 1 3 3 车间调度问题的研究方法 自从调度问题被提出以来，引起了无数研究者的浓厚兴趣，经过5 0 多年的发展， 出现了大量的研究成果，相继提出了很多重要的调度方法，总结如下： ( 1 ) 基于运筹学的方法呻1 运筹学方法大多针对传统的调度问题，即研究如何在朋台机器上安排刀个任务 的加工顺序和开工时间，以便使得某个性能指标最优。典型的目标函数有加工时间 跨度( m a k e s p a n ) 极小化，提前拖期( e f t ) 惩罚极小化等。 ( 2 ) 基于启发式规则的方法 启发式算法因其简单实用、计算复杂度低等原因，在实际中得到了比较广泛的 应用，并且不断涌现出许多新的调度规则。常用的启发式规则可分为简单规则一复 合规则、启发式规则三类阳1 。但启发式规则一般不具备全局优化的特点。 _f ( 3 ) 分枝定界法 分枝定界法可为部分路径计算很强的下界，所以它是求解调度问题比较有效的 方法。但对于较大规模的调度问题，分枝定界法需要较多的时间n 们。 ( 4 ) 拉格朗日松弛算法 。焱j 、 拉格朗日松弛算法由于其在可行的时间里能对复杂的规划问题提供较好的次优 解，并能对解的次优性进行定量评估，近年来已成为解决复杂生产调度问题的一种 重要方法1 。与分枝定界法相比，该算法更耗时。 ( 5 ) 控制理论方法 g e r s h w i n n 2 3 等人从控制理论的角度出发，较全面地阐述了控制理论方法在制造 系统中的应用情况，该方法比较适合定量地定义基本问题。其缺点是：模型描述能 力有限，建模时不得不对真实环境进行大量简化，求得最优解的时间随着问题规模 增大而呈指数规律增长，因此也只适合求解小规模问题。 ( 6 ) 动态规划 动态规划是求解小规模调度问题的有效算法，不适合求解大规模调度问题，计 算复杂性会随问题规模的扩大呈指数增长n 帕。 ( 7 ) 专家系统和基于知识的方法n 3 j 钔 专家系统和基于知识的方法由知识库和推理机组成。知识库包括一些规则、过 程和启发式信息。推理机制用来选择一种策略处理知识库中的知识。将该方法用于 5 第一章绪论 调度问题，可以根据系统当前的状态和给定的优化目标，对知识库进行有效的启发 式搜索和并行模糊推理机制，避开繁琐的计算，并选择最优的调度策略，为在线决 策提供支持。 ( 8 ) 仿真调度方法u 副 由于生产系统的复杂性，以致于很难用精确的解析模型对其进行描述分析。但 是仿真却能提供这种理想模型，且可以定量地进行评估，从而对实际系统采用合适 的调度方法。但应用仿真进行生产调度的费用高，仿真的准确性受程序员判断能力 和技能的限制，并且很难从特殊的试验中提炼出一般规律。 ( 9 ) 神经网络优化法 采用神经网络方法，一方面可以利用其并行处理能力降低调度计算问题的复杂 性；另一方面，利用其自学习和适应能力用于调度知识的获取，以构造调度决策模 型。但由于涉及的变量太多，计算效率低，很难解决实际调度问题n 引。 ( 1 0 ) 基于模糊数学理论的方法 客观现象具有确定性与不确定性两个基本方面，经典数学表达的是现象的确定 性；不确定性一方面表现为随机性，另一方面表现为模糊性。正是利用此特点，许 多学者把它引入了调度领域。但与专家系统相似，这种方法同样存在开发周期长、 需要丰富的调度经验和知识等缺点n 引。 ( 1 1 ) 具有计算智能的局域搜索法 邻域搜索方法是一种随机性和启发式的优化方法。它从若干解出发，通过对其 邻域的不断搜索和当前解的替换来实现优化。尽管这种方法需要的运行时间比启发 式方法长，但解的质量能得到显著提高。近年来，一些高级局域搜索法由于具有普 遍适用性和较低的经验复杂性等优点，得到了广泛的重视和应用。它们是对传统搜 索方法的一种改进，下面是目前常用的几种方法。 a 遗传算法n8 憎1 ：g o l d b e r g 首次将遗传算法应用到实际的工程系统优化当中，由 于该算法在理论上和经验上都被证实能提供在复杂空间中的鲁棒搜索，因而被广泛 应用于机器学习、控制、优化等领域。遗传算法在生产调度中的应用也已很多，但 这些大都以传统的j o b s h o p 或f l o w s h o p 为背景。遗传算法的主要缺陷是早熟和搜索 效率低。 b 禁忌搜索啪1 ：禁忌搜索算法是由g l o v e r 提出的用于解决组合优化问题的一种 搜索策略和方法。目前，禁忌搜索已在调度、旅行商问题等诸多领域中得到应用。 c 模拟退火乜u ：模拟退火算法将组合优化问题与统计力学的热平衡问题类比， 通过模拟退火过程，可找到全局最优解。模拟退火能较好地避免局部最优，但算法 6 青岛大学博士学位论文 的收敛速度很慢，这成为该算法进一步应用的阻力。 除了上述几种主要的生产调度方法外，近年来，随着最优化技术的发展，一些 新的优化算法，如蚁群算法瞳羽、免疫算法1 、微粒群算法口4 1 等也被应用于生产调度 问题中，并取得了较好的优化结果。 ( 1 2 ) 混合调度方法乜2 潘1 将各种优化调度算法进行有机混合，充分利用不同算法的优点，取长补短，有 效地提高了系统优化的效率，目前，混合算法在求解调度问题的最优解以及跳出局 部最优等方面已经显示出其良好的性能，混合算法也将是调度算法的一个新的发展 方向。 1 3 4 车间调度问题的发展趋势 虽然车间调度问题的研究已有5 0 多年的历史，但因其复杂性，至今尚未形成一 套系统的方法和理论，理论研究与实际应用之间还存在着很大的差距。今后调度问 题的研究应向下面几个方向发展： ( 1 ) 实用化 一些理论上的最优调度方法虽然能够提供最优调度，但由于其计算复杂性大， 并且忽略了诸多实际因素，离实际应用还有很大差距。因此如何综合运用现有优化 算法来指导车间调度问题是一项具有重大意义的研究课题。 ( 2 ) 集成化 计划是回答应该生产什么，而调度则是回答怎样生产，二者相互联系。建立一 个集成系统，调度层将车间状态反馈到计划层，而计划层又根据车间状态制定新的 计划或更改原来的计划；计划层再把变化了的计划下达到调度层，调度层根据变化 了的计划调度生产。 ( 3 ) 高效智能化 寻找新的调度算法，该算法应该能够快速、高效地找到大规模调度问题的最优 解或次优解，并能对找到的解进行评估。 ( 4 ) 柔性化 传统的车间调度问题仅考虑每一工件具有唯一确定加工工艺路线。随着加工技 术、自动化技术的发展，特别是柔性加工系统的出现，打破了以往工件加工工艺路 线唯一确定的限制，工件具有多个可选择的加工路线。 ( 5 ) 实时化 进一步研究车间的动态特性，探讨车间状态的变化规律，找到更能反映车间状 z 第一章绪论 态变化的调度方法。在加工过程遇到扰动、机器故障或是有紧急订单需要处理时， 生产系统要能实时地做出反应，使系统持续地、优化地运行。 1 4 供应链调度问题的研究现状 供应链调度优化问题目前还属于一个崭新的研究课题，国内外相关文献还不多， 部分是起源于早期的生产作业调度问题防别，f a b r i c ec h a u v e t 啪1 等人提出了一种可以 用来求解随时可能进入加工系统的一个工件的调度问题的算法。i g o ra v e r b a k h 1 等 人从理论上研究了在线调度问题，其中顾客给制造商下达订单，制造商要加工产品 并将产品运送给顾客，目标是最小化总成本。c h e n 脚瑚3 等研究了一种组合启发式算 法，该算法用来解决带有时间窗约束的化工流水线问题。h a l l 和p o t t s m 3 最早提出 供应链调度的概念，文中以最小化总调度和运输成本为目标函数，研究了供应链环 境中各种调度、分批及运输问题。 1 5 本文的主要工作 第一章简要介绍了本文的研究背景及目的意义，车间调度问题的分类、特点以 及近年来研究车间调度问题的主要方法。分析了车间调度问题的发展趋势，指出了 车间调度问题要与生产实践相结合，向着实用化、集成化、高效智能化、柔性化及 实时化的方向发展，并描述了供应链调度问题的研究现状。 第二章介绍了遗传算法并给出了其在车间调度问题中的应用。首先，针对作业 车间调度问题的特点，设计了基于优先调度权值及采用三个体交叉的遗传算法，给 出了该算法在作业车间调度问题中的具体应用方法。然后，为避免遗传算法的早熟 收敛，我们引入了免疫算法，提出了基于动态评价免疫遗传算法。采用正交试验法 来设计算法中的重要参数，给出了基于正交试验的免疫遗传算法在作业车间调度问 题中的具体应用。仿真实验表明，该算法的搜索效率和稳定性都有了很大的提高。 第三章对微粒群优化算法做了详细描述。微粒群算法是一种基于迭代的优化算 法，具有个体数目少，计算简单，鲁棒性好等特点。本章针对算法的研究现状、存 在问题及研究方向做了详细介绍。 第四章研究了微粒群算法在作业车间调度问题中的应用。首先，针对作业车间 调度问题的特点，给出了基于粒子坐标值排列编码，这种编码方法成功地将解决连 续优化问题的微粒群算法应用到j o b s h o p 这种离散问题当中，通过与遗传算法进行 比较分析，仿真结果令人满意。其次，在微粒群算法的基础上，对迭代公式加以改 进，引入了加速度的概念，这种进化算法能够极大程度地保留微粒群中的有益信息， 8 青岛大学博士学位论文 从而可以减少进化代数，仿真实验也证明了这一点。 第五章对供应链管理下的生产计划与调度问题进行了相关研究。介绍了供应链 和供应链管理的概念及特征，然后描述了在供应链环境下生产系统的协调控制及车 间调度问题。 第六章在f l o w s h o p 及j o b - s h o p 调度问题背景下，研究了对顾客下达的紧急订 单制定生产方案并通过电话或互联网对顾客订单及时反馈的问题。本章首先描述了 无等待供应链在线调度问题的国内外研究现状；然后给出了问题的研究背景及改进 微粒群算法；最后，提出了无等待实时调度算法，并用该算法对f l o w - s h o p 和j o b s h o p 算例进行了求解。 第七章在上一章的基础上进行了推广，考虑了机器人转移工件时的运输时间， 并给出了解决该类问题的带运输时间的无等待实时调度算法，计算机仿真结果也显 示了该算法的有效性。 最后结论部分归纳了本文的主要研究成果及创新点，并提出了作者下一步的研 究方向。 9 青岛大学博士学位论文 第二章遗传算法及其在车间调度问题中的应用 这一章主要研究了遗传算法在作业车间调度问题中的应用情况。首先介绍了经 典遗传算法编解码、复制交叉及变异等重要操作算子在作业车间调度问题中的具体 应用过程；其次，我们给出了基于优先权值编码的三个体交叉的遗传算法；最后， 通过实验仿真，验证了所提算法在作业车间调度问题中的有效性。 2 1 遗传算法简介 自然界的生物进化是按“适者生存，优胜劣汰”规律进行的，m i c h i g a n 大学 h o l l a n d 教授根据这一规律于19 7 5 年首次提出了遗传算法( g e n e t i ca l g o r i t h m ，g a ) ， 其基本思想是力求充分模仿这一自然寻优过程的随机性、鲁棒性和全局性。遗传算 法将问题的解表示成为“染色体”，将目标函数转换为适应度函数，将生物进化中优 胜劣汰，自然选择，适者生存和物种遗传的思想抽象成为复制、交叉、变异等算子， 借用生命遗传中新一代胜过旧一代的现象，逐步寻找最优解( 或次优解) 。该算法主 要特点是直接对结构对象进行操作，7 不存在求导和函数连续性的限定；具有内在的 隐并行性和更好的全局寻优能力；采用概率化的寻优方法，自动获取和指导优化的 搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已 被人们广泛应用于计算机科学、优化调度、运输问题、组合优化、信号处理等多个 领域，它是现代智能计算中的关键技术之一。 2 2 遗传算法的基本操作 遗传算法主要有三个步骤5 1 ： ( 1 ) 染色体编码 编码实现了问题解空间到遗传编码空间的转换过程，由于遗传算法不能直接处 理实际问题的参数，必须首先对实际问题进行抽象，把问题空间映射到编码空间， 以便于该算法的遗传进化。用遗传算法有效解决具体优化问题，在编码方面注意以 下三个基本准则： a 完备性：完备性要求问题空间中的所有解都能作为遗传算法空间中的染色体 来表现； b 健全性：遗传算法空间中的染色体能对应所有问题空间中的候选解； c 非冗余性：染色体和候选解一一对应。 第二章遗传算法及其在车间调度问题中的应用 以上三点只是运用遗传算法解决问题时的一般准则，并没有考虑问题具体信息。 在实际求解时，并不需要满足上面的所有要求。有时适当增加编码的冗余度，反而 能简化算法的实现，因为很多实际问题，尤其是有强约束的组合优化问题难以编码， 适当增加编码冗余度常常能有效降低编码难度。 ( 2 ) 设定适应度函数 在遗传算法的选择过程当中，个体的存活概率是由它的适应度函数值的大小决 定的。适应度函数决定了个体的适应度，从而指导遗传算法的进化方向，因而针对 问题的寻优目标设计一个合适的适应度函数非常重要。 ( 3 ) 设计遗传算子 遗传算法的核心是三个算子： a 选择：从当代群体中选择个体进行遗传的操作，通常采用的选择算子是轮盘 赌。选择算子体现了优胜劣汰的思想。值得注意的是：选择性过强，可能会导致早 熟收敛，陷入局部最优；过弱，则会使寻优过程太慢。 b 交叉：两个或三个染色体m 1 交换基因，以产生新的个体。目前常用的两个体 交叉算子有基于位置的交叉、部分映射交叉、顺序交叉、循环交叉和基于顺序的交 叉等陋7 1 。交叉概率通常取0 l 之间的较大值。 c 变异：随机改变染色体中的一位或多位，以模拟遗传中的变异现象。当群体 早熟时，变异就可以跳出局部极小。变异算子有利于保持种群多样性，但过大的变 异概率能使遗传算法行为趋于盲目随机搜索。变异概率通常取0 - - 1 之间的较小值。 2 3 遗传算法在j o b s h o p 调度问题中的应用 2 3 1 作业车间调度问题的描述 作业车间调度问题旧1 ( j o b s h o pp r o b l e m ，j s p ) 描述如下：对于有疗个工件、m 台 机器的调度问题，每个工件有m 道工序，每道工序要求在不同的机器上加工；已知 各个工序的加工时间和各个工件在各机器上的加工次序约束，求出在满足工艺约束 条件下的一个调度，使得加工性能指标达到最优。加工过程中还要满足下面的条件： 每台机器一次只能加工一个工件；一个工序一旦开始加工就不能被中断。下表给出 了一个3 个工件3 台机器的调度问题，要求出一个最优调度，使其生产周期最短。 1 2 青岛大学博士学位论文 表2 1 ：一个3 工件3 机器j s p 的加工数据 加工时间机器顺序 工工序工工序 件l23件123 z2 56 以 132 j i 278 j i 2l3 j 、 541 ，3 123 以往解决该问题主要有以下几种编对方式驯：基于操作的编码、基于工件的编 码、基于先后表的编码、基于工件对关系的编码、基于优先规则的编码、基于析取 图的编码、基于完成时间的编码、基于机器的编码及随机键编码等。 2 3 2 编码方法 合理的编码方法可有效降低由于约束条件的限制而给问题求解带来的难度，我 们采用了一种基于工序的染色体编码方法。染色体的长度为门x m ，染色体中每个基 因的取值范围为l 到刀m ，并且各基因值不能重复。在这里每个基