（运筹学与控制论专业论文）特殊并行工件排序的研究.pdf

浙江大学硕士学位论文 摘要 本文研究的是两个特殊情况的在线( o v e rl i s t ) 并行工件排序，目标是最 大完工时间最小。并行工件排序与一般平行机排序问题的工件不同之处在于， 一个工件可能需要若干台机器同时对其加工。工件一个一个到达，只有在工件 到达后，它需要的机器数目和加工时间才是已知的，而且工件一旦到达，就必 须立即给其安排加工。 第一章是绪论部分，主要介绍排序，并行工件排序，近似算法和竞争比分 析等基本知识。 第二章主要研究了工件按尺寸非增的顺序到达的并行工件排序，第一节介 绍了该问题的贪婪算法( l s ) ，即安排工件在尽可能早的时刻，算法的竞争比 上界是等，竞争比下界是詈。第二节给出了一个改进的贪婪算法，竞争比不超 肌孚。 第三章主要研究了工件按加工时间非增的顺序到达的贪婪算法( l s ) ，证 明了算法的上界至多是2 。 关键词：并行工件在线排序算法设计与分析竞争比分析 浙江大学硕士学位论文 a b s t r a c t t h i st h e s i sm a i n l yc o n c e r i l sd e s i g na n da n a l y s i so fa p p r o x i m a t i o na i g o r i t h m so n t w os p e c i a lp a r a l l e lj o b ss c h e d u l i n gp r o b l e m s 1 1 1 eg o a li st om i n i m i z et h em a k e s p a n j o b sc o m eo v e rl i s t ap a r a l l e lj o bm a yr e q u k ean u m b e ro fm a c h i n e sf o ri t s p r o c e s s i n ga tt h es a m et i m e u p o na r r i v a lo f a j o b ，i t sp r o c e s s i n gt i m ea n d t h en u m b e r o fr e q u e s t e dm a c h i n e sb e c o m ek n o w n , a n di tm a s tb es c h e d u l e di m m e d i a t e l yw i t h o u t a n yk n o w l e d g eo f f u t u r e j o b s w ef i r s ti n t r o d u c eb a s i cn o t i o n so fs c h e d u l i n gp r o b l e m , a p p r o x i m a t i o n a l g o r i t h m sa n dc o m p e t i t i v ea n a l y s i s i nc h a p t e r2 ，w ed e a lw i t ht h ec a s et h a tj o b sa r r i v ei nn o n i n c r e a s i n go r d e ro f s i z e s f i r s t , w es h o wt h ec o m p e t i t i v er a t i oo fa l g o r i t h mg r e e d yi sa tm o s t ，b u ta t 斗 c l e a s t - j i nt h es e c o n dp a r t ，w es h o w a ni m p r o v e dg r e e d ya l g o r i t h mh a sae o m p e t r i v e 二 r a t i o o fa t m o s t1 + 掣。 z i nc h a p t e r3 ，w ea s s u l n et h a tj o b sa r r i v ei nn o n i n c r e a s i n go r d e ro fp r o c e s s i n g t i m e s w eo b t a i na nu p p e rb o u n do f2b ye m p l o y i n gag r e e d ya l g o r i t h m , w h i c h s c h e d u l e s j o b sa se a r l ya sp o s s i b l e k e y w o r d s ：p a r a l l e lj o b ，o n l i n es c h e d u l i n g , d e s i g na n da n a l y s i so fa l g o r i t h m ， c o m p e t i t i v ea n a l y s i s n 一 浙江大学硕士学位论文 1 1 排序问题 第1 章绪论 排序问题( s c h e d u l i n gp r o b l e m s ) 是研究在满足一定的约束条件下，如何安排 有限的资源以达到某种意义下最优结果的问题，广泛地应用于生产实践的多个 领域，有丰富的实际背景和重要的理论意义，是组合优化问题中重要的一类分 支。虽然这一领域的工作只是在2 0 世纪5 0 年代初期才开始，但有关的文献在 数量上却多得惊人。由于它的应用范围逐渐扩大，新的的问题、新的模型 不断出现，因而从事这一领域研究的入与日俱增，其内容也越来越丰富，应用 也越来越广泛。 在排序问题中，如果说所有的数据在进行决策之前都是己知的，排序问题 称为确定性排序问题。如果有的数据，例如加工时间、准备时间和工期等，在 做决策时是未知的，它们是一些随机变量，这样的排序问题称为随机排序问题。 我们一般讨论的都是确定性的排序问题。为了叙述简便，人们使用了一些简便 的描述排序问题的记号。下面所使用的记法来自【1 】： 我们一般把要完成的任务称为工件，把完成任务需要的资源称为机器。设 有”个给定的工件- i , ，以要在朋台机器m i ，m 。上加工，每个工件对应一个 加工时间p ，每一m 在任一时刻只能处理一个工件，第j 个工件的完工时间 用来c 表示。一般情况下工件的加工要受到某些给定条件的限制，例如工件的 发放时间( 即开始送到指定机器上加工的时间) ，必须交货的时间( 即工件必须 加工完毕的最后期限) ，工件之间由于工艺上的需要必须一次完成( 即不能中 断) ，而在某些情况下则允许在加工过程中可以中断，转为加工别的工件，之后 再恢复对原来工件的加工；某一工件随其加工时间的长短需要付出一定的费用， 这项费用一般假设是时间的非降函数，等等。现在的问题是要求一种关于工件 满足给定条件的可行排序，使得某种给定的指标达到最优。 由于处理机的数量、类型和环境有多种情况，任务和资源的约束条件更是 错综复杂，再加上度量不同指标的目标函数，生产实际中存在大量的、不同类 型的排序问题。例如一般根据处理机的情况不同可分为单机排序，平行机排序 和车间排序问题，平行机又分为同速机、同类机和不同类机，车间排序分为流 水作业、自由作业和异序作业等。由工件特征可按加工时间、工件间关系以及 是否可中断来划分。根据排序时已知信息的多少可以把排序问题分为离线( o f f l i n e ) 和在线( o nl i n e ) 两类。在离线问题中，所有工件信息都是已知的，而在线问 题中有两条基本假设：其一是工件信息是逐步释放的，排序者在对当前工件进 行安排的时刻，对还未释放的工件信息是不知道的；其二是工件一旦被安排给 某一机器在某一时段加工，则在之后的任何时候都不能改变。排序问题一般的 浙江大学硕士学位论文 优化目标是一个一维数量，记c 纛= m a x c , 表示最大完工时间( 极小化目标) ， 称为m a k e s p a n 。其它的目标函数还有总完工时问，最大延误时间和最大误工时 间，以及加权总完工时间，加权总误工时间等等。 排序问题一般用a p y f 来表示。口、和，分别表示机器数量、机器 情况和零件性能，表示最优准则。例如： 2 f l e m a k e s p a n 表示所讨论的模型具有2 台机器，属于流水作业型，不允许中断，工件之问无 任何先后的加工顺序，目的是要寻求一种排序，使得整个加工过程所耗的时间 最短。 一2 一 浙江大学硕t 学位论文 1 2 算法与竞争比分析 优化问题的算法指的是制定一个执行的程序，对于该问题的任意一个实例 ，按照这个程序进行下去，可得到这个实例的一个解和对应的目标函数值。对 于排序问题的一个算法，按照算法可得到实例的一个可行排序和在此排序下的 目标函数值。设计排序问题的基本思路是应用或借鉴其他组合优化问题的方法， 利用排序问题本身的特殊性质，以确定满足约束条件的最优排序。典型的排序 问题的算法有多项式算法，即已经找到了求解问题的有效算法；启发式算法， 是解决排序理论中某些典型问题的常用方法，这类算法一般来说，其计算量是 指数级的，但在实际应用场合却显缛相当有效；近似算法，是目前解决组合优 化中大量实际问题的主要方法，本文的主要工作就是对某些并行工件排序问题 进行近似算法的设计与分析。经典的在线近似算法有解平行机排序问题的l i s t s c h e d u l i n g 算法( 【4 】，【5 】) ，是按工件到达的顺序依次将它们安抨在能使其最早开 工的机器上加工。 实际上，组合优化中的绝大部分问题都是n p 完备问题，对于这种问题， 从计算量的角度看，不大可能存在有效的求解方法，即所谓的多项式算法，但 这类问题在实际中常会遇到。对于这类问题，虽然一般不可能求到最优解，但 有希望找到某种方法求出它的近似解，近似算法理论所研究的就是要对于一种 给定的算法，一般是简单易行的，估计出由它所产生解与问题真正的最优解所 对应的目标函数值之间的差异程度，因而在某种给定的标准之下，它可以评估 几种给定的算法之间的优劣。 设a 是一个求解极小化目标的最优化问题，i 是这个优化问题的实例，p 是所有实例的全体，a 是求解它的一个算法。对于某个e 0 ，我们称算法a 是 问题a 的占近似算法当且仅当对所有问题a 的例子i ，有 c 。( ，) 一c 胛( ，) c 晰( ，) 其中c 一( ，) 是由算法一得到1 的解的目标函数值，c ”( ，) 是i 的最优值。显然， 占越小，近似算法的精度越高。 由于 c 。( ，) 一c 锻( ，) c 柳( ，)= 高一 = 一一_ c t t i 、 有时用 c 。= i n f c - t i c 。o ) 蔓c c 晰 w p 来衡量近似算法的好坏。c a 是算法的最坏情况界。 一3 一 浙江大学硕士学位论文 对在线问题和在线算法的研究中在最坏情况界的基础上逐渐形成了竞争 比分析( c o m p e t i t i v ea n a l y s i s ) 9 】 r = i i l f 1 1 c 。( ，) r c o p t ( 1 ) ，v i p 为算法的竞争比( c o m p e t i t i v er a t i o ) ，为了表示方便也可能写成 fc 。1 代2 s u p 1 i 万f l lj 如果不存在该问题的竞争比小于c 的在线算法，则称在线问题的竞争比下 界( 1 0 w e rb o u n d ) 为c 。下界可以通过给出一系列的实例使得任何算法都不能很 好地求解它们的全部来得到。竞争比反映了算法a 得到的近似解在最坏情况界 下与最优解的接近程度，下界体现了一个在线问题由于部分信息未知而给求解 带来的困难，这是不依赖算法设计的固有性质，若算法a 的竞争比等于问题的 下界，我们就称a 是最优( o p t i m a l ) 算法，这是从竞争比的意义看一个在线算法 可得到的最好结果。对于极大化问题的最坏情况界和竞争比定义为 c a = i i l f 芒l l c 钾( ，) s c c 。p j r 。= i n f r i c 钟7 ( ，) s ，c 。( ，) w j p j 一4 一 浙江大学硕士学位论文 1 3 并行排序和本文概述 并行工件与一般平行机排序问题的工件不同之处在于，一个工件可能需要 若干台机器同时对其加工。例如在大型数据库系统中，并行处理就是利用多个 c p u 和i o 资源来执行单个数据操作，以加快工作效率。设工件集为j = “， 机器总数为m ，每个工件，就对应两个参数h ，n ) 聊，m ，分别为该工件需 要的机器数目( 称作工件尺寸) 和需要加工的时问，工件在每台机器上的加工 时间均相等。在线的条件下，工件一个一个到达( o v e rl i s t ) ，只有在工件到达 后，它的工件尺寸和加工时间才是已知的，而且工件一旦到达，就必须立即给 其安排加工。下一个工件只有在当前的工件安排后才会到达。目标是最大完工 时间( m a k e s p a n ) 最小，即最后一个完工时间最小。 并行工件排序模型最近被广泛的研究，但在线算法还比较少。并行工件排 序问题类似于二维的矩形装箱问题，并行工件排序可看作是条形装箱。在条形 装箱中，是把有限个矩形条装入一个宽度有限、高度无限的矩形箱中，目标是 极小化箱子装完所有矩形条的最大高度。可把并行工件的尺寸看作是矩形条的 宽，工件的加工时间看作是矩形条的高，箱子的宽看作并行排序的机器总数， 最大完工时间就是装箱后箱子的高度。 在工件有到达时间的在线并行排序问题中，n a r o s k a 和s c h w i e g e l s h o h n 3 1 1 给出了一个l s 的启发式算法，竞争比是2 一二，并证明了该算法是最优的。在 m 这里本文考虑的都是工件一个一个到达( o v e rl i s t ) 的情形，1 9 8 3 年由b a k e r 和s c h w a r t z 【2 】给出了一个s h e l f 算法，在所有的工件加工时间不超过1 的假设 下竞争比为6 9 9 。对于在线条形装箱，b r o w n 等【1 l 】证明了任何在线算法的竞 争比下界是2 。j o h a n n e s 【7 】设计了一个对于任意加工时间的在线算法，竞争比 不超过1 2 ，还举例说明了下界是2 2 5 。 本文研究的是已知一些后续工件信息的两个特殊情形。第二章讨论了工件 按需要机器数目非增的顺序到达的情况，所有工件尺寸都为1 的特殊情形问题 可看作是经典的平行机在线排序问题，现在已知的平行机在线排序的最好的下 c 了= 界和上界分别是1 8 5 3 5 8 和l + 1 三二岩 1 9 2 0 1 ( g o r m l e y 等【8 】，f l e i s c h e r 和 l 上 w ，i l i l 【l q ) 。若工件尺寸不等，贪婪算法的竞争比上界是苎，下界是；。第二 42 雨 节给出了一个改进算法，竞争比为1 十半 x ，b ，d ) 中的任意时刻的机器工作效率不小于詈。 证明用反证法证明，若命题为假，可假设k ，d ) 中存在某个时刻g 的只有少于 詈历台的机器在工作，即g 时刻的空闲机器数大于；研。由算法可知在叠及g 之 后时刻开始加工的工件尺寸一定都是大于；辨的，由于工件尺寸非增，可知在 k 亩开始加工的工件尺寸也是大于；m 的，而在b ，d ) 中加工的工件又都不是特 大工件，算法必可安排两个这样的工件同时加工，这样g 时刻的工作机器数目 将大于；，l ，就出现矛盾。所以，k ，d ) 中任意时刻机器的工作效率都不小于j 2 _ 定理2 1 工件尺寸非增的情况下，l s 算法的竞争比至多是等 证明若d x ，则c 岱x + 肼，c 丛2 c 5 若d 工，设j ，= d 一工，c “= d + p t = z + y + a ；因为从0 到工时刻机器的效 率均不小于1 2 ，再由引理2 1 就可得c j 1x + ；y ； y 三x ，c 4 = z + y + n 三x + 乃等c ； y ；x ，；c 吾x + 吾y = x + y + ：( y 一言x x + - ) - ； 浙江大学硕士学位论文 c ”= z + j ，+ p ，5 三c + 力等c 。 综上，工件尺寸非增的情况下，c c i i i c4 定理2 2 工件尺寸非增的情况下，贪婪算法l s 的竞争比至少是主。 证明构造一个例子，使用贪婪算法排序的完工时间与最优排序完工时间的比 大于等于主a 设七 o ，是一个充分大的正整数，机器总数为珊= 3 2 女，工件总 个数为n = 2 k 一2 ；假设一共有六类工件集合 g l ，g 2 ，g 6 ：g 。： ( 3 一i + ，l l ( 3 一l + 一l ，1 l ，( 3 一l + 1 ，1 ) 共个；g 2 ：( 3 1 ，专 2 个；q ： p 吐爿， 3 2 - - 2 , 1 ) ，p 一川爿共阶q ：h 一) 阶 g ：( 2 ，1 ) 3 个；g ：( 1 ，+ 专) 1 个；工件按g l ，g ，g 。的顺序到达，显 然工件尺寸都是非增的。 下面按贪婪算法对其排序，g 中的个i 件尺寸都大于机器数的一半，只 能依次加工，完工时间为n ；接着是g 2 的两个工件，同时加工，开工时间为n 。 g 1 中的i 件可安排在f 0 ，n 1 与g 的工件同时加i ，g 的第i 个工件 这样在【0 ，】，最长的机器空闲时间为 t g l tt g g 5 阴影部分为g 。 一9 t g 6 一 勾问时工 开 的 、 一 i 图 23 ，l 浙江大学硕士学位论文 l 一专；所以g 中的工件必须在时间+ 专开始加工，g 4 中的工件可以每两个 同时加工，所以在卜专，孚+ 爿内完工；g 的工件尺寸都大于 + 丙1 ，了3 n + 专 中的空闲机器数，不能安排与g 4 同时加工，必在三笋+ 上n 时 刻开始加工，三个可同时加工，型2 + 万i + 1 完工；工件g 6 加工时间很长，只能 排在g 完工后，如图。因此g 6 的完工时刻孚+ 号+ 1 ，即是算法排序的完工时 间， c 出：型+ 三+ i 。 ，v 图2 g 6 目g 随l g i ，g 4g 2 ，g 3g 5 而事实上，我们可以把g 。，g 4 和g 6 放在同时加工，完工时间为n + ； g 2 和q 的任意两个工件都能放在同时加工，总加工时间为专+ 1 ；g 中的三个 工件则同时开始加工在| v + 号+ 1 。这样，总完工时闻为+ 万2 + 2 ，如图。这 是一个可行的排序，所以有c + 寺+ 2 ，那么 v 5 n 2 竺 互：豆：! 三 c n + 三+ 2 2 所以，此算法的竞争比至少是昙。 - 一1 0 浙江大学硕士学位论文 2 2 改进的贪婪算法 在上一节利用l s 思想设计了并行工件排序列的贪婪算法，竞争比的上界 是旦。由于算法是一个贪婪算法，在某一工件到达的时候，只考虑了它在当时 4 能开始加工的最小时刻这样它有可能就成为一种类似墙的工件，在它被加工 的时候工作的机器数量很多，而在它之前和之后都有大量的机器空闲，这样排 序就把机器的空闲隔成了零散的部分，而挡住了后面到达的小尺寸但加工时间 长的工件排到它的前面，如图l 中的g ：和g 5 就挡住了瓯在更早的时刻开始加 工。特别地当这个工件尺寸很大而加工时间又很短时，会造成空间的很大浪费。 针对这种情况，我们对l s 算法进行了改进，引入一个参数口，定义了大 工件，算法对大工件进行依次排序，对小工件仍使用l s 的方法，其实就是利 用排序问题中常用的等候的思想，把某些用l s 算法可排在前面加工的大工件 放到后面加工，使竞争比的上界与口有关，在口取某些值的时候竞争比下降。 11 定义2 2 设参数口， x ，则必存在小工件在x 后开始加工，由引理2 2 ，在【o ，d 内任意时 刻机器的工作效率均大于1 一口。引理2 1 在这里也同样适用，即k ，d ) 内任意时 刻的机器工作效率不小于鲁。 设y = d 一善，有c ( 1 一口b + 要y ；c 岱口) = d + a = x + ) ，+ p ，。 1 y 厨，c l s ( a 0 + h + 研( 2 + p ) c ； 2 y 厨，0 + ) c ( 1 + x l 一口b + 善( i + h = x + y 十( 一口一q p ) x + ( ；一； y ； 当( - a - 妒砖+ ( 争抄。时，- 1 2 ，2 怛2 ，所以当吉小跳。娜竿； 口 口2 1 3 浙江大学硕士学位论文 当取= 扣陟竿，吉办心+ 巫2 一孚，这时 m a x b n 矗取鼬值。也就是当口= 孚，算法l s p ) 在工件尺排 增到达情况下的静比不黜+ 孚。 一1 4 渐江大学硕士学位论文 第3 章加工时问非增的并行工件排序 3 1 贪婪算法的竞争比 工件的加工时间非增，即p 。p ：朋，工件尺寸的信息不已知。在特 殊情况下，加工时间全部相等p 。= p 2 - 一p 。，不妨设为1 ，若假设在设计算 法时工件都是在整数时刻开始加工，则问题可看作在线的装箱问题 ( b i n p a c k i n g ) ，即每个单位长度的时间都看作是一个箱子，箱子的高就是肌。 把工件看作物品，物品大小就是工件的尺寸( m ) ，问题就是把这些物品装到高 为m 的箱子中去，目标是装完所有的物品使用的箱子最少，也就是所有工件完 工的时间最早。装箱问题有很多近似算法，在线算法已知的最好的下界和上界 分别是；和三。对于经典的装箱问题，f f 算法的绝对竞争比在而1 7 利i 7 ( 【1 2 】， 【1 3 】) 之间。在工件加工时间非增但不全部相等的情况，利用l s 思想可设计出 贪婪算法，即按工件到达的顺序依次将它们安排在能使其最早开工的机器上加 工。 在这里，定义工件尺寸大于聊的工件为大工件，其它的是小工件。 z l s 算法： 任意工件以p i ，一，以) ，在尽可能早的时刻开始加工；即找到一个最 小的时刻( 一定是某个厶) ，满足在吨，l h + 只】时间段内任何时刻都至少有台机 器空闲，z 安排在毛时刻开始加工，即 岛= 嘤争以ik ，厶+ 只e 少有台机器空闲 直到没有新的工件到达为止。 记r 为执行算法后的排序，按工作效率可把r 分成若干个时间段，记 r = 如，厶，丑：，l ，巩+ 1 ) ，e = 【口，6 j l 厶= 陆，q + 。】，c ”= 以+ l ，e ，厶都是互不 重叠的连续时间段，满足e 内任何时刻机器的工作效率都大于妄，内任何时 刻的工作效率都不大于三( 妻) 。为避免出现平凡的情况，假设 上，i = 1 , 2 ，k 和e 中，i = 2 ，k ；这两种情况下显然算法排序完工时问 与最优排序的完工时间比值是小于2 ；而由于算法排序可能以一个小工件结束， 一1 5 浙江大学硕士学位论文 所以b k “= 中是可能出现的，这时令以。= a k 算法的完工时间为所有时间段之和 t k * l c ”= 吲+ 旧 | l - i = t m 台 - 一 l 0 b l厶b kk 下面进行算法分析，所有在厶内加工的工件都是小工件，而且没有i 件在 ( 6 ，a ，+ ) 开始加工。若不然，因为这样的工件一定是小工件，而在匆时刻机器工 作效率小于三2 ，有超过丢聊的机器空闲，算法会把该工件安排在6 j 开始加工。 所以每个厶的最大长度都不超过所有小i 件中的最长加i 时间，即 吣裂 c m a ) 【h j 吲。 内的工作效率非增，否则必有小工件在( 6 ，口。) 开始加工。 若最= m ，那么在厶后面开始加工的工件都是大工件，否则由于工件加工 时间递减，小工件必可安排在厶，零时刻开始加工。设r 是厶后所有大工件的 加工时间总和，大工件是不能重叠，即不能同时加工，有 c 2 r ，c “= l 厶l + r 。 一1 6 浙江大学硕士学位论文 b 巾，即第一个工件是大工件。考虑区间l ，1 f k ，骂+ 中必有一个 大工件在e + 的开始时刻a j + 。开始加工。记这个大工件为以，加工时间为咒， 需要的机器数m 。，那么在厶。中加工的工件一定在以之后到达，否则算法要安 排这些工件到中加工。所以在毛+ 。中加工的小工件的加工时间都不超过嚣， 且均大于k l ，可得j 厶l 埘。由于工件加工时间非增，p q - p 。旧i 丘和骂的平均 。望掣n + 吲 一1 7 浙江大学硕士学位论文 。蜷群型i t i + 定理3 1 算法的霓争比全多是2 。 证明磊= 中，c “= l a l + r - 2 c 骂巾，上面证明了厶+ 马+ 。o = 1 ，七一1 ) 和厶+ 蜀的平均工作效率都大于 j 1 ，而若毋。m ，曰。的i 作效率也是大于j 1 的，覆盖了 r = 池，厶，马，丘，毋+ ， 整个区间，所以在r 的整个的平均工作效率大于妻， 因此 c 搪讣洲= 三c 4 所以算法的竞争比 也= 脚z 所以，算法的竞争比至多是2 a _ 1 8 一 渊 浙江大学硕士学位论文 参考文献 【1 r l g r a h a m ，el l a w l e r , j k l n s t r a , r i n n o o y , a h qk a n o p t i m i z a t i o n a n d a p p r o x i m a t i o n i n d e t e r m i n i s t i cs e q u e n c i n ga n d s c h e d u l i n g ：a s u r v e y a n n d e s e r e t em a t h 一1 9 7 9 ( 4 ) ：2 8 7 - 3 2 6 【2 】b s b a k e r , j s s c h w a r z , s h e l fa l g o r i t h mf o rt w o - d i m e n s i o n a lp a c k i n g p r o b l e m s ，s i a mj o u r n a lo nc o m p u t i n g1 2 ( 1 9 8 3 ) ，5 0 8 5 2 5 【3 e n a r o s k aa n du s c h w i e g e l s h o h n , o na no n - l i n es c h e d u l i n gp r o b l e mf o r p a r a l l e lj o b s ，i n f o r m a t i o np r o c e s s i n gl e t t e r s8 1 ( 2 0 0 2 ) ，2 9 7 3 0 4 【4 r l g l a h a r n ，b o u n d sf o rc e r t a i nm u l t i p r o c e s s i n ga n o m a l i e s , b e l ls y s t e mt e e k j o u r n a l ，1 9 6 6 ，4 5 ：1 5 6 3 - 1 5 8 1 【5 gw o e g i n g e r , ap o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m ef o rm a x i m i z i n gt h e m i n i m u mm a c h i n ec o m p l e t i o nt i m e ，o p e r a t i o n sr e s e a r c hl e t t e r s ，1 9 9 7 ，2 0 ： 1 4 9 1 5 4 【6 】d s i m c h i l e v i ，n e ww o r s t - c a s er e s u l t sf o r t h eb i np a c k i n gp r o b l e m , n a v a l s e a r c hl o g i s t i c s4 1 ( 1 9 9 4 ) ，7 9 - 5 8 5 【7 b j o h a n n e s ，s c h e d u l i n gp a r a l l e lj o b st om i n i m i z em a k e s p a r t , t e c h n i c a lr e p o r t 7 2 3 - 2 0 0 1 ，t ub e d i n , 2 0 0 1 f u l lv e r s i o nh a sb e e np u b l i s h e di nj o u r n a lo f s c h e d u l i n g9 ( 2 0 0 6 ) ，4 3 3 - 4 5 2 【8 】t g o r m l e y ，n r e i n g o l d ，e t o m g ，a n dj w e s t b r o o k , g e n e r a t i n ga d v e r s a r i e sf o r r e q u e s t a n s w e rg a m e s ，p r o c e e d i n g s o ft h e1l t ha c m s i a ms y m p o s i u mo n d i s c r e t ea l g o r i t h m s ( s o d a ) ，2 0 0 0 ，5 6 4 5 6 5 【9 f i a t , a ，w o e g i n g e lq ，c o m p e t i t i v ea n a l y s i s o fa l g o r i t h m s ，i no n - l i n e a l g o r i t h m st h