论文部分内容阅读
为了避免储存以及隐藏的额外运转带来的高费用，比如由于等待、传递、额外劳动力、重加工以及订单改变等引起的效益损失，生产商不仅考虑延误带来的惩罚还必须顾及提前完工付出的费用；此乃准时排序问题．它限定工件的交货期；如果工件在交货期之前完工，会出现储存费和保管费之类；而在交货期之后完成，固然要课以罚款，则会产生延误赔偿甚至失去合作机会等损失．而准时排序的目的就是要最小化这些费用之和，所以，在“准时”概念中，尽可能使得工件的完工时间接近其交货期或者提前和延误的工件个数尽量少．因此，提前和延误应该尽可能地避免，这也使得以前讨论的传统性能函数已经无效．既然目标函数是关于工件完工时间的非正则函数，问题的研究相对比较困难．
实际上，大多数生产环境中的交货期允许一定的宽容公差，所以‘咬货期窗口”的概念显得尤为重要．本文不考虑公共交货期的情况，而代之以公共交货期窗口．它是一个被最早交货期e和最晚交货期d定义的时间区间，其中窗口大小定义为K=d-e，最早交货期e也被称为交货期窗口的位置．工件在区间[e，d]中完工不必支付费用，若在e之前或d之后完成将受到提前或延误惩罚．这就是窗时排序，它推广了准时排序问题．并且，在有些生产场景中，交货期窗口的位置和大小经常作为决策变量(假设单位时间费用分别是，γ和δ)，与工件的最优序列一起确定．
粗略来讲，有两类相关的惩罚函数．一类是提前时间和延误时间所带来的惩罚，即与完工时间距离交货期窗口的时间差成正比．此类目标函数既普遍又具备很强的竞争力，目前有以下几个结果．Kramer和Lee[52]分析并证明当交货期窗口给定时，此问题是NP-完备的；当交货期窗口的位置待定但没有决策费用时，可以在多项式时间内找到最优算法． [62，64，79]分别探讨了交货期窗口的位置或大小是给定还是待定的生产情形，以最小化提前和延误惩罚及窗口的决策费用之和．在这几篇文献中，“位置权”对搜寻最优排序起了关键作用．就这类目标函数，本文的第二章和第三章都讨论了工件有公共交货期窗口的同时加工排序问题，对批容量是有限的还是无限的两种情况分别研究；尤其当批的容量有限时，乃是以上经典排序的推广．在寻找它们的最优算法时，“位置权”已不再有效．另一类目标函数中，提前和延误惩罚依赖于工件是否提前或延误，而不是提前或延误了多长时间．这类问题关注的是提前和延误的赋权工件数．Yeung等[86]考虑交货期窗口待定的情况，当惩罚系数是任意整数时，他们给出了NP-完备性证明和拟多项式时间算法；并对两类特殊情况提出有效算法．本文的第四章就交货期窗口的位置和大小是给定还是待定的其他三种情况进行了讨论并提出最优算法；第五章至第七章把这些问题推广到同时加工排序、成组分批排序及平行机加工．
本文共分为七章．第一章介绍窗时排序及其相关的组合优化问题，常用术语与符号，准时排序和窗时排序的一些相关结果，本文的结构与主要内容．
在以前关于同时加工排序问题的研究中，最优排序是要使得总完工时间或最大完工时间等正则函数最小；只有几篇文献涉及到交货期的存在性，以最小化总延误或最大延误．这里，第二、三、五章中，首次把窗时排序推广到了多个工件可以被同时加工的情况，目标是要把工件分成多个批、再排列批的次序使得总费用最小．其中第二章考虑批容量无限时，在交货期窗口给定或其位置待定情况下，以最小化总的提前和延误惩罚；并且如果交货期窗口有待定参数时，总费用包含该决策费用．
性质2存在一个最优排序σ，使得准时集合W(σ)包含加工时间最小的工件．
性质3在任一个最优排序σ中，要么W(σ)=φ，要么W(σ)只包含一个批而且这个批是所有批中加工时间最小的一个．
性质6在一个最优排序中，延误集合中的批按加工时间非降的顺序排列．
对给定的交货期窗口，第一个被加工批的开工时间如性质5中所述；而且根据性质7，最优排序符合SPT-批序．所以该问题就转化为最小化延误工件的总完工时间，从而可以用一个动态规划得之．而当交货期窗口的位置e待定时，第一个批的开工时间为零， e的取值如性质9．于是用枚举法确定了集合W后，亦转化为最小化延误工件的总完工时间问题．根据以上分析，分别得到用时为O(N<2> logn)和O(n<3> logn)的两个多项式时间算法．
第三章讨论了交货期窗口给定且批容量有限的情况，但问题的复杂性是NP-完备的。实际上，最小化总完工时间的问题复杂性仍然没有解决，只是一些文献中给出了PTAS.何况本章的问题要比它难得多．文中提出了最优排序的几个性质，其中性质11、12说明了最优排序是SPT一批序的并且准时集合包含那些最小的工件．性质10在最优排序σ中，存在批B使得C(B)=e或G(B)=d，除非第一个批的开工时间为零．
然后探讨了以下两种特殊情况．当提前集合为空集时，仍然可以用列举法确定准时集合，问题就是要最小化延误工件的总完工时间，于是可以得到其PTAS．另外，当所有工件的加工时间相等时，经分析得到了多项式时间算法．
以上两章分别就批容量无限和有限两种情况讨论了同时加工排序，目标是最小化关于提前时间和延误时间的惩罚．下面几章研究第二类目标函数．第四章就交货期窗口给定、窗口大小待定、窗口的位置和大小均待定三种情况进行探讨，以最小化提前和延误工件的赋权个数及交货期窗口的决策费用和；在提出最优性质和参数分析的基础上，给出了相应的多项式时间算法．
作为上一章的推广，第五章研究有界的同时加工排序问题．当提前和延误惩罚系数是任意整数且窗口位置待定时，把3-划分的一个实例转化到该问题，从而证明了它是强NP-完备的．进而提出几个最优性质，但最优排序已不再满足SPT-批序．
进一步，本章解决了三种特殊情况．首先，当所有的提前惩罚为零时，问题转化为有待定的公共交货期问题，但它仍是NP一完备的，本文给出了拟多项式时间算法．如果交货期窗口的定位费用为零，其位置可以取任意大的值．通过使得准时集合能避免最多惩罚以达到最优，得到了拟多项式时间算法．这也说明以上两个特例是一般NP一完备的．另外，当所有的提前惩罚相等、延误惩罚也相等时，准时批包含那些最小的工件，算法5-3在O(max{b<2>n，nlogn})时间内得到最优排序．以上结果也推广了[86]中的结论．
现实生产中有以下情形：具有相似特征的一些工件需要相同的生产场景和设备，所有工件被分成多个组，于是从加工一个组的工件转化到加工另一个组的工件时需要执行安装任务．正是由于安装任务的介入使得问题更加困难． [78]讨论当交货期窗口给定时以最小化赋权提前时间和延误时间总和的问题；即使当e=0时，问题的复杂性未知．但是此类生产环境普遍存在，于是第六章继续讨论，目标函数是关于提前和延误的工件个数，其中交货期窗口的位置待定或者位置和大小均待定．
显然，第一个安装任务在零时刻开始，而且在整个工件与安装任务的序列中没有空闲时间．性质31～34描述了一个最优排序的结构；算法6-1中综合考虑工件对总惩罚的贡献而确定其所在的集合．
而当交货期窗口的位置和大小都是决策变量时，除了以上提到的性质，最优算法又基于以下结论：
性质23如果δ<γ，则最优排序中e=0．
性质25最优排序σ中，如果δ>，γ+α且e≥1，则K=0．
推论4在最优排序σ中，如果，γ<δ<γ+α且e≥1，则K等于1加上W(σ){J<,e>}中工件和安装任务的运行时间总和．
第七章把窗时排序推广到了多台平行机上，以最小化提前和延误赋权工件数，乃是准时排序和单机排序的推广．它是强NP-完备的．当交货期窗口的定位费用为零时，根据多背包问题的算法得到PTAS．若定位费用不是零，在确定了各机器上的提前集合后也类似地得到PTAS．
概括地讲，本文的创新点主要有：
1．多个工件可以同时被加工，并把同时加工的工件视为一个批，目标函数是关于提前时间和延误时间的总惩罚；本文首次把窗时排序和同时加工排序结合起来；
(1)当批容量无界时，对于交货期窗口给定及其位置待定两种情况，分别给出了多项式时间算法；
(2)当批容量有界且交货期窗口给定时，问题是NP-完备的，并对两个特殊情况分别给出了PTAS和多项式时间算法．从而推广了[52]中的结果．
2．当目标函数关于提前和延误的赋权工件个数时，(1)针对交货期窗口的位置和大小是给定还是待定的生产场景，解决了除[86]中所述之外的三种情况；
(2)将[86]中的结果推广到了同时加工排序，证明了当惩罚系数是任意整数时，问题是强NP-完备的；然后对三个特例得到拟多项式时间算法或者给出有效算法；
(3)讨论成组分批排序的情形． [78]曾对第一类目标函数进行了探讨，但问题的复杂性并未解决．本文就第二类目标函数研究，在给出几个结构化性质的基础上得到多项式时间算法；亦是[86]的推广；
(4)在多台平行机上加工且交货期窗口的位置待定，分别就其定位费用为零和非零两种情况分别给出了PTAS．