（管理科学与工程专业论文）作业车间双向调度的遗传算法及蚁群算法研究.pdf

摘要 摘要 作业车间调度问题是一类典型的生产任务给定条件下资源分配的组合优化 问题 许多实际工程问题均可以与之相转化 双向调度问题属于经典调度问题 但它不仅以生产周期为调度目标 还加入了对关键工件截止期的考虑 即 保证 关键工件满足截止期的前提下 尽可能减小调度周期 从而在现实生产中可以有 效降低损失 提高利润 这类问题比普通的经典调度问题更加复杂 但它更接近 实际工作环境 因此对此问题的研究具有重要的理论经济价值 首先 本论文概括性的介绍了调度问题的一些基本概念 定义 分类与常用 的求解算法 总结了本文相关方面的研究现状和成果 然后 本论文将遗传算法与双向调度算法结合 给出了双向调度问题的一种 可行的解决方法 并通过仿真实验验证了其可行性 其次 本论文将蚁群算法与双向调度算法结合 用以解决以生产周期和关键 工件交货期为优化目标的车间作业调度问题 在传统的蚁群算法的基础上自适应 调整挥发系数p 采用了新的启发式规则定义能见度函数叩 f a l l o w e d 表的更 新也有所不同 最后通过仿真实验证实了自适应蚁群算法在解决双向调度问题时 要优于现在广泛采用的遗传算法 最后 在总结全文的基础上 对今后的研究提出了建议和展望 关键词 作业车间双向调度生产周期截止期遗传算法蚁群算法 a b s t r a c t a b s t r a c t j o bs h o ps c h e d u l 洒gp r o b l e mi sah n do fm o s t 帅i c a lc o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m sa b o u tr e s o u r c ed i s t r i b u t i o n 血w h i c hp r o d u c e t a s ki sg i v e n h t so f p r a c t i c a l p r o b l e m sc a n 白眦塔f o 肋谢t hi t b i d i r e c t i o ns c h e d u l i n gp r o b l e mb e l o n g st 0c l a l s s i c a l s c h e d l l l i n gp m b l e m h o w e v e r i t ss c h e d u l i n ga i mi sn o to m ym a k e s p a n b u ta l s o 雠 i n gd e a d l i n eo f t 1 1 ec r i t i c a lj o b si n t oa c c o m t m a ti s 吼d e rp r e c o n d i t i o no fe n s 砸n g 撕t i c a lj o b st os a t i s 匆d e a d l i n e t or e d u c em a k e s p a na sm u c ha sp o s s i b l e s ot h a t 洫 p r a c t i c a lp r o d u c t i o nw ec a l ld e c r e a s el o s s e sa n di n c r e a s ep r o f i t se 伍c i e n u y t t l i ss o r t o fp r o b l e mi sm o f ec o m p l e xt h a j lc o m m o nc l a s s i c a ls c h e d u l i n gp r o b l e m s b u ti ti s c l o s e rt 0r e a le n v i r o i l r n e n t t h 耵e f o r e t h e r ei ss i 嘶f i c a n ta c a d e m i ca n de c o n o m i c v a l u ei nm er e s e a i c ho ni t f i r s to fa l l t 1 1 i sp 印e rg e n e r a l l yi n t r o d u c e ss o m eb a s i cc o n c e p t i o n s d e f i i 血i o n s c l a s s i f i c a t i o n s a n da l g o r i m m st 0g e tn l es o l u t i o na r ns m t u l l a r i z e st h er e s e a r c hs t a t u s q u oa n d r e s u l t sa b o u tt i l er e l e v a n i a l s p e c t s s e c o n d l y t l l i sp a p e rc o m b i n e sg e n e t i ca l g o r i n u l l r i mb i d i r e c t i o ns c h e d u l i n gp r o b l e m p r o v i d i l l gaf e a s i b l es 0 1 u t i o nt ob i d i r e c t i o ns c h e d u l i n gp r o b l e m t h e nt h i sp a p e r p r o v e si t sf e a s i b i l i t b ye m u l a t i o n a le x p e r i m e n t n l i r d l y t h i sp a p e rc o m b i n e sa n 觚tc o l o n ya l g o 棚1 1 1 1w i t hb i d i r e c t i o ns c h e d u l i n g a l g o r i t h mt os o l v em ejo bs h o ps c h e d u l i n gp r o b l e mw i mt h eo p t i m i z a t i o na i mo ft h e m a l e s p a l la 1 1 dd e a d l i n eo fc r i t i c a lj o b s b a s e do nt h e 删i t i o n a la j l tc 0 1 0 n y 出g o r i t h m e 删u s tt l l ee v a p o r a t i o nc o e 觚i e n tpa d a p t i v e l y a d o p tn e wh e u r i s t i cn l l e st o d e f i n et 1 1 ev i s i b i l i t r 劬c t i o n f a 1 1 du p d a t e 伽l ea l l o w e di 1 1ad i 虢r e n t m a y b e s i d e s 也ea d a p t i v ea n ta l g o r i t h ni sp r 0 v e dt ob eb e 讹rm a l l 妒n e t i ca l g o r i t t l n w l l i c hi sw i d e l yu s e dn o a d a y si nb i d i r e c t i o ns c h e d u l i l l g l a s tb u tn o tt h el e a s t is u mu pm ew h o i ep a p e r 孤1 dp r e s e n ts o m ep r o p o s a l sa i l d p r o s p e c t st 06 m l r e r e s e a r c h k e yw o r d s j o b s h o p b i d i r e c t i o n s c h e d u l i n g m a k e s p a j l d e a d l i n e g e n e t i c a l g o r i t h m a n tc o l o n ya l g o r i t h m 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文 是本人在导师指导下进行研究工作 所取得的成果 除已特别加以标注和致谢的地方外 论文中不包含任 何他人已经发表或撰写过的研究成果 与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明 本人授权中国科学技术大学拥有学位论文的部分使用权 即 学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版 允许论文被查阅和借阅 可以将学位论文编入有关数据库进行检 索 可以采用影印 缩印或扫描等复制手段保存 汇编学位论文 俨彳 作支名 垃 第一章绪论 第一章绪论 作为优化组合领域中的一类重要问题 调度问题在柔性制造系统 现代物流 计算机科学等领域的应用非常广泛 目前 全球性的竞争和经济发展趋势又将制 造业产品生产 分销 成本 效率推向一个新的境界 也不断向制造管理者提出 新的挑战 制造业为适应企业新的市场变化 正努力寻求新的管理和生产模式 管理自动化是制造业发展的必然趋势 而计算机辅助生产计划与控制系统是管理 自动化的核心技术 能否科学合理地确定生产计划与调度系统直接关系到企业的 经济效益和产品竞争力 使企业的物流 信息流与价值流尽可能同步 从而有效 提高生产设备的利用率 使局部工序最优化 进而达到缩短产品生产周期 减少 库存 提高生产效率 提高产品品质的目的 最终降低成本 增加利润和提高顾 客满意度 所以 调度系统性能的优劣对许多行业能否高效运作有着极为重要的 影响 然而调度问题的求解却很困难 绝大多数调度问题都是n p 难 甚至是强 n p 难的 但鉴于上述原因 纵然求解调度问题之路荆棘满路 仍然使无数国内 外学者孜孜以求 本章首先介绍了本文将涉及到的调度问题中的基本概念和符号 然后阐述了 本文研究的具体问题一双向车间作业调度问题 以及相关的研究现状 最后概述了 本文的研究动机和论文结构 1 1 基本概念与符号 调度问题是指如何分配有限资源来完成给定作业或任务 并使目标函数最优 的决策过程 目标函数通常是对资源利用率 完工时间 或加工时间长短的描述 作业车间 j o bs h o p 调度问题是一类典型的生产任务给定条件下资源分配 的组合优化问题 具有约束较多 计算量大的特点 许多实际工程问题均可以与 之相互转化 作业车间问题可以描述为 设有n 个工件 m 台机器 已知每个工 件的加工路径和在相应机器上的加工时间 确定各台机器上各个工件的每道工序 加工的先后次序 在满足约束条件的前提下 使给定性能指标得到优化 调度问 题来源于实际生产 因此形态各异 但总体上讲 该问题具有以下几个特点 多约束性 大量的研究工作者对生产调度问题作了几十年研究 仍不能找到 解决一般性问题的算法 就是因为它是 个复杂的组合优化问题 含有大量的约 束 工件 机器设备 库存和运输系统之间相互影响 相互制约 每个工件还要 考虑它的加工时间和安装时间 因而相当复杂 在计算量上也往往是n p 完全问 题 并随着问题规模的扩大 计算量急剧增加 第一章绪论 随机性 实际生产中有很多不确定性因素 如临时插入的紧急生产任务 系 统中常有的突发偶然事件 如机器故障 等 多目标 评价调度优劣的指标很多 达几十种 如 以工件总的完成时间最 短为目标 以不超过工件交货期为目标和以最小生产成本为目标 实际调度往往 是多目标的 如既希望在交货期内完成 又要求生产成本最小 为简化叙述 本文使用通用的三元组符号口i iy 来描述调度问题的类型 即从机器 工件和目标函数三个要素来定义调度问题 1 口域表示机器的数量 类型和环境 主要有 a 1 s i n g l ep r o c e s s o r 指只有一台机器 此类问题称为单机问题 b 尸 i d e n t i c a lp a r a l l e lp r o c e s s o r 同速机 指所有的机器都具有相同的速度 q 吼i f o n l lp a r a l l e lp r o c e s s o r s 恒速机 指机器的速度有所不同 但每个机 器的速度都是常数 不依赖于被加工的工件 尺 瑚啪l a t e dp a r a l l e lp r o c e s s o r 变速机 指机器的速度依赖于被加工的工件 尸 q 尺类机器统称为平行机 记机器的数量为m 则上述三类平行机问 题依次表示为己 q 卅 如 c f n o ws h o p 机器模型 流水作业 指工件需要在所有机器上加工 且每 个工件在所有机器上的加工序列相同 j j o bs h o p 机器模型 异序作业 指工件需要在所有机器上加工 且每个 工件有自己的加工顺序 d o p e ns h o p 机器模型 自由作业 指工件需要在所有机器上加工 而每 个工件在所有机器上的加工顺序可以任意 记机器数量为m 则上述三类车间调度问题依次表示为巴 厶 q 2 域表示工件的性质 加工要求和对加工的限制等约束条件 它可同时包 含多项 也可为空 如 p 删切 p 删甜分别表示工件有到达时间 工件加工时 允许中断 车间调度中工件按照排列方式加工 3 y 域表示目标函数 常见的目标函数有 最大延误数k 制造跨度 m a k e s p a l l c m 加权完工时间和罗国 c 等 本文研究的即是在非过载情况 u 一 j jj 下 以制造跨度为目标函数 并保证关键工件按时完成的双目标双向调度算法 1 2 双向调度问题 1 2 1 经典调度问题及现代调度问题 调度问题可以分为经典调度 c l a s s i c a js c h e d u l i n g 和现代调度 m o d e m s c h e d u l i n g 根据e l a u l e r 等的总结 1 经典调度有如下四个基本假设 2 第一章绪论 资源的类型 一台机器在任何时刻最多只能加工一个工件 个工件在任何 时刻也最多只能被一台机器加工 确定性 调度问题的一个实例所需的任何输入参数都是事先知道的 完全确 定的 可运算性 经典调度实在可以运算的程度上研究调度问题 而不去顾及诸如 如何确定工件的交货期 如何购置机器和设备等技术上可能发生的问题 单目标和正则性 经典调度假设调度的目标是使衡量排法好坏的一个一维目 标函数的函数值最优 此目标函数是任何工件完工时间的非减函数 即正则函 数 现代调度问题根据实际生产的需要 打破了经典调度问题的诸多限制 使研 究更加接近现实情况 增强了算法的实用性 唐国春等在其著作 现代排序论 里 2 详细介绍了发展较为完备的1 0 种现代调度模型 其中成组分批调度 s c h e d u l i n gw i t hb a t c h i n ga u l di o t s i z i n g 同时加工调度 b a t c hs c h e d u l i n g 不 同时开工调度 s c h e d u l i n gw i t hn o n s i m u l 协n e o u sm a c h i n ea v a i l a b l et i m e 和资源 受限调度 r e s o u r c e c o n s n 面n ts c h e d u l i n g 打破了假设 1 的限制 可控调度 c o n t r o l l a b l es c h e d u l i n g 随机调度 s t o c h a s t i cs c h e d u l i i l g 模糊调度 如z 巧 s c h e d u l i n g 和在线调度 o n l i n es c h e d u l i n g 打破了假设 2 的限制 多目标 调度 m u l t i c d t e r i as c h e d u l i n g 准时调度 j i t s c h e d u l i n g 和窗时调度 d u e 研n d o w s s c h e d u l i n g 打破了假设 4 的限制 1 2 2 双向调度问题 双向调度问题 3 是一类比较特殊的经典调度问题 它属于经典调度问题 但 是又不完全符合经典调度问题的假设 4 即它的调度的目标不完全是一个一维 目标函数的函数最优值 而要加入对加工任务的分类考虑 根据生产中遇到的现实情况 可以将生产任务分为两类 一类具有硬截止期 这类任务如果不能在规定时间内完成 将会带来很大的损失或者赔偿 我们称之 为关键工件 另一类只有软截止期 这类任务的交货期比较灵活 没有硬性规定 我们称之为一般工件 如果我们仅从生产周期这一单一目标出发 很可能使生产 周期达到了最短 而某些关键工件却超过了其截止期 带来很大的经济损失 基 于这一普遍问题 讨论以生产周期和关键工件截止期为双目标的双向调度算法就 具有了它的现实意义 所谓双向调度 即先对关键工件从截止期向前逐个工序进行反向调度 机床 首先满足关键工件的需求 然后根据机床剩余的空闲时间对一般工件进行正向调 度 因此 在非过载的情况下 双向调度算法既能使关键工件按时完工 又能使 第一章绪论 一般工件尽快完工 由于考虑了关键工件的截止期这一因素 所以双向调度的结 果通常不是生产周期最短的调度方案 但是却能最大限度的保证企业的经济效 益 因此双向调度算法的最主要调度目标并不是生产周期最短 而是经济效益最 大化 损失最小化 从双向调度算法提出至今 一些国内外学者在这方面已经做了一些研究 但 是解决方法始终围绕着遗传算法 蚁群算法虽然在解决j s s p 问题上有着自己独 特的优势 如采用分布式并行计算机制 易于与其它方法结合 鲁棒性强等 但 由于双向调度算法的问题模型与传统的蚁群算法模型差异较大 难于移植 所以 如何将蚁群算法与双向调度算法有效结合 解决具有硬截止期的j s s p 问题 是 本文的重点所在 1 3 调度方案中的生产费用评价指标 制造业中的生产计划调度问题在理论研究和实际应用方面都是一个难题 探 索实用和有效的解决方案仍是国际上广为关注的热点研究课题 目前在大多数调 度文献中都采用时间指标评价调度方案 4 常用的有 生产周期 m a l e s p a l l 延迟时间 t 砌i n e s s 平均流动时间 m e a l ln o wt i m e 以及基于成本的调度指 标 工件的加权流动时间和加权拖期 w e i g h t e df l o wt i m ea 1 1 d e i 曲t e dt a r d i n e s so f i o b 等 这些指标一方面往往是相互冲突的 比工件延误时间最小的调度平均 流动时间经常是令人难以接受的 另一方面时间指标也不能正确反映调度过程中 发生的各种费用 如原材料费 在制品库存费用 机床工时费 直接工人的工资 和工件提前或拖期完工造成的损失等 而这是企业十分关心的 按 成本会计 的规定 工业企业产品成本的内容包括直接材料费用 直接人工费用 其它直接 费用和间接费用四部分 为全面反映调度过程中发生的生产费用 s m i t h d 砌i e l 等学者提出了调度 净现值指标 净现值就是将各时间点上的现金流量按基准受益贴现到基准年后加 在一起所得的值 净现值方法既考虑了资金的时间价值 又考虑了企业的投资效 率 虽然净现值指标较全面地反映了调度过程中发生的费用 但涉及的参数多 使用不方便 由于调度周期短 设置资金贴现率为零 则可忽略资金未来贴现率 此外 零件的原材料费用和收益在调度过程中是常数 亦可忽略而不至于影响调 度决策 s h a f 犯i 和b n l n n 得到了单加工资源单工艺路线调度的简化的生产费用计算 公式 但是 在实际生产过程中 一个零件往往有多条可选择的工艺路线 不同 的工艺路线可选择不同的加工机床 一台机床也可由多个工人分别来操作 不同 工人的技术水平 生产效率不一 机床的工时费可能不同 这也是影响生产调度 4 第一章绪论 决策的因素 再者 零件提前完工发生的库存费用 拖期完工发生的延误惩罚分 别是提前时间或滞后时间的线性函数 基于以上分析 得到第i 个零件选择第j 条工艺路线加工的生产费用计算公式为 卿 m s 飞 m m i f i i j t 独 s 绀i s u q ia 邮 6 1 式中 g 一受调度影响的生产费用 1 1 一年收益率 h 一工序u 独的准备好时刻 f 一加工工序u i j i 的机床工时费 彘 一加工工序u i j i c 的工人小时工资率 m i 一工件i 的原材料费用 n 一待加工工件的数量 包一工件i 的提前完成时间 色 m a x o z c 嘞 n i 一工件i 的提前惩罚系数 6 i 一工件i 的延误惩罚系数 0 i i k 工件i 的第j 道工序在机床k 上进行的操作 d i 若c i i l i i d i 矿d k 其余 一生产周期 1 4 计算复杂性与n p 类问题 组合优化问题 2 5 6 7 的难易程度是针对一些有代表性的问题而言的 所谓问题是指需要回答的一般性提问 通常含有若干个参数或者自变量 若给定 所有参数具体值后 便可得到问题的一个实例 即使一个最优化问题 就是这个 问题的一些实力的集合 如对于问题l c 当工件个数n 以及各工件的加工 时间p i 到达时间i i 等情况都确定之后 就得到问题1 l l i i c 咪的一个实例 某一 组合最优化问题的任一实例能否被实际有效的解决决定了其难易程度 实例用计算机表示出来所占用的存储单元数 定义为实例的大小 或输入规 模 当计算机每执行一次初等运算 包括算术运算 比较和转移 需要一个单 位时间 一个算法在计算机上执行所需要的时间定义为其执行初等运算的次数 对于所有规模为n 的输入 算法的行为可能不同 我们把其中最坏的行为定义为 算法关于规模为n 的复杂性 因此算法复杂性是输入规模的函数 8 8 0 年代以后 调度问题的研究引入了计算复杂性理论 9 1 3 计算复杂性 理论认为 当算法的复杂性被输入规模的多项式界定时 该算法为多项式算法 第一章绪论 这样的算法是可以接受的 也是实际有效的 一般认为这样的算法为好的算法 一个组合最优化问题通常有三种提法 1 4 最优化形式 计值形式 判定形 式 我们按问题的复杂性把最优化问题分类 一个组合优化问题的判定形式可描 述为 给定一个组合最优化问题面n 厂 x s j x x 问是否存在可行解 使得 厂 三 这里x 是有限集 l 为整数 即判定问题是需要用 是 或 否 来 回答的问题类 一般我们根据判定问题的复杂性把最优化问题分类 用p 表示多项式时间算 法所能解决的判定问题类 即p 类是相对容易解决的最优化问题 它们有有效算 法 对于n p 一类问题并不要求他的每个实例都能用某个算法在多项式时间内得到 回答 而只要求 如果z 是问题的答案为 是 的实例 则存在对x 的一个简短 证明 其大小以x 的长度的多项式为界 使得能在多项式时间内检验这个证明 的真实性 由上述可见 有尸s p 设4 和4 都是判定问题 称4 在多项式时间内归结为4 当且仅当q 有多 项式时间的算法l 并且岛是多次的以单位费用把4 的算法一用作子程序的算 法 把乃叫做4 到以的多项式归结 如果给定任意符号串x 可以在 x 的 多项式时间内能够造出符号串y 使工是4 的回答为 是 的实例当且仅当j 是幺的回答为 是 的实例 则称判 定问题4 多项式地变换到另一个判定问题4 判定问题彳 p 称为是n p 完备的 n p c o m p l e t e 简记为n p c 如果所 有其他的n p 问题都能多项式归结到a 此时 判定问题a 所对应的由最优化形 式描述的问题称为是n p 难的 n p h 2 l r d 1 5 作业车间调度问题 j s s p 的研究现状 作业车间调度问题可以描述如下 给定一组作业 要求在一组机器上加工完 成 要满足以下约束条件 a 每个作业在机器上的加工次序给定 b 每台机器 在任何时刻最多只能加工一个作业 一个作业在一台机器上的加工成为一道工 序 工序加工的时间是固定的且工序一旦开始不能被中断 要找使所有作业加工 完成的时间 m a l e s p a n 最短的调度 此外 流水作业调度问题 f s s p 是j s s p 问题的特殊形式 即所有工件都 有相同的加工工序 柔性作业车间调度问题 f j s p 突破了资源唯一性的限制 每个工序可有多个不同的机器完成 从而使作业车间调度问题更加符合生产实 践 6 第一章绪论 1 5 1 作业车间调度问题的模型 8 1 5 1 1 整数规划模型 整数规划模型由b a k e r 提出 下面简单给出一个嘶州g c m a x 调度问题的常 用数学描述 施 z m a x m a x g 1 4 一1 s t c i k p i k m 1 a 址 c i h i 1 2 n l l k l 2 m c j k c i k m 1 x 啦 p i k i j 2 1 2 n k 1 2 m c i k o i l 2 n k 1 2 m x i i l 2 0 或l i j 2 1 2 n k 1 2 m 1 4 2 其中 式 1 4 1 表示目标函数 即m a k e s p a j l 式 卜4 2 表示工艺约束 条件决定的各工件的各操作的先后加工顺序以及加工各工件的各机器的先后顺 序 式中 符号巳和玩分别为i 工件在机器k 上的完成时间和加工时间 m 是 一个足够大的正数 和x 分别为指示系数和指示变量 其意义为 a 舭 1 孽母篓2 妻于机器k 力口工工件i 1 4 3 妓lo 非上述情况 叶 7 玉陡 j1 妻 冀1 垂三工伟在机器k 上加工 1 4 4 驰一1 0 非上述情况 叶 1 5 1 2 线型规划模型 a d 锄s 提出的线型规划模型假定 j 1 2 n 代表工件集合 m 1 2 m 代表机器集合 v o l r 1 表示工序集合 其中0 和r 十1 分 别代表开始和结束的哑工序 a 代表受条件a 限制的工序对的集合 k 代表在机 器k 上加工的工序对集合 巨代表在机器k 上加工的工序对 因此要受条件b 限制 阢和f 分别代表工序v 的加工时间和开工时间 工序0 和工序r 1 的加工 时间都是o 则作业车间调度问题可以描述为 i n i n t 什l m d i j a j 1 4 5 o j t j d ivt j 一 j d j i j e k k m t i 0 i v 任何满足式 1 4 5 的一组t i 0 l 什1 都称为一个调度 问题的目标就 是要找出一个t 件 尽可能小的调度 1 5 1 3 联络图模型 联络图是描述j s s p 的常用工具 对于n 个工件 m 台机器 共n 个操作 7 第一章绪论 的j s s p 所对应的联络图g a e 如图1 1 所示 其中 v 为所有操作构成的 顶点集 包括0 和n l 两个虚拟操作 分别表示加工开始和结束 a 为n 条子 边构成的边集 子边 实线 表示某工件按约束条件在所有机器上从开始到结束 的加工路径 e 为m 条子边构成的弧集 子弧 虚线 表示同一机器上加工各 操作的连接 图l l3 个作业 3 个机器的联络图 1 5 2 求解作业车间调度问题的方法 作业车间调度算法 1 5 大致分为两类 一类是精确算法 另一类是近似算法 也称作启发式算法 早期的调度算法致力于寻求问题的精确解 典型算法是整数 规划法和分支定界法 近似算法主要包括优先分配规则 拉格朗日松弛法 人工 智能 神经网络 转换瓶颈程序 局域搜索方法 1 5 2 1 精确算法 二十世纪六十年代 这个时期人们倾向于p n p 因此就努力去设计具有多 项式时间复杂度的确定型算法 以期求出该问题的最优解 精确算法能得到问题 的一个最优解 整数规划法因为其变量和约束条件个数太多 要实现它几乎是不 可能的 对于一个作业数为6 机器数为5 的算例 一个经过改进的整数规划算 法还有多达1 0 5 个变量和1 7 4 个约束条件 而用穷举法也是不现实的 n 个作业 由n 种加工顺序 从而m 台机器加工n 个作业就有 n m 种加工顺序 因此 采用新的枚举技术 l o m i l i c k i 提出分支定界法和g o l o m b 等提出的回溯算法 但 这些算法在人们可以接受的时间范围内 它们所能够计算的实例的规模很有限 实验报告表明 即使使用当今的大型机器 通常不超过l o o 个工序 1 5 2 2 近似算法 第一章绪论 二十世纪七十年代后 人们不再追求用精确的算法求出问题的最优解 而是 通过近似算法在可以接受的时间内寻求问题的满意解 因此提出用启发式方法来 解决这个问题 1 优先分配规则 优先分配规则是最简单的启发式方法 最早的分派规则由j a c k s o n 和s m i m 等提出 g i 胁和1 h o m p s o n 的算法是优先权规则调度算法的典型代表 1 9 7 7 年 p a n 砌k e r 和i s k a l l d e r 归纳了1 0 0 多个 最主要的有以下8 个 s p t s h o r t e s tp r o c e s s i n gt i m e 法则 即优先选择加工时间最短的工序 l p t l o n g e s tp r o c e s s i n gt i m e 法则 即优先选择加工时间最长的工序 f c f s f i r s tc o m ef i r s ts e e d 法则 即先来先服务 m w k r m o s tw b r kr m a i n i n g 法则 即优先选择余下加工时间最长的作业 i 册 r l e a s tw b r kr e m a i n i n 曲法则 即优先选择余下加工时间最短的作业 f a f i r s t a v a i l a b l e 法则 即优先选择立即可以被加工的工序 m o 补浓 m o s to p e r a t i o nr e m a i n i n g 法则 即优先选择余下工序数最多的作 业 n d o m 法则 即随机地挑选一道工序 这些规则按照某种方法对每一个将有可能被选取的操作做出相应的评价 将 一个数值作为满意度赋予该操作 这样每一个可能被选取的操作都有一个满意度 值 再根据问题的需要选择满意度适宜的操作 这类算法可以找到较好的近似解 但使用单一的优先规则得到的解不能满足要求 如何把多个规则进行融合 设置 一个合理的满意度值是近期研究的方向 同时 为了得到更好的近似解 研究者 们都把基于优先分配规则得到的近似解作为初始解 如禁忌搜索的初始解 2 拉格朗日松弛法 拉氏松弛技术作为一种求解复杂优化问题的近似算法 由于其能在较短时间 内获得高质量的次优解 并能进行性能评价等优点 近年来受到学术界的广泛重 视 将整数规划问题i p 按照拉格朗日松弛方法转化为拉格朗日松弛 扩大问题 的解空间 拉氏松弛算法得出问题的可行解是原问题的最优解的上界 再求整数 规划问题的相应对偶问题的解 它是原问题的最优解的下界 最后通过解的转化 使之成为原问题的可行解 3 人工智能 8 0 年代出现的人工智能和专家系统在调度研究中占据重要地位 可以产生 比优先规则更复杂的基于对整个调度系统的启发式 并能从特殊数据结构中获取 大量信息 缺点是计算比较耗时 i s i s 是最早基于a i 技术解决特定j s s p 的专 家系统之一 使用约束指导的搜索方法 其目标约束基于交货期和在制品 把资 9 第一章绪论 源的处理能力作为物理约束 a i 技术对如何协调各代理机制 目前还没有统一 的设计和指导思路 对作业调度集中化和分散化思想还在讨论中 4 神经网络 神经网络应用于调度问题已有十几年的历史 目前应用最多的是b p 网和 h o p f i e l d 网 yp s f 0 0 和y 呲e m j i 最早提出用h o p 丘e l d 网求解j s p 问题 是 一个比较有影响的方法 1 9 9 9 年r o v i t h a l i s g a 提出了神经网络用于f m s 系统 2 0 0 0 年y 锄g s x 等采用了满足约束条件的神经网络和启发式算法用于通用车间 的调度 但神经网络通过训练和学习来寻找输入和输出的关系 随着问题规模的 增大 网络的规模也急剧地增大 把神经网络与其他启发式方法相结合仍然是现 在研究的热点 5 转换瓶颈程序 a d a n l s b a l a s 和z a w a c k 在1 9 8 8 年首先提出了瓶颈机算法 s h i r i n gb o t t l e n e c k m a c h i n ep r o c e d u r e 他们提出一个给机器确定瓶颈度并优先给瓶颈度最高的机 器排序 这里的给机器排序就是给在同一台机器上加工的工序确定一个先后次 序 的方法 当用这种方法给所有的机器都排完序后 整个调度问题就解决了 为了给机器排序 对于每一台还没有排序的机器都在松弛原问题之后来求解这个 机器的单机调度问题 即每次只考虑一台机器的调度问题 用这些单机调度所得 到的时间跨度的大小来给这些还没有排序的机器确定优先级 优先级最高的机器 的瓶颈度最高 优先给瓶颈度最高的机器排序 每当一台新的机器排序完成之后 对那些已经排好序的机器进行再优化 这样有可能通过再求解一次单机调度问题 使最终求解的结果更优 当所有的机器的顺序都确定后 就可以很容易得求出调 度的时间跨度了 但s b 算法在计算大规模 1 0 宰5 0 的算例时出现了得不到解 的问题 黄文奇和尹爱华提出两种新方法 一是用了改进的c a l i e r 单机调度方法 使用带扰动的s c h r a g e 算法求解单机调度问题 对转换瓶颈算法的改进保证算法 一定能得到可行解 二是带部分回溯策略的改进算法 黄志等对转换瓶颈算法的 不可行解进行了探讨 找到一个反例证明用c a l i e r 算法作单机调度产生不可行解 的情况 因此 转换瓶颈算法虽然是一个很好的启发式算法 但它在用c a l i e r 算法做单机调度求解j s p 问题时可能会出现不可行解 6 局域搜索方法 1 遗传算法 d a v i s 首次将遗传算法 g e n e t i ca l g o r i t h m g a 用于解决调度问题 它将问题 的求解表示成染色体的适者生存过程 通过染色体群的一代代不断进化 包括选 择 交叉和变异等操作 最终收敛到 最适应环境 的个体 从而求得问题的最 优解或满意解 近年来 g a 得到了较为广泛和深入的研究 苏子林提出了采用 1 0 第一章绪论 海明距离的概念对种群进行修正 在进化过程中 不断淘汰较差的个体 不断引 入修正种群 保持了种群的多样性 李钢等提出的是混合的遗传算法 通过与其 它算法的结合弥补在局部搜索和早熟方面的缺陷 许晓栋等提出一种基于免疫原 理的遗传算法 当前使用的编码方法主要有9 种 研究者们通过对遗传算子进行 设计来不断改进 g a 原理和操作简单 通用性强 不受限制性条件的约束 且 具有隐含并行性和全局解空间搜索能力 但g a 的早熟和搜索效率低问题是它的 主要缺陷 2 模拟退火算法 模拟退火算法 s i m u l a t e d 灿m e a l i n ga l g o r i t h m s s a 是19 8 2 年k i r k p 撕c k 等人将金属热加工中的退火工艺的思想应用于组合优化问题领域而提出的一种 新的搜索技术 s a 算法采用m e 昀p o l i s 接受准则 以一组冷却进度表参数控制 算法过程 可以在多项式时间内找到金斯最优解 s a 算法是针对局部搜索算法 l o c a ls e a r c ha l g o r i t h m 改进而提出的 它是一种通用 高效 健壮 可行的拟 物型随机近似算法 s a 算法可以较容易地并行实现 赵良辉等对该算法进行了 改进 提出了记忆回火和快速退火的模拟退火算法 分别适合于求精度要求较高 的调度和大规模的调度 同时还与遗传算法相结合组成遗传退火算法 但如果要 得到一个高质量的近似解 需要花很长时间进行退火 s a 能较好的避免局部最 优 但算法的收敛速度很慢 搜索空间过于庞大 下降温度难以掌握 这成为进 一步应用的阻力 3 禁忌搜索方法 禁忌搜索 t a b us e a r c 是一个为优化组合问题寻求金斯最优解的启发式算 法 它由g 1 0 v e r 提出并形式化 b 锄e sa j l dn o w i c l i 对t s 做了改进 t s 是位跳 出局部最优而设计的一种确定性算法 在陷入局部最优时做上升移动 它能找到 调度问题中一些实例的最优解 禁忌搜索是一个效率较好的启发式算法 它能找 到调度问题不少算例的最优解 但禁忌搜索要面对很多的问题 如初始解问题 邻域结构问题 搜索策略和禁忌表的长度问题等等 只有很好的解决了这些问题 禁忌搜索算法才能表现得更好 尹爱华提出了禁忌搜索的一种新的邻域结构 用 改进的转换瓶颈算法得到初始解核对搜索策略进行了改进 试验结果表明该算法 性能很好 特别是发现一个实例的更低的上界 7 其它方法 近年来 一些近似方法的综合应用 比如局部邻域搜索结合移动瓶颈过程的 算法 禁忌搜索结合移动瓶颈过程 取得了很好的效果 黄文奇首先提出用拟物拟人的方法求解组合优化问题 后来又提出一种基于 拟物的策略求解j s s p 的快速算法 其效率优于其它启发式算法 因为它是有针 第一章绪论 对性地为具体的问题找到非常贴切的物理世界 而不是像遗传算法 神经网络方 法 模拟退火方法那样依赖于某个唯一的 始终不变的因而往往是不贴切的生物 或者物理的体系 然后拟人策略更是添加人类的智慧 利用人类丰富的经验往往 会得出好的启发式算法 拟物拟人方法是一个新的思想 它尚未得到人们的广泛 认可 纵观研究j s s p 的发展 经历了三个阶段 从最初的精确算法到基于简单的 优先分配规则的启发式算法 再到转换瓶颈和超启发式方法 取得了丰硕的成果 但也存在许多尚未解决的问题 近似算法能在可接受的时间范围内找到问题的满 意解 计算时间短 效率高 精度不如精确算法 衡量一个调度算法的好坏的标 准是解的优度和计算时间 基于简单优先分配规则的算法计算时间短 但解的优 度不如其他启发式算法 拉格朗日松弛法由于其本身的限制使用范围有限 且搜 索效率低 可行调度的构造有待进一步研究 神经网络的计算量随问题的规模急 剧增大 如何实现并行结构和并行处理以减小计算量是今后研究的方向 同时如 何使其更好地学习 训练进行自适应和自组织也是提高其计算能力的方面 转换 瓶颈算法的致命弱点在于不能总保证得到可行解 邻域搜索以一定的概率接受劣 解 从而逃离局部最优 但其主要缺点是需要多步实现 如何选择邻域 使其具 有强化性和多样性的搜索机制这一点很重要 又由于引入随机的概念 存在求解 性能稳定性的问题 拟物拟人算法的关键是到自然界寻找解决问题的贴切的模型 不是一件容易的事 1 6 研究动机 研究结果和论文结构 1 6 1 研究动机和结果 由1 5 节可以看出 关于经典调度问题的研究已有了相当丰硕的成果 但对 于更加贴近实际应用的双向调度却刚刚起步 双向调度概念的提出都为时不久 求解方法更是少之又少 如何分析双向调度算法本身的特点 并依据这些特性设 计性能更加优越的启发式算法是近一步研究的方向 本文首先介绍了如何使用遗传算法求解双向调度问题 进而提出了通过自适 应蚁群算法来搜索此类问题的解 并结合问题模型给出了相应的a l l o w e d 表 信 息素挥发系数和能见度的启发函数的定义 通过仿真试验可以看出 在迭代次数 相同的情况下 本文的算法求得的解比遗传算法具有更大优势 能取得实际应用 中较好的效果 1 2 第一章绪论 1 6 2 论文结构 第二章构造了双向作业车间调度问题的遗产算法 阐明了如何通过有效的编 码解码将遗传算法应用于双向作业车间调度问题 并通过交叉 选择 变异 最 终产生解的过程 第三章给出了自适应蚁群优化算法在双向车间作业调度问题中的应用 引入 机器利用率作为蚁群算法中的启发式信息 能见度 通过自适应的调整信息素 挥发系数 增强了算法的全局搜索能力和收敛速度 并通过仿真试验证明了 在 迭代次数相同的情况下 蚁群优化算法要优于遗传算法 第四章总结了全文的主要研究成果 并指出了目前的不足 对未来可能的研究方向做 了展望 第二章双向调度算法的数学模型及其遗传算法实现 第二章双向调度算法的数学模型及其遗传算法实现 本章首先简单介绍了遗传算法的一些基本概念和一般步骤 然后给出了双向 调度算法的问题描述和数学模型 并介绍了一种基于混合遗传算法的双向调度算 法来解决以关键工件交货期和生产周期为优化目标的作业车间调度问题 在算法 中 遗传算法在全局范围内搜索最优调度染色体 双向调度算法根据得到的染色 体进行调度 仿真结果表明该算法是可行的 与传统的调度算法相比 其优越性 是明显的 2 1 遗传算法概念 2 1 1 遗传算法的定义和特点 遗传算法 g e n e t i ca l g o r i t h m 是模拟达尔文的遗传选择和自然淘汰的生物进 化过程的计算模型 是用一种通过模拟自然进化过程搜索最优解的方法 它是由 美国m i c l l i g a n 大学j h o l l 狃d 教授于1 9 7 5 年首先提出来的 并出版了颇有影响 的专著 a d a p t a t i o ni i ln a t u r a la 1 1 da n i f i c i a ls y s t e m s g a 这个名称才逐渐为人所 知 j h o l l 锄d 教授所提出的g a 通常为简单遗传算法 s g a 2 1 1 1 遗传算法的定义 遗传算法 1 6 是从代表问题可能潜在的解集的一个种群 p o p u l a t i o r l 开始的 而一个种群则由经过基因 g e n e 编码的一定数目的个体 i n d i v i d u a l 组成 每个个 体实际上是染色体 c h r o m o s o m e 带有特征的实体 染色体作为遗传物质的主要载 体 即多个基因的集合 其内部表现 即基因型 是某种基因组合 它决定了个 体的性状的外部表现 如黑头发的特征是由染色体中控制这一特征的某种基因组 合决定的 因此 在一开始需要实现从表现性到基因型的映射即编码工作 由于 仿照基因编码的工作很复杂 我们往往进行简化 如二进制编码 初代种群产生 之后 按照适者生存和优胜劣汰的原理 逐代 g e n e r a t