（运筹学与控制论专业论文）具共同宽容交货期的交错形式的准时排序问题.pdf

2 0 0 5 年上海大学硕士学位论文 摘要 随着准时生产制( j u s t i n t i m e ) 生产体系的出现，跟工期有关的排序问题受 到研究者越来越多的关注这其中包括关于共同工期或者共同宽容交货期的超前 迟后罚排序问题 本文考虑的是关于共同宽容交货期的下述单机排序问题：在一台机器上加工 n 个工件，机器每次只能加工一个：【件若工件的完工时间在宽容区间之前，则 该工件属于提前完工，就要受到一个同该工件有关，但同超前时间无关的的超前 罚若工件的完工时间在宽容区间之后，则该工件属于迟后完工，相应地受到一个 迟后罚，该迟后罚是工件迟后时间的加权线性函数工件只有在宽容区间内完工 才会免受惩罚如何适当地安排n 个工件的加工顺序，使总的超前迟后罚最小 文中宽容区间大小给定，相应于宽容区间的位置不固定( 非限制性) 和固定( 限 制性) 两种情况进行了讨论，首先通过划分问题证得两者都是n p h a r d 的，然后 根据问题的最优性质，找到了解决问题的动态规划算法该文还考虑了一个宽容 区间大小可变的排序问题，给出了相应的分枝定界算法 算法 关键词：宽容区间，超前迟后，n p h a i d ，动态规划算法，分枝定界 2 0 0 5 年上海大学硕士学位论文 i i a b s t r a c t w i t ht h ea r i s i n go fj u s t i n t i m ep r o d u c t i o ns y s t e m ，t h es c h e d u l i n gp r o b l e m sr e l a t e d t ot h ed u ed a t e sh a v eb e e na t t r a c t e dm o r ea t t e n t i o n i ti n c l u d e st h es c h e d u l i n gp r o b l e m s w i t hb o t he a r l i n e s sa n dt a r d i n e s sp e n a l t yc o r r e s p o n d i n gt oag i v e nc o m m o nd u ed a t eo ra c o m m o nd u ew i n d o w t h i sd i s s e r t a t i o nc o n s i d e r st h ef o l l o w i n gs i n g l em a c h i n es c h e d u l i n gp r o b l e mw i t ha c o n l n l o nd u ew i n d o w t h e r ea r enj o b sn e e dt ob e p r o c e s s e do nt h es a m em a c h i n e ，a n dt h i s m a c h i n ec a np r o c e s s e sa tm o s to n ej o ba ta n yt i m e i fag i v e nj o bi sc o m p l e t e di t sp r o c e s s b e f o r et h ed u ew i n d o w ，t h e nt h i sj o bw i l lb es u f f e r e da l le a r l i n e s sp e n a l t yw h i c ho n l y r e l a t e dt ot h i sg i v e nj o b i fag i v e nj o bi sc o m p l e t e di t sp r o c e s sa f t e rt h ed u ew i n d o w ，t h e n t h i sj o bw i l lb es u f f e r e dat a r d i n e s sp e n a l t yw h i c hi saw e i g h t e dl i n e a rf u n c t i o no fi t st a r d y t i m eo u rs c h e d u l i n gp r o b l e mi st og i v eap r o c e s s i n gs e q u e n c ep r o p e r l yf o rt h e s en j o b s s u c ht h a tt h et o t a lp e n a l t yi sm i n i m i z e d f o rs u c has c h e d u l i n gp r o b l e m ，c o r r e s p o n d i n g t ot h ef o l l o w i n gt w oc a s e s ：t h ew i d t ho ft h ed u ew i n d o wa n dt h es i t eo ft h ed u ew i n d o w a r ea l lg i v e n ；t h ew i d t ho ft h ed u ew i n d o wi sg i v e nb u tt h es i t eo ft h ed u ew i n d o wc a n b es e l e c t e d ，t h i sd i s s e r t a t i o np r o v e sa l lt h e s et w op r o b l e m sa r en p h a r dv i ap a r t i o nf i r s t ， t h e nc o n s t r u c t st h ec o r r e s p o n d i n gd y n a m i cp r o g r a m m i n ga l g o r i t h mf o rt h e m t h i sp a p e r c o n s i d e r sa l s oas c h e d u l i n gp r o b l e mi nw h i c ht h e1 e f te n do ft h ed u ew i n d o wi sf i x e dw h i l e t h er i g h te n dn e e d st ob ed e c i d e d w ec o n s t r u c tab r a n c h - a n d - b o u n da l g o r i t h mf o ri t k e yw o r d s ：c o n t n l o nd u ew i n d o w ，e a r l i n e s s t a r d i n e s s ，n p h a r d ) d y n a m i cp r o - g r a m m i n ga l g o r i t h m ，b r a n c h - a n d b o u n da l g o r i t h m 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究 工作除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已发表或撰写过的研究成果参与同一工作的其他同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意 签名；臧传 日期：象。占6 智 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定， 即：学校有权保留论文及送交论文复印件，允许论文被查阅和 借阅；学校可以公布论文的全部或部分内容 ( 保密的论文在解密后应遵守此规定) 签名：导师签名：日期： 2 0 0 5 年上海大学硕士学位论文 第一章排序问题简介 在本章中，我们首先简单地介绍排序问题的产生背景以及排序问题的实际应 用，接着我们给出了统一的排序问题的表示方法以及求解排序问题的算法，最后 讲到的是排序问题的复杂性 1 1 排序问题的产生背景和应用 2 0 世纪3 0 年代末第二次世界大战爆发，盟国为了对付法西斯德国的空袭， 开始研究如何合理利用雷达这一新问题，它被称之为o p e r a t i o n a lr e s e a r c h ，许国志 先生把它译为运筹学经过半个多世纪的发展，运筹学有了飞速的发展，并且在 发展过程中，形成了许多分支，比如数学规划、图论与网络、排序、排队论、存贮 论、对策论、决策论、可靠性和质量管理等等这些分支的研究在实际生活中发 生了非常重要的作用，它们被广泛地应用到市场销售、生产计划、库存管理、运输 问题、人事管理、计算机和信息系统、工程的优化设计等诸多方面 排序问题，又称为时间表理论，作为运筹学和组合最优化的一个重要分支始 自于上世纪5 0 年代它产生的背景主要是机器制造，后来被广泛应用到计算机系 统、运输调度、生产管理等领域排序的理论和算法在这些领域内都发挥着重要 作用 如一个机械加工车间要加工一批机器零件，每一个零件按照相同的顺序在几 个不同的机床上加工，但每个零件在每个机床上的加工时间可能不同，如何安排加 工顺序才能以最短的时间加工完所有的零件，这是一个流水作业问题；又如一台 计算机的c p u 在任何时候只能执行一个程序，各程序的到达时间是不同的，怎样 调度这些程序才能使c p u 的利用率最高或程序的平均周转时间最短? 这就是一 个单机排序问题；另外如每个程序的到达时间和执行时间事先是不知道的，但随 机到达时间的数学期望、方差等是已知的，这时的目标函数是极小化平均周转时 间的数学期望上述问题就是一个典型的极小化加工全程排序问题；再如出租车 调动中心接受客户定车，备客户往往提供一最早和最迟来车时刻，中心所派车辆 只要在这二时刻之间到达客户都认可，中心对各车辆的分派也是一种排序问题 2 0 0 5 年上海大学硕士学位论文 2 1 2 同本文相关的基本概念和表示方法 排序问题是一类重要的组合最优化问题，它是利用一些处理机、机器或资源， 最优地完成一批给定的任务或者作业在执行这些任务或者作业时需要满足某些 限定条件，如任务的到达时间、完工的限定时间、任务的加工顺序、资源对加工 时间的影响等最优的完成是指使目标函数达到最小，而目标函数通常是对加工 时间的长短、处理机的利用率的描述在排序问题中，处理机的数量和种类、任务 或作业的顺序、到达时间、完工时间、资源的种类和性能等情况是错综复杂的， 很难用精确的数学描述给出一个排序定义在这里，我f f 3 弓l 用沈阳师范大学唐恒 永和赵传立两位老师编写的排序引论【2 8 l 一书中的定义：给定n 个任务的集 合t = 乃，t 2 ，) ，m 个处理机的集合p = ( p l ，p 2 ，f ) ，8 种资源的集合 兄= 韪，嘞，风) ，在一定的条件下，为了完成各项任务，把p 中的处理机和r 中的资源分配给t 中的任务，使某目标函数达到最优因此排序问题基本上是由 处理机的数量、种类、与环境，以及任务或作业的性质和目标函数所组成求解排 序问题时，可以借鉴求解其它组合最优化问题的方法，充分利用排序问题本身的 特殊性质，以确定满足约束条件的最优排序有些排序问题可直接转化成其它的 组合最优化问题求解对排序问题，要尽可能找到空间复杂性和时间复杂性好的 算法在求解过程中主要的步骤有； ( 1 ) 提出和形成问题即要弄清问题的目标，可能的约束，问题的变量以及 有关参数； ( 2 ) 建立模型把问题中可控变量、参数和目标与约束之间的关系用一定 的模型表示出来； ( 3 ) 求解，用各种手段( 数学的方法和算法) 将模型求解解可以是最优 解、满意解、次优解； ( 4 ) 解的检验首先检查求解步骤和程序有无错误，然后检查解是否反映 现实问题 对于还不知道是否有多项式时间算法的排序问题，首先要用复杂性理论进行 分析，看它是否是n p 一困难的，以便知道求解此类问题的难度，为求解提供一些 有益的启发求解这类问题有两种基本方法：一种是用分枝定界法、动态规划等 巧妙的穷举法以求出它的精确最优解，这类算法计算量大，只有对规模较小的问 题才可行；另外一种是求出它的近似解，各种局部搜索法和启发式算法都是很有 效的，这类算法计算最小，并能满足一定的实际需要 排序问题中的处理机可以是一台也可以是多台只有台处理机的排序问题 2 0 0 5 年上海大学硕士学位论文 3 我们称为单( 处理) 机排序问题，否则称为多( 处理) 机排序问题本文考虑的是 单处理机的排序问题文中采用三参数表示法( g r a h m n e ta l ( 1 9 7 9 ) 1 3 ) 在未特 别指明的地方，对所涉及的排序问题采用b a k e r ( 1 9 7 4 ) 4 j 给出的下述基本假设： 【c 1 一组n 个工件的集合t = j 1 ，j 2 ，矗) 在时刻t = 0 可供加工； f c 2 1 每一工件的安装时间独立于序且包含于该工件所需加工时间中； 【c 3 任一工件 t ，i = 1 、2 ，n 所需的加工时间p i 和工件间的优先加工约 束已知； f c 4 1 任一工件 t i = 1 ，2 ，n 一经开始加工，必须不中断地被加工完； f c 5 1 在任意时刻，任一处理机只能加工一个工件； 文中对工件 t ，i = 1 ，2 ，n 还给出了一些其它变量： 也：工件 t ，i = 1 ，2 ，n 的应交工时间； 8 ：工件 t ，t = 1 ，2 ，n 的实际开始加工时间； g ：工件五t ，i = 1 ，2 ，n 的完工时间； 【i 】= 任一给定序中第i 个工件； 易= ( 嘞一9 ) + = m a x 0 ，南一) ；工件乃t ，j = 1 ，2 ，n 的超前； 乃= ( q 一吗) + = m a x 0 ，q 一嘞) ：工件乃t ，j = l ，2 ，n 的延误； e = 0 ：岛 d j ，j ；1 ，2 ，n ) ； 乩： 1 3 , d j 一岛邳， i1 ，d j q o o i x ) 5 10z o l p t ( 1 0 n g e s tp r o c e s s i n gt i m ef i r s t ) 序指所有工件按照加工时间从大到小的顺序 加工； s p t ( s h o r t e s tp r o c e s s i n gt i m ef i r s t ) 序指所有工件按照加工时间从小到大的顺序 加工； 对应于应交工时间向量彳= 【d 。，d 2 ，d ，。) r 及序a 的目标函数记为f ( o ，西文 中出现，( 一、( i ) 的主要形式有： le t l g 7 d5 = ；( 马+ l j ) 其中d j = d v j n 指譬1 ( 下 同) 2 0 0 5 年上海大学硕士学位论文 2 t ，e f l t ：e a ( d 一( 0 ) + + 序( 9 ，一d ) + = ( n 易十口乃) 3 “，( e 1 1 ) ：r ：t j i ( 乃一d i = ( n ，岛+ 弓乃) 4 j e 岛t ：【o j ( d 一 0 ) + + f 乃( c j d ) + 】= ( n j 岛+ 岛i j ) 2 0 0 5 年上海大学硕士学位论文 5 第二章准时生产和宽容交货中的排序问题 自五十年代开始，对工件工期问题的研究涌现了许多成果，本章主要回顾跟 工期有关的两类排序问题的研究成果，这些成果主要集中在两个方面一准时生 产排序问题和宽容交货的排序问题， 2 1 准时生产中的排序问题 多年来对排序问题的研究大多集中在目标函数为正则的即需极小化的目 标函数是工件完工时间的非降函数( b a k e r ，1 9 7 4 ) 【4 】，如加工全程( m a k e s p a n ) ， 平均流程，最大迟后，最大延误，延误工件数等随着准时生产制( j u s t - i n - t i m e ) 的出现，上述目标函数已不能恰当地反映生产一库存一需求间的关系准时生产 制对应的排序问题反映的是工件过早完工如同工件延误工期一样不受鼓励，因此 理想的加工安排应使所有的工件在设定的交货时刻完工日本人首先在生产中贯 彻了这一思想，而目前被广泛接受的定义则是由s c h o n b e r g e r ( 1 9 8 2 ) f 3 0 给出的，其 定义为：“产品和交付的货物准时卖出，部件准时装配成产品，零件准时到达装配 线和所构原材料准时加工成零件”，即从原材料一加工成零件一装配成部件一 装配成产品一销售的每一阶段都需准时完成，这就是j i t 。自七十年代开始，对 j i t 问题的研究已涌现出了许多的成果，这些成果大致可分为两类：一类是对工件 寻找最优应交工时间的同时寻找最优序；另一类是对工件给定的应交工时间寻找 最优序，这类问题往往比前一类困难现介绍其中最简单的两个问题 问题1 为c h e n g ( 1 9 8 7 ) 【6 考虑的如下排序问题： 1 翡1 1 甲i q 一4 其中m a x 指m 斜( 以下同) ，要求是寻找最优d 和最优序使极小化给定的目标函 数c h e n g ( 1 9 8 7 ) 指出任一加工时间最长的工件第一个加工的序均为最优序，最优 值为 ( c i ，d q 1 1 ) 而对上述问题，如果序列给定，则该问题等价于一个线性规划 问题，可以利用线性规划的强对偶性质得相应的最优值d + = i 1 ( q 。1 + q 1 1 ) ，因此上 述问题是多项式可解的，其复杂性为o ( - ) f 以上是对给定目标函数寻找最优d 和 最优序，如果d 给定，只是寻找最优序，即考虑下面的问题： 2 0 0 5 年上海大学硕士学位论文 5 第二章准时生产和宽容交货中的排序问题 自五十年代开始，对工件工期问题的研究涌现了许多成果，本章主要回顾跟 工期有关的两类排序问题的研究成果，这些成果主要集中在两个方面一准时生 产排序问题和宽容交货的排序问题 6 2 1 准时生产中的排序问题 多年来对排序问题的研究大多集中在目标函数为正则的即需极小化的目 标函数是工件完工时间的非降函数( b a k e r ，1 9 7 4 ) 4 】，如加工全程( m a k e s p a n ) ， 平均流程，最大迟后，最大延误，延误工件数等随着准时生产制( j u s t i n t i m e ) 的出现， 二述目标函数已不能恰当地反映生产一库存一需求间的关系准时生产 制对应的排序问题反映的是工件过早完工如同工件延误工期一样不受鼓励，因此 理想的加工安排应使所有的工件在设定的交货时刻完工日本人首先在生产中贯 彻了这一思想，而目前被广泛接受的定义则是由s c h o n b e r g e t ( 1 9 8 2 ) 3 0 给出的，其 定义为；“产品和交付的货物准时卖出，部件准时装配成产品，零件准时到达装配 线和所构原材料准时加工成零件”，即从原材料一加工成零件一装配成部件一 装配成产品一销售的每一阶段都需准时完成，这就是j i t 自七十年代开始，对 j i t 问题的研究已涌现出了许多的成果，这些成果大致可分为两类：一类是对工件 寻找最优应交工时间的同时寻找最优序；另一类是对工件给定的应交工时问寻找 最优序，这类问题往往比前一类困难现介绍其中最简单的两个问题 问题l 为c h e n g ( 1 9 8 7 ) 考虑的如f 排序问题： 其中z n a x 指m “( 以下同) ，要求是寻找最优d 和最优序使极小化给定的目标函 数c h e u g f l 9 8 7 1 指出任一加工时间最长的工件第一个加工的序均为最优序，最优 值为j 1 ( c h ；1 c 1 1 ) 而对上述问题，如果序列给定，则该问题等价于一个线性规划 问题，町以利用线性规划的强对偶性质得相应的最优值矿= 。l4 - c 。 ) 因此上 述问题尾多项式可解的，其复杂性为( ) 以上足对给定目标函数寻找最优d 和 最优序，如吴。给定，只是寻找最优序，即考虑下而的问题： 最优序，如吴c i 给定，只是寻找最优亭，即考虑下面的问题 2 0 0 5 年上海大学硕士学位论文6 可以证明，任一加工时间最长的工件第一个加工的序均为最优序 问题2 为平均绝对偏差( m a d ) 问题 呼：i 岛一d | 1 当d 给定时： k a n e t ( 1 9 8 1 ) 1 8 在d 之m s = p 3 和必须有一个工件在时刻d 完工 两个条件下，给出了一个算法h a l i ( 1 9 8 6 ) 1 4 发现：d m s 时，上面的目标函数 等价于吨n p j ，其中若工件j 在d 前( 包括d ) 完工，z ，表示工件j ( 包括j ) 之前完工工件数；若工件j 在d 之后完工，。j 表示工件j ( 包括j ) 之后完工工件 数对此形式的目标函数，该作者给出了o ( n l o g n ) 算法，最优序的个数可多达2 r 个，若n 为奇数，则r = a 尹；若n 为偶数，则r = ；，且如期完工的工件数b = 引 b a g c h ie ta 1 ( 1 9 8 6 ) 【3 1 3 对问题2 在设工件已预排成p 1sp 2s s i o n 后，令： 1p l + p 3 + + m ，若n 为奇数， ip 2 + 用+ + 肌，若n 为偶数 ， ip l + p 3 + + 骱一1 + p 。， 若n 为偶数， lp 2 + p 4 + 十肌一1 + p 。，若n 为奇数 显然， 口 m s 该文指出当d 口时该问题等价于n 一1 个工件( 去掉加工时问最 长的工件) 相应的p 2 y ，其中户为平均流程，并且给出了最优算法，它也可获相同 于上面的2 个最优解而对sd d ，。) ，n = 1 ，2 ，n ) 此序o - 具有下述四个性质： 性质1 机器连续地加工n 个工件，即q + l = q + 功，助 性质2o - 为v s h a p e d ，其中b 中工件依加工时间的非增序排，a 中工件依 加工时间的非降序排 性质3b 中恰有一个工件在时刻d 完工 性质4i b l = b ，则b 中第b 个工件在时d 完工，且b = 当d d ；如果它在d 1 ，如之间完工，由于延误的工件的罚很大( t 中 任一工件罚口= d ) ，因此只有把所有的工件都排在e 和w 中，才能使总的罚最 少由于宽容区间的大小为d 2 d 1 ，因此e 中工件的完工时间之和一定超过d 。综 上可得，工件 = 2 n + 1 只能在d 1 时刻完工 下面证第二个条件，由于工件五= 2 n + 1 在d 1 时刻完工，其他的工件排在 e ，f l ，w 中，同样因为t 中工件的罚很大( t 中任一工件罚y = d ) 所以只可能把 工件排在e ，w 中，才能使总的罚sd ，所以划分问题有解 定理1 非限制性的宽容交货问题是n p 一困难的 证明：由引理1 和引理2 可得 g a 3 求解该问题的动态规划算法和应用 通过最优性质争t f f l 可以得知：某个工件在d 1 时刻完工；集合t 中的工件按 2 0 0 5 年上海大学硕士学位论文 1 3 照 肌似) 的非降序排列；集合e 中的工件和集合w 中的工件可以按任意序列排 列，而不影响总的罚最优序中有一个工件在d l 时刻完工，那么在d 2 时刻，肯定 会出现下面的情况( 如图3 2 ) ： ( 1 ) 某个工件巩在d 2 时刻开始加工或者在d 2 时刻完工； ( 2 ) 某个工件以在d 2 之前开始加工在d 2 之后完工 ii 口= = 二 = 口 e d 1 w d 2 t ed l w d 2 t e d 1 w d 2 t 图3 2 工件 的三种位置 因此我们可以先从n 个工件中任意拿出一个工件 【k = 1 ，2 ，n ) 分别将该工件 排于从d 2 时刻完工到d 2 时刻开始加工的所有可能位置，即若令a 表示工件 的 完工时间瓯与d 2 偏差，则a = 0 ，1 ，p k 而余下的n 一1 个工件按 p t 肥) 非降序 依次排于工件 的两边具体化即得下述动态规划算法i 动态规划算法i ： 假设工件 已取定，余下的r - 1 个工件按 p i 肥) 的非降序排列为工件1 ，2 ， 、n 一1 令f k ( j ，t l ，t 2 ) 表示上述非降序的前j 个工件和工件。如排成的最优序所得 的目标值在此最优序中，令t 。表示区间【d 1 ，d 2 中已排的加工量，t 2 表示t 中最 后一个工件的完工时间跟d 2 的偏差( 如图3 3 ) ， 图33 动态规划算法i 示意图 显然舟= l2 j = 1 2 、n 1 ( t l d = d 2 一d 1 0 t 2 茎t p 初始条件 2 0 0 5 年上海大学硕士学位论文1 4 , 3 k a ，如果t 1 = m 一。t 2 = o ，其中n = p k m i n p k ，d ，p + 。其他 f k ( j ，t 1 ，t 2 ) = + c o ，惫= 1 ，2 ，忆，j = 1 ，2 ，n 一1 ，t 1 0 或0 2 0 递推公式： f k ( j ：_ 1 浍, h , 裂t 2 ) + a j 堋。 詹= l ，2 ， ，n ，j = l ，2 ，n l ，t 1 = 0 ，l ， 上) ，t 2 = l ，2 ，1 p 最优解 z = m i n f 8 ( n 一1 ，t l ，2 ) ；= 1 ，2 ，n ，0 1 = o ，1 ，d ，t 2 = 1 ，2 ，t p 在递推公式中，括号右边第一个式子把工件 排在集合e 中，第二和第三个 式子分别把工件j ，排在t 中和w 中如果工件被排在集合e 中，则该工件发生 的超前费用为。，；如果工件被排在t 中，则发生的迟后费用为岛0 2 ；工件被排在 w 中，则不增加总的罚( 工件排在w 中时指能遵循性质5 排在w 中) 选定一个工 件以后，把剩下的n 1 个工件全部排完，可以得到一个局部最优解然后比较对 应所有的k = 1 , 2 ，n 所得局部最优解可以得到宽容交货问题的最优解上 述动态规划算法是伪多项式时间算法，算法的复杂性为0 ( n 2 t p d ) ，因此非限制 性的宽容交货问题是一般意义上n p 一困难的 u e t w 问题的动态规划算法应用 某工厂接受一批订单，客户要求在一台机器上加工四个工件j i = 1 ，2 ，3 ，4 ， 工件的加工时间向量为( 2 ，1 ，2 ，3 ) ，客户要求接收货物的最迟交货时间和最早交 货时间不能超过三个单位时间，即d = d 2 一d 1 = 3 ，四个工件的超前罚系数向量为 ( 1 3 2 、2 ) 、迟后罚系数向量为( 2 2 3 ，4 ) ，问工厂应该如何适当地安排四个工件 的加工顺序才能使总的超前迟后费用最小? 现用上述动态规划算法i 求解该问题首先我们把四个工件按照协岛) 的非 降顺序排列，由于p l ：j 1 = 1 ，p 2 , j 2 = j 1 、p 3 岛= ；p 4 五= ；，所以我们得到 2 0 0 5 年上海大学硕士学位论文1 5 根据上面的算法，从四个工件中任意选定了一个工件以排在从d 。时刻完工到d 。 时刻开始加工的所有可能位置之后，就可以把剩下的三个工件按照上面的顺序依 次排在工件以的两侧现用疗( j ，t l , t 2 ) 表示把第i 个工件排在所有可能位置上后， 接着排完了前j 个工件之后的当前最优值函数，而t 1 ，t 2 含义同前 ( 1 ) 首先选定把第一个工件 排在所有可能的位置上，然后把剩下的工件按 照 p 。肥) 的非降顺序排列在工件j ，的左右两侧 s t e p1 ： 假定工件 在d 2 之后的加工时间为a ( o n 2 ) ( 如图3 4 ) ，则当前发生的 超前迟后费用为 片( 0 ，2 一a ，a ) = 口l a = 2 a i j t 图3 , 4 s t e p2 ： 要把工件也排在工件以的左侧或者右侧由已知得：p 2 = 1 ，2 = 3 ，恳：2 ， 如果把工件j 2 排在工件j 1 的左侧，即工件如的完工时间在宽容区间内，这时工 件山不会造成任何费用的增加，因此 但是如果把工件如排在工件j 1 的右侧，肯定会发生迟后的违约费用，所以我们 选择把工件也排在工件j 。的左侧 s t e p3 ： 下面把工件也排在序列中p 3 = 2 ，3 = 2 ，岛= 3 、把工件如排在w 中包 括排在d 时完工可以使费用不增，此时总费用为 盯( 2 ，3 ：a ) = 2 a ， s f e u4 ： 最后把工件 排在序列中p 4 = 3 ，岫= 2 ，伪= 4 ，把工件山排在序列的最 虎端，此时总费用为 2 0 0 5 年上海大学硕士学位论文1 6 如果把工件排在序列的最右端，则总费用为 ，( 3 ，3 ，n + 3 ) = 2 a + 4 ( 3 + a ) = 6 n + 1 2 所以当a = 0 时，总费用都为 疗( 3 ，3 ，0 ) = 2 因此我们可以得到工件 第一个排时最优值大小为 ，：( 3 ，3 ，0 ) = 2 而工件的加工顺序为( j 4 ，也，如， ) ( 如图3 5 ) ，最早交货工期d 一5 ew t d l = 5d 2 = 8 图3 5 ( 2 ) 现在考虑把第二个工件也排在从d 2 完工到d 2 开始加工的所有可能的位置 上，然后把剩下的工件按照 p 屈) 的非降顺序排列在工件如的左右两侧 s t e p1 ： 由已知得p 2 = 1 ，“2 = 3 ，阮= 2 ，假定工件也在d 2 之后的加工时间为 a ( o 兰a 1 ) 、则当前发生的超前迟后费用为 尼( 0 1 一a ，a ) = 口2 0 = 2 a s t e p2 ： 要把工件，3 排在工件j 2 的左侧或者右侧由已知得：p 3 = 2 ，n 3 = 2 卢3 = 3 ， 如果把工件也排在工件也的左侧，这时不管工件如的位置如何，工件如完全在 宽容区间内加工，此时1 = 3 n ，t 2 一n ，则总费用为 如果把工件j i 排在：i ：件如的右侧，此时t 1 = l n ，t z = 2 + n 、则序列发生的超前 迟后费用为： 止( 1 1 一“+ 2j = 矗( ( ) 1 一n ，n ) + “3 ( n + 2 ) = 2 a + 3e n + 2 ) = 6 n + o 2 0 0 5 年上海大学硕士学位论文1 7 显然排定工件也后发生的总费用的最小值可以表示为 龙( 1 ，3 一n ，a ) = 2 a s t e p3 ： 下面把工件 排在序列中p 4 = 3 ，。4 = 2 ，阮= 4 ，因为工件 和j 2 的加工 时间之和正好等于宽容区间的长度所以工件 如果排在最左端则至少可以在d 。 时刻完工，而且并不会使总的费用增加， 尼( 2 ，3 ，1 2 ) = 尼( 1 ，3 一n ，口) = 2 a s t e p4 ： 最后要把工件 排进序列中，p l = 2 ，“1 = 1 ，角= 2 ，工件t ，l 既可以排在序 列的最左端，也可以排在序列的最右端如果排在五之前，此时h ：3 ，t 。：n ，则 发生的费用为 ，2 ( 3 ，3 ，o ) = 尼( 2 ，3 ，n ) + l = 2 a + i ， 如果排在也之后，则发生的费用为 ，2 ( 3 ，3 ，十2 ) = ，主( 2 ，3 ，n ) + 2 ( o + 2 ) = 4 a + 4 比较上述两式，取疗( 3 ，3 ，n ) = 2 a + 1 ，并且当o = 0 时龙( 3 ，3 ，o ) = 1 因此我们可以得到工件如第一个排时最优值大小为 艿( 3 ，3 ，4 ) = 1 工件的加工顺序为( ， ，五，如) ( 如图3 6 ) 1 最早交货工期d 1 ew d l = 5d 2 = 8 图36 ( 3 ) 同样的方法，我们可以得到把工件如第一个排时的最优值的表达式为 当“= 二= 0 时，最优值为艿( 3 3 o ) = 1 工件的加工顺序为( ，1 扎如如) ( 如图 蔓7 ) 最早交货工期d t = 5 2 0 0 5 年上海大学硕士学位论文1 8 ewt i j 1j 4j 2j 3 d 1 = 5d z = 8 图3 7 ( 4 ) 当工件山第一个排时目标函数的表达式为 f z ( 3 ，3 ，a ) = 4 a + 1 ， 疗( 3 ，3 ，a ) = 4 a + 3 ， 片( 3 ，3 ，。十2 ) = 6 a 十4 ， 疗( 3 ，3 ，a + 2 ) = 6 a + 6 ， 排在如左侧， j 1 排在如左侧， 排在如右侧， 以排在如右侧， 当a 1 时，取a = 1 可以极小化最优值表达式，最优值为 艿( 3 ，3 ，1 ) = 5 ， a l 时，取a = 0 可以极小化最优值表达式， 疗( 3 3 ，0 ) = 3 ， 因此我们可以得到工件 第一个排时最优值大小为 艿( 3 ，3 ，0 ) = 3 工件的加工顺序为( j 1 ，山如，j 4 ) e ( 如图3 8 ) 最早交货工期d 1 = 5 wt j 1j 3 i j 2j 4 d l = 5d 2 = 8 图3 8 综合上述所有步骤可得按照( j - ，。，3 ，如) 或者( j 1 ， 、j 2 ，也) 的顺序加工四个 工件可以使总的费用最大小为戌( 3 3 、o ) = 矗( 3 ，3 、0 ) = l 最早交货工期d 1 = 5 赞 例结束 2 0 0 5 年上海大学硕士学位论文 第四章限制性宽容交货问题 本章介绍的是限制性宽容交货排序问题，给出了它的一些性质并给予证明， 考虑了该问题的复杂性在第二节中，我们给出了求解该问题的动态规划算法和 一个算例 4 1 限制性的宽容交货问题基本情况和n p h a r d 的证明 限制性的宽容交货问题( r e t ) 指的是针对同样的目标函数 n ，= 【。 咖1 一o ) + a m a x o ，c i d 2 ) t = 1 但宽容区间的大小d 以及最早交货工期d 都是预先给定的，因而d 2 也是确定的 问题是在这种情况下，如何适当安排工件的加工顺序才能使得目标函数极小化? 限制性的宽容交货问题具有跟非限制性宽容交货问题类似的一些性质： 性质1 对问题r e 丁1 w ，存在一最优序，机器加工任何两个工件之间都没有 空转发生 性质2 对问题r e t w ，存在着一个最优序，其中某个工件在d 1 时刻开始 加工或完工或者第一个工件从零时刻开始加工 。| 生质3 集合t 中的工件按照 仇风) 的非降序排列为最优 性质4 集合e 中的工件可以按任意序列排列