（运筹学与控制论专业论文）窗时排序问题中的最优化算法研究.pdf

s h a n d o n gu n i v c r s i t yd o c t o r a ld i s s e r t a t i o n 窗时排序问题中的最优化算法研究 赵 洪銮 ( 山东大学数学与系统科学学院，山东，济南2 5 0 1 0 0 ) 指导教师李国君蓑授 中文摘要 为了避免储存以及隐藏的额外运转带来的高费用，比如由于等待，传递，额外 劳动力，重加工以及订单改变等引起的效益损失，生产商不仅考虑延误带来的惩罚 还必须顾及提前完工付出的费用；此乃准时排序问题它限定工件的交货期；如果 工件在交货期之前完工，会出现储存费和保管费之类；而在交货期之后完成，固然要 课以罚款，则会产生延误赔偿甚至失去合作机会等损失而准时排序的目的就是要 最小化这些费用之和，所以，在“准h 护概念中，尽可能使得工件的完工时间接近其 交货期或者提前和延误的工件个数尽量少因此，提前和延误应该尽可能地避免， 这也使得以前讨论的传统性能函数已经无效既然目标函数是关于工件完工时间的 非正则函数，问题的研究相对比较困难 实际上，大多数生产环境中的交货期允许一定的宽容公差，所以交货期窗口” 的概念显得尤为重要本文不考虑公共交货期的情况，而代之以公共交货期窗i ：l ； 它是一个被最早交货期e 和最晚交货期d 定义的时间区间，其中窗口大小定义为 k = d e ，最早交货期e 也被称为交货期窗口的位置工件在区间【e ，d 1 中完工不必 支付费用，若在e 之前或d 之后完成将受到提前或延误惩罚这就是窗时排序，它 推广了准时排序问胚，并且，在有些生产场景中，交货期窗口的位置和大小经常作 为决策变量( 假设单位时间费用分别是1 和6 ) ，与工件的最优序列一起确定 粗略来讲，有两类相关的惩罚函数一类是提前时间和延误时间所带来的惩罚， 即与完工时间距离交货期窗口的时间差成正比此类目标函数既普遍又具备很强的 竞争力，目前有以下几个结果k r a m e r 和l e ep 胡分析并证明当交货期窗口给定 时，此问题是n p - 完备的；当交货期窗口的位置待定但没有决策费用时，可以在多 项式时间内找到最优算法【6 2 】、【6 4 】及1 7 9 1 分别探讨了交货期窗口的位置或大小 是给定还是待定的生产情形，以最小化提前和延误惩罚及窗口的决策费用之和在 这几篇文献中，“位置杉【 对搜寻最优排序起了关键作用就这类目标函数，本文的 s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 第二章和第三章都讨论了工件有公共交货期窗口的同时加工排序问题，对批容量是 有限的还是无限的两种情况分别研究；尤其当批的容量有限时，乃是以上经典排序 的推广在寻找它们的最优算法时。啦置权i 已不再有效 另一类目标函数中，提前和延误惩罚依赖于工件是否提前或延误，而不是提前 或延误了多长时间这类问题关注的是提前和延误的赋权工件数y e u n g 等【8 6 】考 虑交货期窗口待定的情况，当惩罚系数是任意整数时，他们给出了n p - 完备性证明 和拟多项式时间算法；并对两类特殊情况提出有效算法本文的第四章就交货期窗 口的位置和大小是给定还是待定的其他三种情况进行了讨论并提出最优算法；第五 章至第七章把这些问题推广刭同时加工排序，成组分批排序及平行机加工 本文共分为七章第一章介绍窗时排序及其相关的组合优化问题，常用术语与 符号，准时排序和窗时排序的一些相关结果，本文的结构与主要内容 在以前关于同时加工排序问题的研究中，最优排序是要使得总完工时间或最大 完工时间等正则函数最小；只有几篇文献涉及到交货期的存在性，以最小化总延误 或最大延误这里，第二、三、五章中。首次把窗时排序推广到了多个工件可以被同 时加工的情况，目标是要把工件分成多个批，再排列批的次序使得总费用最小其 中第二章考虑批容量无限时，在交货期窗口给定或其位置待定情况下，以最小化总 的提前和延误惩罚；并且如果交货期窗口有待定参数时，总费用包含该决策费用 性质2 存在一个i 优排序口，使得准时集合( 口) 包含加工时间最小的工件 性质3 在任一个囊优排序口中，要么( 口) = 0 ，要么( 口) 只包含一个批而 且这个秕是所有批中加工时间囊小的一个 性质6 在一个i 优排序中，延误集合中的批按加工时间非降的顺序排列 对给定的交货期窗口。第一个被加工批的开工时间如性质5 中所述；而且根据 性质7 ，最优排序符合s p t - 批序所以该问题就转化为最小化延误工件的总完工 时间，从而可以用一个动态规划得之而当交货期窗口的位置e 待定时，第一个批 的开工时间为零，e 的取值如性质9 于是用枚举法确定了集合后，亦转化为 最小化延误工件的总完工时间问题根据以上分析，分别得到用时为o ( n 2 l o g n ) 和 o ( n 3l o g ，1 ) 的两个多项式时间算法 第三章讨论了交货期窗口给定且批容量有限的情况，但问题的复杂性是n p 完 备的实际上，最小化总完工时间的问题复杂性仍然没有解决，只是一些文献中给 出了p t a s 何况本章的问题要比它难得多文中提出了最优排序的几个性质，其中 i i s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 性质1 1 ，1 2 说明了最优排序是s p t - 批序的并且准时集合包含那些最小的工件 性质1 0 在囊优排序口中，存在批b 使得c ( b ) = e 或c ( b ) = d ，除非第一个 批的开工时间为零 然后探讨了以下两种特殊情况当提前集合为空集时，仍然可以用列举法确定 准时集合，问题就是要最小化延误工件的总完工时间，于是可以得到其p t a s 另 外，当所有工件的加工时间相等时，经分析得到了多项式时间算法 以上两章分别就批容量无限和有限两种情况讨论了同时加工排序。目标是最小 化关于提前时间和延误时间的惩罚下面几章研究第二类目标函数第四章就交货 期窗口给定窗口大小待定，窗口的位置和大小均待定三种情况进行探讨，以最小 化提前和延误工件的赋权个数及交货期窗口的决策费用和；在提出最优性质和参数 分析的基础上。给出了相应的多项式时间算法 作为上一章的推广，第五章研究有界的同时加工排序问题当提前和延误惩罚 系数是任意整数且窗口位置待定时，把3 - 划分的一个实例转化到该问题，从而证明 了它是强n p - 完备的进而提出几个最优性质，但最优排序已不再满足s p t - 批序 进一步，本章解决了三种特殊情况首先，当所有的提前惩罚为零时，问题转 化为有待定的公共交货期问题，但它仍是n p - 完备的，本文给出了拟多项式时间算 法如果交货期窗口的定位费用为零，其位置可以取任意大的值通过使得准时集 合能避免最多惩罚以达到最优，得到了拟多项式时间算法这也说明以上两个特例 是一般n p - 完备的另外，当所有的提前惩罚相等延误惩罚也相等时，准时批包 含那些最小的工件，算法5 - 3 在o ( m a x b 2 n ，n l o g n ) 时间内得到最优排序以上结 果也推广了【8 6 】中的结论 现实生产中有以下情形具有相似特征的一些工件需要相同的生产场景和设 备，所有工件被分成多个组，于是从加工一个组的工件转化到加工另一个组的工件 时需要执行安装任务正是由于安装任务的介入使得问题更加困难1 7 8 1 讨论当交 货期窗口给定时以最小化赋权提前时间和延误时间总和的问题；即使当e = 0 时，问 题的复杂性未知但是此类生产环境普遍存在，于是第六章继续讨论，目标函数是 关于提前和延误的工件个数，其中交货期窗口的位置待定或者位置和大小均待定 显然，第一个安装任务在零时刻开始，而且在整个工件与安装任务的序列中没 有空冈时间性质3 2 3 5 描述了一个最优排序的结构；算法6 1 中综合考虑工件对 总惩罚的贡献而确定其所在的集合 i i i s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n 而当交货期窗口的位置和大小都是决策变量时，除了以上提到的性质，最优算 法又基于以下结论- 性质2 3 如果5 1 + 口且e 1 ，则k = 0 推论3 在i 优排序盯中，如果1 6 1 + a 且e21 ，则k 等于1 加上 w p ) 以) 中工件和安装任务的运行时间总和 第七章把窗时排序推广到了多台平行机上，以最小化提前和延误赋权工件数， 乃是准时排序和单机排序的推广它是强n p - 完备的当交货期窗口的定位费用为 零时，根据多背包问题的算法得到p t a s 若定位费用不是零，在确定了各机器上的 提前集合后也类似地得到p t a s 概括地讲。本文的创新点主要有t 1 多个工件可以同时被加工，并把同时加工的工件视为一个批，目标函数是关 于提前时间和延误时间的总惩罚；本文首次把窗时排序和同时加工排序结合起来； ( 1 ) 当批容量无界时，对于交货期窗口给定及其位置待定两种情况。分别给出 了多项式时间算法； ( 2 ) 当批容量有界且交货期窗口给定时，问题是n p - 完备的，并对两个特殊情 况分别给出了p t a s 和多项式时间算法从而推广了【5 2 】中的结果 2 当目标函数关于提前和延误的赋权工件个数时， ( 1 ) 针对交货期窗口的位置和大小是给定还是待定的生产场景，解决了除【8 6 l 中所述之外的三种情况； ( 2 ) 将 8 6 】中的结果推广到了同时加工排序，证明了当惩罚系数是任意整数时， 问题是强n p - 完备的；然后对三个特例得到拟多项式时间算法或者给出有效算法； ( 3 ) 讨论成组分批排序的情形【7 8 】曾对第一类目标函数进行了探讨，但问题 的复杂性并未解决本文就第二类目标函数研究，在给出几个结构化性质的基础上 得到多项式时间算法；亦是1 8 6 的推广； ( 4 ) 在多台平行机上加工且交货期窗口的位置待定。分别就其定位费用为零和 非零两种情况分别给出了p t a s 关键词；排序；单机器；等同机；交货期；交货期窗口；窗口位置；窗口大小； 提前；延误；提前时间；延误时间；批；组安装任务；最优算法；p t a s i v s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n o p t i m a la l g o r i t h m so ft h e s c h e d u l i n gp r o b l e mw i t hc o m m o n d u ew i n d o w z h a oh o n g - l u a n ( s c h o o lo fm a t h s y s s c i ，s h d o n gu n i v ，j i n a n2 5 0 1 0 0 ，p 凡c h i n a ) a b s t r a c t i no r d e rt oe l i m i n a t eh i d d e np r o d u c t i o na n di n v e n t o r yp r o b l e m sw h i c hc a i l 鼯h i g h c o s t s ，f o re x a m p l e ，w a i t i n gt i m e ，d e l i v e r yt i m e ，e x t r al a b o u rc o s t s ，r e w o r ka n do r d e r c h a n g e s ，m a n u f a c t u r e r sm u s tc o n s i d e rs c h e d u l i n gp r o b l e m si n v o l v i n gn o to n l yt h et a r - d i n e s sp e n a l t i e s b u ta l s ot h ee a r l yc o s t s t h e ya r ej i t ( j n a - i n t i m 4s e q u e n c i n ga n d s c h e d u l i n gp r o b l e m s ，w h i c ha q u m et h ee 幽t e n c eo fj o bd u ed a t e sa n dd i s c o u r a g ee a r l y a 8w e l la st a r d yj o b s i faj o bf i n i s h e sb e f o r ei t sd u ed a t e a ne a r l yp e n a l t yw i l lb e i n c u r r e ds u c h 蠲h o l d i n gc o s t a n dc o m p l e t i n gt h ej o ba f t e ri tc a nr e s u l ti ns u c ht a r d y p e n a l t ya sl a t ec h a r g e ，币嗍d e l i v e r yc h a r g e ，o rl o s to fs a l e s oaj i t - s c h e d u l ei st o m i n i m i z et h eg mo ft h e s ep e n a t i o s u n d e rt h ej u s t - i n - t i m ec o n c e p t i o n ，i ti sd e s i r e dt oh a v ej o b sc o m p l e t e d 弱c l o s e 8 sp o s s i b l et ot h e i rr e s p e c t i v ed u ed a t e s o rm i n i m i z et h ew e i g h t e dn u m b e ro fe a r l y a n dt a r d yj o b s t h i sn e c e s s i t a t e st h eu s eo f n o n t r a d i t i o n a lp e r f o r m a n c em c a s n r e st h a t t a k ei n t oa c c o u n tb o t he a r l ya n dt a r d ye v e n t s s i n c ei t so b j e c t i v ei sn o n - r e g n l a ra b o u t t h ec o m p l e t i o nt i m eo fj o b s ，t h ep r o b l e mi sm o r ed i f f i c u l ta n dm a n yr e l a t e ds c h e d u l i n g p r o b l e m sa r en p - c o m p l e t eo re v e no p e n i nt h i sd i s s e r t a t i o n ，w er e m o v et h ec o m m o nd u ed a t ec o n c e p ta n dr e p l a c ei tw i t h ac o n l n l o nd u ew i n d o wa s s u m p t i o n t h ec o n c e p to fd u ew i n d o wi si m p o r t a n ts i n c e m o s td u ed a t e s9 x es p e c i f i e dw i t hs o m et o l e r a n c e s t h e ni ti sat i m ei n t e r v a ld e f i n e d b ya ne a r l yd u ed a t ee ( a l s oc a l l e dw i n d o wl o c a t i o n ) a n dat a r d yd u ed a t ed ，w h e r e k = d ei sw i n d o ws i z e o n e sf i n i s h i n gi n 【e ，d lh a v en op e n a l t y o t h e r w i s e ，t h e ya r e s u b j e c t e dt oe a r l yo rt a r d yp e n a l t i e s ，d e p e n d i n go i lc o m p l e t i n gb e f o r eeo ra f t e rd a n d t h ew i n d o wl o c a t i o na n ds i z ea r et ob ed e t e r m i n e da l o n gw i t ht h eo p t i m a ls e q u e n c e ， v s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n p e n a l i z e db yl i n e a rt i m ec o s t1a n ddr e s p e c t i v e l y , i ns o m ep r o d u c t i o ns i t u a t i o n s t h u s ， t h i sc o n c e p tg e n e r a l i z e st h ec o m m o nd u ed a t ea s s u m p t i o n 1 强ea b o v ep r o b l e m sa r er e a l - l i f ep r o b l e m s c o n c e r n i n gs o m ee x i s t i n gu n e x p l o r e d o n e sw h i c hn e e dt ob ea d d r e s s e d o w i n gt ot h ew o r l d w i d ei n c r e a s i n gi m p o r t a n c eo f t h ej u s t i n - t i m ec o n c e p tw i t hd u ed a t et o l e r a n c e ，d u ew i n d o ws c h e d u l i n gp r o b l e m s a l es i g n i f i c a n t t oo l e rs u r p r i s e ，o n l yac o u p l eo fs i n g i em a c h i n ed u ew i n d o w s c h e d u l i n g p r o b l e m ss of a rh a v eb e e ns o l v e d o n eo ft h er e a s o n si sp r o b a b l ya t t r i c t e dt oi t s n o t o r i o u si n t r a c t a b l eh a r d n e s s t h ep u r p o s eo f t h i sd i s s e r t a t i o ni st w o f o l d ，o n eo f w h i c h i st oi n v e s t i g a t et h i su n e x p l o r e dp r o b l e ma n da n o t h e ri st op r o v i d es o l u t i o np r o c e d u r e s r o u g h l y , t h e r ea r et w ok i n d so fp e n a l t yf u n c t i o n s t h ef i r s ti so ne a r l y - t i m ea n d t a r d y - t i m ep e n a l t i e s ，i e p r o p o r t i o n a lt ot h et i m ed i f f e r e n c ef r o mt h ed u ew i n d o w ， w h i c hi so f t e nc a l l e de a r l i n e s sa n dt a r d i n e s s t h i so b j e c t i v ei 8m o r ec o m m o na n dt o m p e t i t i v e k r a m e ra n dl e e 【5 2 】a n a l y z es u c hp r o b l e ma n dp r o v ei t sn p - c o m p l e t e n e s sf o r g i v e nd u ew i n d o w t h e nap o l y n o m i a la l g o r i t h mi sp r o v i d e dt h e r ef o rd e c i s i o nw i n d o w l o c a t i o nb u tw i t h o u tc o s t 【6 2 】，【6 4 】a n d 【7 9 】s t u d yt h ep r o b l e m sw i t hv a r i a b l ew i n d o w l o c a t i o n ，d e c i s i o nw i n d o wl o c a t i o na n ds i z e ，a n dd e c i s i o nw i n d o ws i z er e s p e c t i v e l y t h e o b j e c t i v ei st of i n dt h eo p t i m a ld u ew i n d o wa n dj o bs e q u e n c es u c ht h a tt h ep e n a l t y8 u u l o fc a r h n e e s ，t a r d i n e s sa n dt h ec o s to fd e t e r m i n gd u ew i n d o wi sm i n i m i z e d a ss o l i n g t h e s ep r o b l e m s ，t h ep o s i t i o n a lw e i g h ti sap o w e r f u lt o o la n dt h e ne f f i c i e n ta l g o r i t h m s a r ep r o v i d e db a s e do ns o m eo p t i m a lp r o p e r t i e s i nc h a p t e r s2 , 3h e r e ，w ee x t e n di tt o t h ed u ew i n d o ws c h e d u l i n gw i t hh a t c h i n g b u tn ol l s eo fp c 6 i t i o n a lw e i g h t a n o t h e ri sa b o u tt h ew e i g h t e dn u m b e ro fe a r l ya n dt a r d yj o b s ，r a t h e rt h a nh o w e a r l yo rh o wl a t et h e ya r e t h i ss o r to fp r o b l e m si ss i g n i f i c a n ta n dh a sm a n yp r a c t i c a l a p p l i c a t i o n s ，f o re x a m p l e ，i nc h e m i c a l ，d r u g sa n dc o l l e c t i o no f b l o o df r o md o n o r s y e u n g e ta 1 【8 6 】p r o v et h a tt h ep r o b l e mi sn p - c o m p l e t ew i t hv a r i a b l e w i n d o wl o c a t i o n ，w h e n t h ep e n a l t yf a c t o r sa r ea r b i t r a r yi n t e g e r s f u r t h e r ，p o l y n o m i a la l g o r i t h m sa r ep r o p o s e d f o rt w os p e c i a lc a s e s a sf o rt h i sf u n c t i o n ，c h a p t e r s4s t u d yo t h e rs e v e r a lv e r s i o n sa b o u t d e c i s i o n0 5g i v e nw i n d o wl o c a t i o na n ds i z e c h a p t e r s5 - 7e x t e n dt h e mt ob a t c h i n g o p e r a t i o n ，f a m i l ys e t u p sa n dp a r a l l e lm a c h i n e s ，w h i c hg e n e r a l i z et h er e s u l t so fc h a p t e r 4a n dt h o s ei n 【8 6 b u tp o s i t i o n a lw e i g h ti sn o th o l d e nf o rt h i sp e n a l t yf u n c t i o n v i s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n t h et h e s i si sd i v i d e di n t ot h ef o l l o w i n g8 e 、7 锄c h a p t e r s i nc h a p t e r1 w ei n t r o d u c e d u ew i n d o ws c h e d u l i n ga n dt h er e l a t e dc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s ，s o m ek e y c o n c e p t sa b o u tc o m p l e x i t ya n dr e l a t e dw o r ka b o u td u ed a t e sa n dd u ew i n d o w i nt h ep r e v i o u sr e f e r e n c e sa b o u th a t c h i n g ，t h eo p t i m a ls c h e d u l ei st om i n i m i z et h e t o t a lc o m p l e t i o nt i m eo r 如a 】唧a n o n l ys e v e r a lc o n s i d e rt h ee x i s t e n c eo fd u ed a t e s a n dm a k et h et o t a lt a r d i n e s s0 1 m a x i m a ll a t e n e s sm i n i m i z e d i nc h a p t e 硌2 ，3 ，5o ft h i s d i s s e r t a t i o n ，w ef i r s t l ye x t e n dd u ew i n d o ws c h e d u l i n gt ot h es i t u a t i o nw h e r et h ej o b s 锄h ep r o c e s s e di nb a t c h e s ，w h e r eab a t c hi sas e to fj o b sp r o c e s s e ds i m u l t a n e o u s l y a n dc o m p l e t e dt o g e t h e rw h e nt h ep r o c e s s i n go fa l lj o b si nt h eb a t c hi sf i n i s h e d t h u s ， t h et a s ki 8t op a r t i t i o nt h ej o b si n t ob a t c h e sa n ds c h e d u l et h eb a t c h e st om i n i m i z et h e s u mo fa l lc o s t s i nc h a p t e r2 ，t h es c h e d u l i n gp r o b l e ma s s o c i a t e dw i t hb a t c h i n g a n d c o m m o nd u ew i n d o w ，i sc o n s i d e r e d ，b u tf o ru n b o u n d e db a t c h i n g t h eo b j e c t i v ei st o m i n i m i z et h et o t a lw e i g h t e de a r l i n e s sa n dt a r d i n e e sp e n a l t i e so fa l lj o b s ，f o rg i 啪a n d d e c i s i o nw i n d o wl o c a t i o n p r o p e r t y2 t h e r ee x z s t sa no p t i m a ls c h e d u l e 盯w h e r et h eb a t c h e s 讥w i n d o ws e t w ( o ) c o n t a i nt h es m a l l e s tj o b sa m o n ga l lnj o b s p r o p e r t y3 i na n yo p t i m a ls c h e d u l e 盯，e i t h e r ( 口) ；0o ri tc o n t a i n so n l yo n e b a t c h il o h o s ep r o c e s s i n gt i m e 话t h es m a l l e s to | a l lb a t c h e s p r o p e r t y6 i na no p t i m a ls c h e d u l e t h eb a t c h e s 讯t a r d ys e t i r es e q u e n c e di n n o n d e c r e a s i n go r d e ro t h e i rp r o c e s s i n gt i m e s t h e nf o rt h eg i v e nd u ew i n d o w , t h es t a r t i n gt i m eo ft h ef i r s tp r o c e s s e db a t c hc a l l h eo b t a i n e da sp r o p e r t y5 f u r t h e r ，a no p t i m a ls c h e d u l ei si ns p t - b a t c hr u l e ，s e e p r o p e r t y7 t h u st h ep r o b l e mi st r a n s f o r m e dt om i n i m i z et h et o t a lc o m p l e t i o nt i m eo f t a r d yj o b s s oad y n a m i cp r o g r a m m i n gi su s e dt od e t e r m i n et h et a r d yb a t c h e s f o rt h e d e c i s i o nw i n d o wl o c a t i o ne ，i t sv a l u ei sa sp r o p e r t y9 ，s i n c et h ef i r s tp r o c e s s e db a t c h s t a r t i n ga tt i m e7 u e r o a f t e re n u m e r a t i n gt h ee l e m e n t so fw ，i ti sa l s ot om i n i m i z e t h et o t a lc o m p l e t i o nt i m eo ft a r d yj o b s b a s e do nt h ea b o v ea n a l y s i s ，t w oo p t i m a l a l g o r i t h m sa r eg e n e r a t e d ，r e s p e c t i v e l yi nt i m eo ( n 2l o gn ) a n do ( n 3l o gn ) ，w h e r et li s t h en u m b e ro f j o b s a sf o rb o u n d e db a t c h i n gw i t hag i v e nd u ew i n d o w i ti sd i s c u s s e di nc h a p t e r3 s h a n d o n gu n i v e r s i t yd o c t o r a ld i s s e r t a t i o n t om i n i m i z et h ew e i g h t e de a r l i n e s sa n dt a r d i n e s s b u tt h ec o m p l e x i t yi sn p - c o m p l e t e a c t u a l l y , t h i ss c h e d u l i n gp r o b l e mi sm o r ed i f f i c u l tt h a nt h eo n e t om i n i m i z et h et o t a l c o m p l e t i o nt i m e ，w h o s ec o m p l e x i t yi so p e na n do n l yp t a si sp r o p o s e d t h e ns e v e r a l s t r u c t u r a lp r o p e r t i e sa r ep r o p o s e d f o ra no p t i m a ls c h e d u l e i ts a t i s f i e ss p t o b a t c hr u l e a n dt h ew i n d o ws e ts t i l lc o n t a i n st h es m a l l e s tj o b s ，嬲p r o p e r t i e s1 1 ，1 2 t h ef o n o w i n g i se x t e n d e df r o mt h ec l a s s i c a lp r o b l e m p r o p e r t y1 0 na no p t i m a ls c h e d u l e 口，t h e r ee x i s t so n eb a t c hb s u c ht h a tc ( b ) = eo rc ( b ) = d ，u t l f e s st h es t a r t i n gt i m eo ，t h ef i r s tp r o c e s s e db a t c h 诂z e r o ， t h e f o l l o w i n gs p e c i a lc a a r es o l v e d w h e nt h ee a r l ys e t i se m p t y , i tj 8t om i n i m i z e t h et o t a lc o m p l e t i o nt i m eo ft a r d yj o b sa f t e rt h ee n u m e r a t i o no fd e t e r m i n i n gw i n d o w s e t s oap t a sc a nb eo b t a i n e d a d d i t i o n a l l y , ap o l y n o m i a lt i m ea l g o r i t h mi sd e v e l o p e d a 8a l lp r o c e i n gt i m e sa r ee q u a l t h ea b o v et w oc h a p t e r sa r ea b o u te a r l y - t i m ea n dt a r d y - t i m ec o s t 。r e s p e c t i v e l y f o ru n b o u n d e da n db o u n d e db a t c h i n g a sf o rt h es e c o n dp e n a l t yf u n c t i o n ，s e v e r a l p r o d u c t i o ne n v i r o n m e n t sa r ei n v e s t i g a t e da m o n g t h ef o l l o w i n gc h a p t e r s i nc h a p t e r4 ， t h eo b j e c t i v ei st om i n i m i z et h ew e i g h t e dn u m b e ro fe a r l ya n dt a r d yj o b sf o rg i v e nd u e w i n d o w ，d e c i s i o nw i n d o ws i z e ，a n dv a r i a b l ew i n d o wl o c a t i o na n ds i z e c o r r e s p o n d i n g l y , t h r e ee f f i c i e n ta l g o r i t h m sa r ep r o v i d e db a s e do ns o m eo p t i m a lp r o p e r t i e s a st h ee x t e n s i o no ft h el a s tc h a p t e r ，b o u n d e db a t c hs c h e d u l i n gi sd i 窨c n s s c di n c h a p t e r5t 0m i n i m i z et h en u m b e ro fe a r l ya n dt a r d yj o b sw i t ht h ew i n d o wl o c a t i o n c o s t w h e nt h ee a r l ya n dt a r d yp e n a l t yc o e f f i c i e n t so ft h ej o b sa r ea r b i t r a r ya n dt h e w i n d o wl o c a t i o ni 8d e c i s i o n ，t h ep r o b l e mi ss h o w nt 0b es t r o n g l yn p - c o m p l e t e ，w h o s e i n s t a n c ec b et r a n s f o r m e df r o mo n eo f3 - p a r t i t i o np r o b l e m t h e ns e v e r a lo p t i m a l p r o p e r t i e sa r ep r o p o s e d b u ta no p t i m a ls c h e d u l ec nn ol o n g e rr e s t r i c tt os p t - b a t c h o r d e rf o rt h ee n t i r es c h e d u l e t h e nt h r e es p e c i a lc a s e sa r es