学位论文之加工时间依赖开工时间的排序问题(pdf 39页).pdf

苏州大学 硕士学位论文 加工时间依赖开工时间的排序问题 姓名 胡金华 申请学位级别 硕士 专业 概率论与数理统计 指导教师 闻振卫 20070401 摘要 排序问题是一类重要的组合最优化问题 本文讨论了分段恶化捧序问题和带资源 约束的恶化捧序问题 第二章讨论分段恶化排序问题 本章考虑了单机分段恶化排序问题I IP F4 钟 删 b j d l w 0 根据最优解的性质给出了遗传算法和分支定界法 对于问题的较小 规模情形分支定界法能精确地求得最优解 对于问题的较大规模情形遗传算法能 很快地求得近似最优解 算例及大量实验表明用遗传算法来求问题的近似解是成 功的 第三章讨论带资源约束的单机恶化排序问题 本章讨论了两类问题 一类是资 源量满足一定要求 目标匾数为极小化最大完工时闻的单机恶化排序问题ll P F b J j a j u j 哟 疗IG 和lI P F s y b t j a j u j 疗IG 对于这两个问题分 别给出了针对任意给定排列的最优资源分配及在某些特殊情况下求得最优解的多 项式时间算法 另一类是完工时间不超过一定值 极小化资源总量的单机恶化排序 问题1 I 础一 c ks e I 吩和l l 胪矿 的一 G 0 I 吩 分别给 出了针对任意给定排列的多项式时间算法和启发式算法 关键词 捧序 分段恶化 遗传算法 分支定界法 资源约束 作者 胡金华 指导老师 闻振卫 一一 丝堕鲤 A b s t r a c t S c h e d u l m gp r o b l e mi sak i n do fi m p o r t a n tc o m b i n a t i o no p t i m i z a t i o np r o b l e m I n t h i st h e s i s w es t u d yt l 忙s i n g l em a c h i n es t e p d c t c r i o r a f i o ns c h e d u l i n gp r o b l e ma n dt h e s i n g l em a c h i n ed e t e r i o r a t i n gs d 幢d u l i n gp r o b l e mw i t h 坞 l m c ec o n s t r a i n n I i 3t h e s i s c o n s i s t so ft w op a n s t h cs i n g l em a c h i n e 删o r a t i o n s c h e d u l i n gp r o b l e m t h e s i n g l em a c h i n ed e t e r i o r a t i n gs c h e d u l i n gp r o b l e mw i t hn 渤u r c o l l s l f f R i n h lt h es e c o n dc h 耻r w ed i s c u s st h e 蚓em a c h i n es t e p d e t e r i o r a t i o ns c h 圳n g p r o b l e m W es t u d yt h e 叩t h l l a lp r O l 础So f t l mp r o b l e ml ip 口o ra b j 彳I 蝴 a n da c c o r d i n gt oi tak i n do f G A i m p l e m e n ta n dak i n do f B r a n c ha n dB o u n dm c t h o d a 坞g i V 钆T h e 嘶B r a n c ha n dB o m dm e t h o dc a nf i n do u tt h eo p t i m a ls o l u t i o no f t h ep r D I l e mi ns m a l ls i z e 诩蝴et h e 百V G A m p l e m e n t 啪q u i c k l yf i n do u lt h e a p p r o x i m a t eo 坩m a ls o l u t i o no f t h ep r o b l e mi nl a r g es i z e T h es i v e nG A i m p l e m e n t p r o v e st ob ev e r ye f f e c t i v eb yn u m e r i c a le x p e r i m e n t sa n de x a m p l e s I nm et h i r d 吐呵慨w ed i s 印鹳t w oc l a s s e so fs i n g l em 雒h i n ed e t e r i o r a t i o n s d 地d u l i n gp r o b l e mw i t hr c s o u r c 七 叫坞n a i n O n ec l a s si s 血em e n t i o n e dp r o b l o ni n w h i c ht h et e s o u l r 冶a m o u n ts a t i s f i e sac e r t a i nc o n d i t i o na n dt h eg o a li st om i n h n z et h e m a k e s p a n t h ep r o b l e mIl 旷蚴一a u j 叶 疗fC E a n dt h ep r o b l e m1f 旷簟 6 分一哪 吩s 痧lC m W ep r o v i d et h eo p t i m a l 他啾a l l o c a t i o n st o 趾y g i v e ns e q u e n c e sa n dt h ep o l y n o m i a la l g o f i t h m su n d e rc e r t a i nc o n d i t i o n so ft h et w o p r o b l e m t h eo t h e ro n ei st h em e n t i o n e dp r o b l e mi nw h i c ht h em a k e s p a ns a t i s t i e sa c e r t a i nc o n d i t i o na n dt h eg o a li st om i n i m i z et h et o t a ln 嚣o u I ea m o u n t t h ep r o b l e m lI p b s 一鹕c 哪 eI 吩a n dt h e p r o b l e m 1I p s y b O 一 se J 吩 A st ot h et w op r o b l e m s w er e s p e c t i v e l yg i v et h ep o l y n o m i a la I 鲥t h m t oa n y g i v e ns e q u e n c ea n dt w oh e u r i s t i ca l g o d t h m s K e y w o r d s S c h e d u l i n gp r o b l e m s l v p d e t e r i o r a t i o n G A B r a n c ha n dB o u n dm e t h o d I l m W r i t t e nb yH u J i n h u a S u p e r v i s e db yv i c e p r o f W e n Z h e n w d 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明 所提交的学位论文是本人在导师的指导下 独立 进行研究工作所取得的成果 除文中已经注明引用的内容外 本论文 不含其他个人或集体已经发表或撰写过的研究成果 也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料 对本文的研究作 出重要贡献的个人和集体 均已在文中以明确方式标明 本人承担本 声明的法律责任 研究生签名 j 牮名粤一日 学位论文使用授权声明 苏州大学 中国科学技术信息研究所 国家图书馆 清华大学论 文合作部 中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档 可以采用影印 缩印或其他复制手段保存论 文 本人电子文档的内容和纸质论文的内容相一致 除在保密期内的 保密论文外 允许论文被查阅和借阅 可以公布 包括刊登 论文的 全部或部分内容 论文的公布 包括刊登 授权苏州大学学位办办理 研究生签名 导师签名 日期 2 田 耸 日期 堡 厂遂 加工时问依赣开工时间的捧序同愿第一章序言 第一章序言 1 1 背景 掉序 s c h e d d i n g N 题是一类重要的组合最优化问题 它产生的背景早期是机器 制造 后来被广泛用于计算机系统 运输调度 生产管理等领域 事实上 捧序 问题在编制作业计划 企业管理 航空航天 医疗卫生等各个领域都有着广泛的 应用 它是利用一些处理机 p r o c e s s o r 或机器 埘a c h i n e 以及可能的资源 r e s o 珊c e 最优地 完成一些给定的任务 t a s k 或工件 i o b 在处理这些任务 或工件 时还 需满足某些限制条件 如任务可以有就绪时间 完工可以有时限 任务的加工可 以有顺序关系 如出树等 加工时间可以受资源的影响等 最优地完成指的是使目 标函数达到最小 目标函数通常是对加工时闻的长短 处理机的利用率等的描述 恶化排 亭 d e t e r i o r a t i n gs c h e d u l i n g f 司题是一类重要的新型现代捧序问题 在这 类问题中 工件的加工时间不为常数 而是开工时间的函数 且通常是开工时间的 增函数 这类问题产生的背景有 如 在银铁企业中 某些工件的加工有温度的 要求 在满足温度要求的情况下 工件的加工时间是常数 如果工件在加工前有等 待时间 将引起温度的下降 这样一来 无论是重新加温使其满足温度要求还是 直接在低湿下加工情况 都将导致加工时间的增加 这类问题模型在维修工作方 面 塑料工业及医疗等领域也有广泛的应用 1 2 常用记号 捧序理论中常用G r a h a m 等人首先使用的三元组来描述排序问题 三元组记号 由三个域组成 口I 声I 它们具有以下含意 a 域表示处理机的数量 类型和环境 它可以取 l 单处理机 P r o 肼台同速机 Q m m 台恒速机 R m m 台变速杌 F r o 辨台处理机流水作业 O r e 朋台处理机自由作业 或开放作业 d r a m 台处理机 异顺序作业 加工时问依赣开工时间的捧序目题第一章序言 F F s s 种处理机柔性流水作业 域表示任务的性质 工件加工的要求或限镧 资源对加工的影响等约束条 件 它同时可以包含很多项 可能的项包括 吩 工件有不同的就绪时间 若肿不出现伽则说明r O 产1 2 一 船 表示在任务n 的紧接T j 的安装时问 若T I 是第一个被加工的工件 则j 船 表示b 的起始安装时间 若弓是最后一个被加工的工件 则常用跏表示1 加工 后的清理时问 若安装时间与处理机一有关 则安装时间还要再多一个下标f 即 J 狮如果肿不出现哪 则所有的安装时间都是零 朋l p 加工时可中断 如果卢中不出现朋弘说明每个工件的加工不可中断 p r e c c h a i n s i r e t e e o u t t r e e 分别表示工件的相关性 一般优先 平行链 入 树和出树等约束 如果口中不出现此项 则表示工件集是无关的 域表示要优化的目标函数 它可以是 C m 戤 时问表长或最大完工时间 五q E w j C j 总完工时间 加权总完工时间 L m a x 最大延误 F D s Z w s O s 总误工 加权总误工 珥 E 岣珥 误工工件数 加权总误工工件数 I 3 论文主要内容 第二章讨论分段恶化排序问题 本章考虑单机分段恶化捧序问题l I 乒尹4 甜 a b s d I 乏 竹q 根据最优解的性质分别给出遗传算法和分支定界法 第三章讨论带资源约束的单机恶化排序f 司题 本章讨论两类问题 一类是资源 总量有限的单机恶化的最大完工时简排序问题 lf 胪呐一Q j U j qs 移lc 矗 和1I P Fs j b t j a t u s 哟 疗Ic 函c 另一类是最大完工时间不超过一定值的 极小化资源总量的单机恶化排序问题 1J 乃F 叻一q 畅c k s 0J 竹和1I 乃 讹一卿 c 矗 e I 吩 2 加工时问依赖开工时间的捧序闷题 第二章单机分段恶化捧序问题 第二章单机分段恶化排序问题 2 1 引言 近些年来 一类新型的捧序问题一工件加工时间依赖开工时间的排序问题 受到越来越多学者的关注 与传统捧序问题不同 此类排序问题中加工时间不是 常数 而是随着开工时间的推移不断增加的 即所谓的恶化 目前加工时问随开 工时间线性增加的捧序问题已有不少研究 1 0 1 1 1 3 1 4 1 而加工时间随开工时间分 段恶化的排序问题研究并不多 l 捌 本文考虑一类加工时间随开工时间分段恶化的 单机捧序问题lI p j ao r a b j d l H o 研究其最优解的性质并根据这些性质给出 了一种遗传算法和一种分支定界法 2 2 排序问题1I p j a 凹口 d l M 的求解 问题模型描述如下 设有疗个工件 厶 以需要在一台机器上加工 每个工件巧有一个基本加 工时间毋及共同恶化时刻诫痧o 当工件西的开工时间 用s j 表示 不迟于d 时 它 的加工时间就是a j 而当工件的开工时间迟于d 时 沪四 它还有一个额外的惩罚 时间鸟 因此巧的实际加工时间毋可表示为 fa J d 或2 h b Jj s j d 是工件珥的权重 q 表示工件正的完工时间 表示目标函数 那么产G O 或 哟分别代表最大完工时间 总完工时间及加权总完工时间 问题的目标是寻 找一个捧序极小化耳标函数 按三参数表示法 该类问题记为1I 万弛o r a 匆 d I f 分段恶化模型最早由M o s h e i o v 3 及S u n d a t a r a g h a v a n 和K u n n a t h u r 6 分别提出 M o s h e i o v 3 研究了时间表长问题 证明了问题1 1 只舟o l rm d IG 一是N 卜完 备的 并对某些更一般的情形给出了启发式算法 S u n a a r a r a g h a v a n 和硒瑚懈幽焖 研究了加权总完工时间问题l l p 口o r a b d I 乏 白 并对它的三种特殊情形分别 给出了最优算法 但未能阐明一般情形的该问题的复杂性 只给出了一个启发式 交抉算法 T C EC h a n g 和QD i n g 7 举例说明 6 中的启发式交换算法不能保 证最优 3 加工时间依赣开工时问的捧序闻愿 第二章单机分段恶化捧序问题 本文讨论加权总完工时间问题1I 四 4o ro b j 刎Y w C j 简称问题P 得到 了最优解的性质 并根据该性质设计了一种遗传算法且进行了求解实验 另外对 于问题P 的较小规模情形 提出了求最优解的分支定界法 并给出了分支定界过 程中下界的计算公式 通过分支定界法对算例的验证表明 这里提出的遗传算法 是有效的 2 2 1 最优解性质 对于问蹶P 的一个最优捧序 显然n 个工件在机器上是接连而无空闲地加工的 因此以下我们所讨论的捧序 都限于接连而无空阿地加工的捧序 这样的一个捧 序完全由l J 个工件的加工顺序所确定 因而以下我们所提到的排序就是一个拜元 排列 但是以下当我们提到 个刀元排列时 它并不直接就指一个排序 因为我 们所讨论的排序还要求该一元捧列满足一定的性质 为叙述方便 我们用 厶 五 表示全体工件的集合 以下对于问题P 的一个给定的排序盯 i l 1 2 柚 我们总是用R l 表示满足铲 d 的按给定顺序排列的工件集 其中七是R l 中的工件数 用恐 叱 气 表示满足毋 d 的按给定顺 序排列的工件集 惑中的工件数为n k 定理2 1 若口 i l 也 铜是问题P 的一个最优排序 则必满足 硒中工 件按w 非增序排列 简称此为L W 规则 L W 代表l 姆髓w e i g h t6 r s t R 2 中工件 按 兰 非增序排列 即关于j 庐叶吩与 I R gW S P T 规贝 J 口 乃 证明 由于问题l I I 乏 白按W S P T 规则 即坳 乃递减序 可得最优捧序 故问题II 力 口0 f 口 勃d I y w C j 的最优排序中R I 尼中工件均应按M 局递减序 排列 又岛中工件的加工时f 司p j a 置1 而飓中乃 口 岛 恐 故最优 排序中露l 中工件按哟非增序挥列 而惑中工件按 卑非增序排列 D 口十乃 定理2 2 届中的工件数J i 山创 1 其中用意义同定理1 M 是不大于x 的最大整数 证明 在 0 明时间段至多能加工山 口j 个工件 此处工件加工时间为 且第 4 加工时问依藏开工时间的捧序目置 第二章单机分段番化排序闩愿 L d 剧个工件也L 抛J l 的完工时问c I L 抛J d 即趣L 删 ll 4 但c L 划 Il 西从而可 得k L d a J 1 口 将定理l 中的两部分排序规则合称为L W W S P T 规则 或顺序 易见 当k n 即d n I 弦时 问题lI P J a o r 叶勃d l 坳0 就是经典 捧序问题1 I 功产n l 芝M O 因而按L W 规则即可得最优捧序 当k 1 或加l 时 我 们可按如下推论3 求得问题的最优排序 推论2 3 当忍中工件数 l 即o d a 时 把工件西放入R I 中 按 L W W S P T 规则计算相应的目标函数值仃 1 2 田 这疗个值中的最小者就是 问题的最优值 相应掉序为最优排序 当足I 中工件数k n I 即 卜2 亦O 卜l 弦 时 把工件 6 放入飓中 按L W W S P T 规则计算相应的目标函数值f f 1 2 帕 这刀个值中的最小者就是问题的最优值 相应排序为最优摔序 证明 由定理I 显然 口 从上述分析可知 求解问题lI 历 a o r a b j d I w 局只需考虑2 i 一 n 2 的 情形即可 由于该问题目前尚未找到多项式算法 也不知道它的复杂性 故下面 我们用遗传算法对问题在2 聪 卜 2 情形求最优解或近似最优解 2 2 2 遗传算法设计 由于遗传算法固有的全局搜索与收敛特性 一般说来 从理论上能以概率1 找到最优解 具体到本文的单机分段恶化最小化总和加权完工时间排序问题 提 出遗传算法如下 给定任一代种群的个体数量 给定复制概率P c 交叉概率为P e 和变异概 率为P i n 其中P e P c P m l 且P c N P c N 偶数 P m N 都是整数 我们用记号 f i 如 表示1 靠的一个排列 用 i l f 2 胡表示一个排序 1 编码设辆 玩 柚是一个 元排列 它对应种群的一个个体 染色垂蛉 分别将 f i 如 妨和 l 坛 柚按L W 和W S P T 重新排列 褥到的合成捧列就 是该个体所对应的L W W S P T 排序 记为o i l 2 一 柚 2 初始种群的选取将工件集饥 也 Z 分掰按L W 规则和按 针对胪口 加工时间依藏开工时问的捧序目愿第二章单机分段恶化捧序问题 嘞的 W S P T 规则捧列 得两个初始捧列s 1 和s 2 这里不妨设S I 1 2 田 即W l 耽 对于产l 2 从S 1 中取t 1 r 件J 协 矗l 爿 构成工件集儡 其中 满足扣1 十 万 其余工件按W S P T 规则 与s 2 中相同的 顺序 挥列 构成工件集眉 合成所得的捧列构成初始种群的一个个体 显然 初始的每个个体已符合L W W S P T 捧序 无须重新排列 3 适应值计算对于一个个体烈曲 卢l 2 朋 其中h 表示代数 初始代 o 设擀O l 2 硒 定义该个体的适应函数K 蝴为排序仃 f l 2 妨 的目标函数值 即 w 栅 哟 2 1 l I 4 算子操作 将当前群体中的个体按适应值从小到大排列 记为兀 耳中个体划分成三部分 适应值最小的前P c N 个个体 适应值居中的P e 个个体 和适应值最大的后P m N 个个体 复制算子复制过程的目的是为了从当前群体中选出优良的个体 使其有机 会作为父代将其优良的基因信息传递给下一代 个体优良与否与各自的适应值有 关 选取兀中前 适应值最小的 P c I 个个体进行复制 交叉算子选取兀中适应值居中的中问P c 偶数 个个体顺序配对进行交 叉 1 设P l 和P 2 是配成对的两个父代个体 设两者中第一位不相同的基因编码 分黜为i 帮j 2 对于父代染色体P 1 0 2 将从首位基因到基因式力的子调度块及基因灭砂 赋予到后代染色体o c 2 的相应位置中 并将这些基因在两个父代个体中的位置 均用一l 取代 3 将父代个体P 2 P 1 中不为一1 的基因通过从左到右扫描 依次填入到后代 染色体C l C 2 的空余位置中 例1 以 9 七 3 L W 1 2 3 6 4 9 7 5 8 W S P T 5 4 8 9 1 2 6 3 7 父代P I 12 3 4 5 6 789 玎 12 3 4 5 6 7 89 L 2 3 5 4 8 9 6 乃 父代P 2 285 l3 4 6 79 o r 2 8 5 13 4 6 79 2 5 8 4 9 1 6 3 7 6 加工时间依赣开工时间的排序问题第二章单机分段罂化捧序问题 中间执行过程如下 后代C I 12 拳 幸牛 宰宰 父代P I 1 13 4 5 67 89 后代C 2 2 奉拳l 事拳术叼父代P 2 l8 5 134 6 79 结果 后代C I 12 85 3 4 6 79 o 128 53 4 6 79 l 2 8 5 4 9 6 3 7 后代C 2 2 3 4 156 7 89 盯 2 3 4 l5 6 7 89 2 3 4 5 8 9 l 6 刀 变异算子选取丌中后 适应值最大的 P m N 个体 依次对每一个父代个体 分别从1 七和加以中随机各取一个数 i 和办然后交换父代个体中位置i 和 上 的基因编码得到新的个体 5 演化迭代给定预定迭代次数N m a x 如果当前迭代次数h l 记 死2 强1w l J r 2 一l 如一 占 2 川 若I 霸I 后彳 则包含该节点部分排序的排序不存在 故下面假定I 乃I 巧 记 厶 2 厶2 岫 则 J q 是乃中权 最大 的坷个工件 且 w O 设 死2 厶 J I 2 0 厶 2 曩l 西惕 j n J 尹l J 2 5 并且 其中J 巾l 五是死中权坳最小的 卜州个工件 记 驴彻2 似I 归w I J J j 巧延功 2 D 若l 马l l 憨 卜七 邓I 霸1 k i 则将死的工件按W S P T 规则排列构成工件集岛 便获得对应此部分排序的排序 故现在假定I 乃I 坷 记 乃是死中惩罚时间b t 最小的 卜扣l 乃I 工件所构成的集合 令T 5 T 4 U 7 3 设T 5 2 气 并且 H 记4 口 墨2 魄 2 7 l j l k t 吐札t k l l t 珏 i 1 邑 缸 口 壹加 4 垦 1 4 2 8 引理2 4 设旬 晚 c 捆 矾 而 如 彳l 如 鲥是 1 2 哟的任一捧列 则 碱 啦 I I I 1 证明若 i I i 2 枷 l 2 叫 那么存在1 m 一1 使磊 叱 我们交换 与 得到p l j 2 1 则有 c 吒 q 噍 a 引理2 5 设旬 c 2 C m 巩 吨 4 日 一l 磊 1 0 加工时间依藏开工时问的捧序目题第二章单机分段恶化捧序向题 k 子妨 矗 噍 那么 由引理2 4 I r 岛噍 q 噍 面 白噍 W l I k l l k r l 再将 i l 2 k 矗 l 2 1 重新排列成 i l 2 k 蠡 l i h m k 使嚷 d 1 噍 如 噍 d 0 本岍1 噍 一而 那 么 窆c 吮 杰c 噍 壹q 钆 妻q 西 lI k r l埘I k r I 引理2 6 设n Q 西 晚 如 h a h 2 J j l 和幻t 啦 g d 是 1 2 砷的任意两个排列 则 杰 吒 I 气 杰 气 艺吒 宝 面 圭q 杰以 芝西 l dt t Il I It It II t I2 证明首先将 g l q 2 铂 重新排列成 l 2 州 那么 由 气 气 t lt I 及引理2 4 得到 1 矗 气 西 c k 西 l吐t 1I It Il dk 再将昕l 1 1 2 k 1 重新排列成 1 2 埘 那么 由Z a 西 1 1 4 I 2 9 加工时间依赣开工时甸的捧序问题 第二章单机分段恶化捧序问题 喀及引理2 4 得到 J 膏 q 珥 q 珥 定理2 7 设口 i l 屯 如扣I 柚是包含部分排序 f l 屯 扔 的任一捧序 j k j 则 的总和加权完工时间 腹o 具有下界疽 f l 红 缸 I 即 贝a 觚i l 匕 缸 1 其中 乃由式 2 4 给出 证明设盯 p I 2 如如l k I 明 我们证一 参口 垦 其中 A 口由式 2 3 定义 4 垦由式 2 7 给出 由定理2 1 要得到包含该节点部分捧序的 满足L W W S P I 规则的 排序 排在从第一1 到第 i 位置上的工件气 应满足 由于咻l W 1 2 坼 岷 l 嗍 A a 帆 I j l 毗 1 啊l 卅咖雕扩K h l 咻l k r s J W k s j 1 w s k j i H l 州 砂吲 那么由引理2 5 可得 4 丞 由 K 及 的选取 以及K 和 并 且 垦 魄 那么由引理2 6 可得 占 口 2 2 4 算例 设有问题lf 历 4O r 呐 d I 0 的一个实例 其参数如表2 1 所示 表2 2 给出最优排序及最优值 图2 1 给出了分支定界过程 表2 1n 7 口 1 0 d 2 7 i I 西缸卜l 3 l O 加工时间依藏开工时问的捧序问题 第二章单机分段恶化捧序闯愿 工件号 l23 4 567 l O 3 9O 3 80 3 7O 3 6O 3 50 3 5O 3 4 易 1 82 3 1 61 73 0 3 22 7 1 0 0 3 9 2 83 8 3 33 耽63 6 忍73 5 4 03 5 4 23 4 3 7 口 屯 1 3 9 1 1 6 1 4 2 1 3 3 o 8 8 铂 8 3 o 9 2 I 扛L J 1 2 3 4 5 6 7 W S P T 4 3 1 4 2 7 5 6 匆个 3 4 1 2 7 5 6 如下是部分计算情况 虹D a 1 w t 2 w 2 3 w 3 4 w 4 5 w f t 6 w e 7 w T w 4 w r 时加M r 渤 6 曲1 竹O a 加I P 6 2 U o 纠 T I T f f i J 1 0 1 3 9 2 3 8 3 3 7 4 3 6 5 3 5 6 3 5 7 3 4 3 6 1 6 3 5 1 6 1 7 3 5 1 6 1 7 l 鲈 3 4 1 6 1 7 1 8 2 3 1 5 9 6 2 专继续分支 疽窿 n a 1 w 2 2 w 3 3 w 一 4 w l 5 w f t 6 w 6 7 w T w l 0 b 岵 b 3 b J w 6 忖6 6 1 叩 6 r 加 a 的 产l Z 与 以 乃 6 b 斥 I O 3 8 2 3 7 3 3 6 4 3 9 5 3 5 6 3 5 7 3 4 3 9 1 6 3 5 0 6 2 7 3 5 1 6 1 7 1 8 p 3 4 1 6 1 7 1 8 2 7 1 6 2 0 6 斗继续分支 苁 2 5 6 3 2 4 7 a 1 w 2 2 w r 3 w e 4 w 3 S w l 6 w 4 T w T w 3 南 w r b 3 b O w 4 b b l b w 7 b 3 b I b b T 2 0 1 3 8 2 3 5 3 3 5 4 3 7 5 3 9 6 3 6 7 3 4 3 7 1 6 3 9 2 6 1 8 3 6 1 6 1 8 1 7 3 4 1 6 1 8 1 7 2 7 产 鲻蝤最优解及最优值 缸 5 Pa 1 w l 2 w 加W 6 4 W 2 5 W 3 6 W 4 7 w T 卸吃 渤卜岫 b 3 b 4 h 4 3 b 4 b O w 7 b 3 b 4 b z b T j 2 T J 五历 T z 妊 磊 l O 1 3 9 2 3 5 3 3 5 4 3 8 5 3 7 6 3 6 7 3 4 3 8 0 6 3 7 1 6 1 7 3 6 1 6 1 7 2 3 3 4 1 6 1 7 2 3 2 7 爿 垒 才 l 鲢 竖剪支 表2 2计算结果 I 最优排序 2 5 6 3 1 4 川 l 最优值 1 6 5 0 6 加工时问依赖开工时间的捧序惩匿 第二章单机分段恶化捧序目愿 图2 1 分支定界法算例 2 2 5 计算实验 给定张 取实数岣 o l 脯确到o 0 0 口 2 0 2 5 3 0 整数匆 5 1 5 取定整数d 使 i 2 3 4 5 b 口J 1 得到分支定界法的平均运行时间 对每 种情形均运行至少2 0 次1 如表2 3 加工时间依赣开工时问的捧序目题第二章单机分段恶化捧序向恿 k2345 撑 1 5 1 1 1 2 3 4 4 0 2 0 l l2 0 7 1 84 3 4 5 3 2 5 l1 4 5 3 l6 6 9 5 3 2 9 3 8 7 4 3 0 l3 3 7 9 83 7 2 4 6 93 6 1 9 2 0 5 3 5 l7 0 2 6 41 2 0 5 6 2 6 6 0 0 4 0 l1 3 8 4 2 l5 0 8 2 7 3 3 6 0 0 5 01 4 4 8 34 0 9 8 1 3 6 0 0 6 0 0 6 02 4 1 8 91 0 1 7 9 2 3 6 0 0 6 0 0 7 03 7 9 8 42 3 8 2 4 2 0 6 0 0 6 0 0 8 05 5 0 7 85 8 1 2 7 5 0 6 0 0 6 0 0 当工件数以较小时伽 2 0 时 对任意的七 2 3 疗 2 分支定界法都能很快 求出最优解 当工件数一适度大 2 0 胛 4 0 并且2 七 4 时 分支定界法能在一 定时间内求出最优解 当工件数疗较大时 珂 1 由于时间和空间的消耗量都很 大 很难用分支定界法求出最优解 对于表2 3 中涉及的数据所傲的相同实验 本文给出的遗传算法 迭代次数 N m a x 3 0 种群规模N 2 0 用m a t l a b 语言编写 在P e n t i u m l V 2 5 6 M B 内存的P C 机上进行计算实验 都很快地 平均运行时间 1 秒 求出了近似最优解 最优解率达 到9 7 以上 对于较大的每个以伟l 括任意 2 3 2 至少针对2 0 个算例 遗传算法求得近似最优解的运行时间由表2 4 给出 表格2 4 遗传算法的平均运行时间 秒 工件数弹 平均运行时间 s 标准差 s 5 00 5 2 60 0 2 6 1 0 00 8 1 0O 0 0 3 1 2 01 0 6 60 0 5 7 1 5 01 4 3 9O 1 6 4 2 0 01 6 5 5O 4 从表2 3 和表2 A 可知 本文所给的遗传算法对于该类问题的求解是很有效的 加工时问依藏开工时问的排序问题 第三章带资源约束的单机番化捧序闯履 第三章带有资源约束的单机恶化排序问题 3 1 引言 带资源约束的排序问题和恶化 加工时间随开工时问增加 排序闯题都是比较 复杂的现代捧序问题 受到许多学者的关注 1 8 1 2 带资源约束的排序问题在加 工工件时 除需要处理机以外 还需要附加资源 资源分y 口 r 再生的 r e n e w a b l e 和不可再生的 n o l a e n e w a b l e 可再生资源在被使用它的任务释放后还可以再次被 使用 而不可再生资源一旦被某个任务使用 以后不再能分配给其他任务使用 从可分性角度来说 资源又分为离散的 d i s c r e t e l y d i v i s i b l e 和连续的 c o n t i n u o u s d i v i s i b l c 研究资源约束排序问题的文章有1 8 9 1 2 恶化排序问题研 究加工时间随开工时间的推移不断增加的捧序问题 l 1 0 l l 骨前将资源约束与恶 化情况结合在一起讨论的排序f 目题尚未见文章发表 本章考虑带资源约束的单机 恶化捧序问题 3 2 带资源约束的单机恶化排序问题 这里的资源指的是只有一种 不可再生的 连续资源 以下我们总假定加工不 可中断 加工时间既是开工时间的线性增函数也是资源的线性减函数 问题可描 述如下 设有一个工件 以 J l 需要在一台机器上加工 每个工件J 的加工时间 易可表示成 1 p f b f a 她j 或 2 玎呵畅分 卿 其中争是待确定的工件4 的开始 加工时间 D 2 幻 o 吩是待确定的分配给工件西的资源量 o 鱼庐蟠巧 b 鸳 巧 吼 o 电f 是已知参数 鸳和 分别是资源分配量的下限和上限 并且不妨总假 定资源分配量的下限鸳就是0 j i 2 9 0 0 9 撑 吩 D 痧是资源的总量 用三参 i 数表示法 本问题可记为1I P j Iy 其中臃示工件加工的要求 限制等内容 y 表示目标函数 用z 口l 忽 列表示某个给定排序的工件的下标排列 Z 是所有下标排列的集 合 即一阶排列的集合 满足资源约束的资源分配向量记为印气甜l 蚝 址矿表示 1 4 加工时问依藏开工时问的捧序目题第三章带瓷源约束的单机恶化捧序向量 最优排序的下标排列 矿表示最优资源分配向量 则 一 称为问题的最优解 3 2 1 问题1I 厅 芒 务一a j u j 叶 DIc k 本节我们讨论问题 1 I 驴锄一a j u j 哟s 疗Ic k 1 对于一个给定的加工顺序 如下算法可以找出口1 相应该顺序的最优资源分配 向量 设庐 z b z z 列是任一给定的下标捧歹J J 算法3 2 h 1 令J 厶 厶 艺 2o 产l 2 2 找一个孙使气 1 2 m a x 气 1 I E J J t I 件1 3 置畦 m i n 瓦 D D 产O u J 一 厶 4 如果y o R O 0 转 2 否则置口 气 一 球 算法终止 定理3 2 1 算法3 2 1 得到的口 材 甜 群 是对应于下标排列z 的最优资源 分配 证嚼为了叙述方便 不失一般性 设下标捧歹 j 乒扛l 忽 硝 1 1 2 州 于是 由M o s h e i o v 1 9 9 4 5 可知 p l 6 l l 矿 a l u l C 1 2 1 b 1 t o a l t l 妒幻c I a 2 u 2 1 6 2 G a a u 2 1 2 1 b 1 t o 1 十6 0a f t l 晚l 乜 p 3 b 3 C rn 3 勰 C f 1 6 3 c 2 一a 3 u 3 5 r o 兀 1 幼一 1 b 3 1 b 2 a l u l 1 b 3 a 2 u 2 a 3 u 3 加工时间依赖开工时问的捧序目愿 第三章带资源约束的单机密化排序闯恿 易尸6 d l 一锄竭 c 产t o l 1 幼一 岛辑1 I 1 屯 3 2 1 I J I 其中G 即最大完工时间G 为使式 3 2 1 在形式上保持一致性 这里视 H n 1 屯 2 l 在下标接列 给定的情况下 由式 3 2 1 可知 按算法3 2 1 所选择 H 的q 1 屯 最大的工件优先分配资源可使目标函数值达到最小 口 算法3 2 1 是对给定的下标掉列z 求得一个最优的资源分配 但由于集合Z 的 基数是刀I 穷举求出最优下标捧列矿是不可取的 在不知问题的复杂度下 如何 尽快地求出问m t q 1 的一个近似最优下标排列就成为人们关心的事情 我们将构造 一个下降算法求问题口1 的一个近似最优下标排列 在介绍这个算法之前 先给出 以下概念 定义3 2 1 设z 2 2 z l E Z 矿是对应于排列一的最优资源分配 记 a 2 警 产l 2 露 若a i 2 狐c 鲻称产为问题 P 1 的稳定点 定理3 2 2 稳定点是最优解的必要条件 证明设矿是最优解对应的下标排列 矿是对应于矿的最优资源分配 则一定 有a i 孤 翘 否则 设存在相邻的两下标i 东l 1 鲐硼 使a o t s 交 换z 和不 的位置 得到一个新的下标排列矿 设 对应的最优资源分配为矿 由于矿也是z t 的一个资源分配 不一定是z 对应的最优资源分配 设矿 H 对应的目标函数为c m 如 口 那么由式 3 2 1 有 矿户幻 1 十 一否 乞甜毒脚 吆 一口 k 赢 1 墨 1 气 一勺吒 兀 1 一 魄 H I 1 h 1i I 1 3 k l l 1 6 加工对问依鞍开工时何的捧序同置第三章带瓷潭约束的单机器化捧序目置 c 删 户如珥 1 6 1 一丢魄 弓珊 一勺 1 思 1 里 1 一磊 熙 1 从而有c 柚 矿 sc 锄 铲 4 疗的情况 虽然上述的 不一定是最优排列 却可作为如下算法的 川 初始点 算法3 1 2 2 1 把下标按q 尸 等的递减序得到的排列z o 作为初始点 惫卸 2 调用算法3 2 1 求相应于 的最优资源分配向量矿 3 计弛 警心 刃 4 按瑾z 递减序重新排列得到广1 若少1 算法终止 否则 置肛轴1 转 2 1 7 加工时问依赣开工时间的捧序闯履 第三章带资源约束的单机恶化捧序目愿 由定理3 2 2 证明可知该算法是下降的 即随着算法不断进行 目标函数值是 不断减小的 且从稳定点的定义及算法的终止准则可直接得到算法终止于稳定点 倒3 2 1 考虑问题lI p F b 西 u j 吩s 疗Ic n 其中n 4 t o 3 扩 o 2 O 3 0 4 o 5 b 2 5 1 4 1 6 1 8 i 邓 5 3 5 8 I 4 0 5 记 2 1 也 J 第一次迭代 由于 a 1 5 t 2 a 2 o L s 3 2 伍 l 放初始点为 1 2 3 4 l l O 3 2 8 A r o 3 9 4 A 3 0 4 5 1 4 0 5 蚝o 1 4 醇 5 g 避 5 3 砰 5 9 2 4 a 5 9 4 8 a 2 0 2 a o f f i 3 2 a 4 0 I z 2 3 l 4 1 4 2 0 5 5 1 1 3 0 6 3 1 1 0 2 2 5 4 4 0 5 呓 5 3 以 5 8 l 4 即 5 9 2 4 c 矿产f o 兀 1 动 0 转 2 否则置露 材 一 甜 算法终止 定理3 2 4 对于随匦O 国 算法3 2 3 所得到的脚 鼍甜 是对应于下标 排列 的最优资源分配 证明由C u p t a 0 9 S S 4 可得 p l j l 6 f o a l l i C t 2s l 卜 1 t o a l l i p 2 一s 2 b 2 C t a 2 u 2 C 乒晚 1 1 2 C t a 2 1 2 p 严s 寸b 犯ra 3 u 3 1 6 旷 1 O l a l u I 眈一位眈 c 3 郦矿 1 6 C 卜田蜥 t o 1 3 1 6 2p l 口l 甜I 卜 1 O 心地 妁 a 3 u 3 p n s b n C n i a n u c 乒 0 1 6 y 墨一口j x l 6 H 鲥 t o 1 6 暑 1 6 一 q 坼 1 6 3 2 2 脚1 1 其中G 就是最大完工时间G 当下标排列给定时 式 3 2 2 中关于G 的 等式 右端第一和第二大项均为常数 故由第三大项可知 应将资源优先分配给 1 9 加工时问依藏开工时间的捧序问题第三章带资灞约柬的单机恶化捧序向题 啦 1 6 r 一大的工件 从而可使目标函数值达到最小 证毕 由于在一般情形下 问题 的最优解不易找到 于是针对某些特殊情形 我 们寻找多项式时间算法 定理3 2 5 对于闯题 如果玉js 口 她将工件按再r 哮乃递增序捧列可 得最优下标捧列矿 并且 一 孑 是问题O 2 的最优解 其中虿 l 2 瓦 证明由于主动s D 对任意下标排列包括最优下标排列 显然最优资源分配 向量为 贫 又从式 3 2 2 可知 只需将工件按驴呵瓦递增序捧列即可得最优 捧序从而得相应的最优解 口 定义3 2 2 在问题 中 如果有两个工件以 巧满足 昭毋 a 宜 a j 甄 巧 则称J 资源优先于易记作毋劬 如果问题口2 中任意两个工件都是可比较资源优先性的 则如下算法可求得它 的最优解 定理3 2 6 对于问题口2 若任意两个工件都是可比较资源优先性的 不妨设 茎J 盔 s 厶则矿 l Z h i 是最优下标排列 一 证明将资源按优先顺序依次分配给各工俘 记所得到的资源分配向量为矿 o 则 z 甜 是问题a P 2 的最优解 设 z 矿 是一最优解 其中矿 是最优下标律列 一 是相应的最优资源分配 由算法3 2 1 得 但矿 不符合资源优 先顺序r 即存在两相邻工件以矗I 1 s 的啧 J 以l 即妒跏l 卿 阱I 写 a e a 1 曲广2 2 雅矿坤 口l 1 6 y 卜1 2 卿l 1 柑 a l IO b y 嘶 1 6 广1 a 2 I b n 2 2 以在矿中 由上述两不等式及算法3 2 3 可知 巧 材 俨1 2 卜l 心 力 且 吱 2 矿 惦 3 2 3 下面分三种情况比较c n 矿 矿 与G 矿 的大小 1 矿 珥 盛 易知 西 砺 1 1 4 I 珥 又由妒嚯什i a f a s l 甄 J f l 诅汁l 甄 从而得c 矿 雎 G z 矿 2 矿 巧 略硝 玩 或 巧 胚矿 o 只针对矿 玩 略惦 霸 的情况 事实上 由等式 3 2 3 西 坟 矿 蜗即吒一惦 矿一西知 若砺 茚 l i t l I 加工时间依赖开工时闻的捧序目息第三章带资源约束的单帆恶化捧序问题 证 若甄s 矿 U t i 从而可得G 盥 G 本 矿 3 怄矿 甄 吒 0 或怄盛 矿 o 易知 订 龋 记 矿或茚 矿 畦 u m 由等式 3 2 3 可得C z 脚 e 转 2 否则 停止计算 定理3 2 7 对任意的可行下标肄列 若算法3 2 4 以 o 且c l e 终止算 加工时间依赣开工时问的捧序闯题 第三章带资源约束的单机恶化排序向题 法 问题无可行解 否则算法3 2 4 所得到的矿是对应于Z 的最优资源分配 证明当 彩且G e 终止算法时