带配送时间的在线分批调度问题

曲阜师范大学硕士学位论文带配送时间的在线分批调度问题姓名：王成飞申请学位级别：硕士专业：数学、运筹学与控制论指导教师：张玉忠20080401带配送时间的在线分批调度问题作者：王成飞学位授予单位：曲阜师范大学相似文献(10条)1.学位论文付乳燕平行批在线排序问题2009在线排序是现代排序的一个重要组成部分.在经典的离线排序问题中，我们总是假设决策者在做决策之前已经获知所有工件的信息.事实上，在实际生产过程中很多时候决策者在没有获得所有工件信息之前就必须做出决策.于是出现了在线排序.人们通常把在线排序问题分为三类：br　　列表在线（online-list）：工件是排成一个序列到达的.前面的工件必须被安排到机器上后面的工件才会被释放出来.工件一旦被释放，工件的信息即被获知.工件的安排方式一旦确定就不可以再改变.br　　时间在线（online-time）：工件是随着时间到达的.前面到达的工件即使没有被安排也不会影响后面工件的到来.工件的信息在工件的到达时刻才能获知，工件在到达之前不可以被安排.工件被安排之后不能再改变.br　　不可预测的时间在线（online-time-nclv）：工件是随着时间到达的.工件的加工时间只有在工件完工之后才可获知，而在工件的到达时刻无法得知或预测（nonclairvoyance）.工件在到达之前不可以被安排，一旦安排就不可以改变.br　　在本学位论文中，我们主要研究的是时间在线排序问题.我们考虑一台或两台平行批处理机的排序模型.平行批处理问题起源于半导体制作工业、制平行批鞋业、金属铸造工业等方面.在后文中我们将会详细叙述.一台平行批处理机在不超过批容量的情形下，可以同时加工多个工件.批的加工时间是由该批中最长的工件确定的.同一批的工件具有相同的开工时间和相同的完工时间.在本文所研究的排序模型中，我们均假设批容量是无界的，即机器可以同时加工任意多个工件.同时，我们还假设存在多个不可相容的工件组或者假设批是允许有限次重启的.br　　不可相容的工件组是指，每个工件可能属于不同的组，组与组之间是不可相容的（比如，不同的组具有不同的化学性质）.因此，不同组的工件不可以被安排在同一批加工.br　　考虑到重启是一种有限的资源或者重启会带来一定的负面影响，因此我们提出了有限次重启的概念.批允许有限次重启是指，如果一批中不包含有已经被重启过的工件，就可以被重启.批重启之后，批中的工件被释放出来，成为各自独立的未加工工件.再次加工被重启过的工件时必须重新开始加工，并且加工过程不可以被打断直到其完工.br　　重启与中断是两个不同的概念.中断的工件再次被加工时是接着已经被加工的部分继续加工的；而重启的工件再次被加工时是从头开始加工的，前面已经加工的部分全部作废.重启只有在在线排序问题中才有意义.因为在离线排序中，我们完全可以等到适当的时候再加工工件，而不用做无用功.而在在线排序中，因为缺乏未来工件的信息，所以利用重启可以帮助决策者得到更优良的在线算法.br　　我们用竞争比来衡量一个在线算法的优良程度.对于一个最小化目标函数的在线排序问题，我们说在线算法A是ρ-竞争的（ρ1），如果对于任意的实例Ⅰ，都有A（Ⅰ）≤ρ.opt（Ⅰ），其中A（Ⅰ）是在线算法A生成的目标函数值，opt（Ⅰ）是最优的离线算法生成的目标函数值.（对最大化目标函数的在线排序问题，如果A是ρ-竞争的（ρ1），则有A（Ⅰ）≥ρ.opt（Ⅰ）.）由此可见，ρ的值越趋于1，则在线算法得到的目标函数值就越趋于离线情形下最优的目标函数值，在线算法也更优良.对某个在线排序问题来说，如果它的一个在线算法的竞争比与该问题的竞争比的下界相吻合，那么我们就说该算法是最好可能的在线算法，这也就意味着该在线排序问题彻底被解决.br　　本学位论文中我们主要考虑了六个问题.第二章和第三章研究的是单台平行批处理机带有不可相容的工件组的在线排序问题；第四章和第五章研究的是两台平行批处理机的问题；后面两章我们主要探讨了允许有限次重启的平行批排序问题，包括单机和平行机.具体地，主要结果如下：br　　1.在第二章中，我们研究了带有两个不可相容的工件组的单台平行批处理机在线排序问题.目标函数是最小化最大完工时间.我们首先证明了该问题任意在线算法的竞争比的下界是√17+3/4≈1.7808，然后我们给出了一个竞争比是√17+3/4的最好可能的在线算法.br　　2.在第三章中，在第二章研究的基础上我们扩展了已有的结果.我们假设不可相容的工件组的个数f是一个输入的数.我们找到了最好可能的在线算法的竞争比是f的一个表达式，即1+√4f+1-1/2f.当f≤2时，得到的结果与已知结果相同.需要说明的是，本章我们给出的算法是一个有别于已知的新的在线算法.br　　3.在第四章中，对于两台平行批处理机，目标函数是最小化最大完工时间的在线排序问题，我们首先证明了问题的竞争比的下界是√2，然后我们给出了一个最好可能的新的在线算法，证明了算法的竞争比与下界吻合.br　　4.在第五章中，我们探讨了带有两个工件组的两台平行批处理机在线排序问题.目标函数足最小化最大完工时间.我们用对手策略证明了该问题任意在线算法的竞争比的下界是√5+1/2≈1.618.继而，我们给出了一个最好可能的在线算法，证明的算法的竞争比就是√5+1/2.br　　5.在第六章中，我们主要研究的是单台平行批处理机，批允许有限次重启的最小化最大完工时间的在线排序问题.我们首先证明该问题竞争比的下界是3/2，然后给出了个竞争比是3/2的最好可能的在线算法.在不允许重启的情形下，最好可能的在线算法是√5+1/2-竞争的.因此批允许重启使得我们得到了史好可能的在线算法.br　　6.在第七章中，我们研究的是允许有限次重启的两台半行批处理机在线排序问题.目标函数是最小化最大完工时间.在不允许重启的情形下，最好可能的在线算法是√2-竞争的.我们证明当批允许有限次重启时，任意在线算法竞争比的下界约为1.298，在second-restart的假设下（即只有两台机器都忙碌的时候才会考虑利用重启，并且每次都是重启开工时刻较晚的正在运行的一批），问题的下界是√3+1/2.接着，我们给出了一个竞争比是√3+1/2的在线算法.在second-restart的假设下，该算法是最好可能的.2.期刊论文丁际环.曲桂东.张伟.岳丽.张玉忠带机器准备时间的同类机在线与半在线排序问题-曲阜师范大学学报(自然科学版)2003,29(3)研究带机器准备时间的m台同类机(uniformmachines)在线和半在线排序问题,目标函数为极小化最大机器(工件)完工时间.对于在线情形,证明了LS算法的最坏情况为ρ=(1+5)/2,m=2,1+2m-2/2,m≥3,并且当m=2时,LS算法是最好的近似算法;当m=2,3,...,6时界是紧的,特别地,当s1=s2=...=sm-1,sm≥1时,证明了LS算法的最坏情况界为ρ=(1+5)/2,m=2,3-4/(m+1),m≥3,而且界是紧的;对于已知加工时间递减的半在线排序问题,证明了LS算法的最坏情况界为2-2/(m+1).3.学位论文刘培海平行机上的在线排序问题研究2008本文主要研究平行机上的几个在线排序问题以及半在线排序问题。我们主要研究这些排序问题的下界、设计算法并分析算法的竞争比。全文主要分为六部分内容。第一章主要介绍了组合优化、排序问题相关的一些概念，并介绍了在线排序以及半在线排序的研究现状。第二章研究了同型机上的在线排序问题，目标为极小化所有工件的完工时间之和。这是在线排序中一个非常重要的问题，已经有了很多的研究成果。Vestjens证明了此问题的任何在线算法的竞争比不可能小于1.309，对具体的机器数m，这个结果可以做进一步改进。本文给出了此问题的一个在线算法DSPT，证明了这个算法的竞争比为2。这是目前最好的结果，也是大家一直希望得到的结果。第三章主要研究了两台同类机上的在线排序问题。两台同类机的速度分别为1和s(s≥1)。我们分别研究了不可中断和可中断两个排序模型。对不可中断的情形，我们研究目标函数为极小化完工时间之和的在线排序问题。我们证明了此问题的任何在线算法的竞争比不可能小于1.5，同时我们给出了一个2＋min(s/s＋1，1/s)—competitive的在线算法。而对可中断的情形，我们研究目标函数为极小化加权完工时间之和的在线排序问题，我们给出了一个竞争比为2的在线算法。第四章研究了同型机上带配送时间的在线排序问题，最优化准则是极小化所有工件最迟配送时间，即极小化Lmax。Vestjens[1]证明了此问题的任何在线算法的竞争比都不可能小于1.5。利用LDT(LargestDeliveryTime)算法的思想，对机器数为2的情形，我们给出了此问题的一个在线算法，并证明了这个算法的竞争比为1.618。第五章主要研究了两台同类同型机上的半在线排序问题，目标函数为极小化最大完工时间。两台同类机，假设它们的速度分别为1和s(s≥1)。工件是从一个列表中逐个释放的(overlist)。我们首先研究了一个带buffer的半在线问题。对带buffer的两台同类平行机上的半在线排序问题，我们给出了任意确定性在线算法的竞争比的下界，同时当s≥√2时，我们给出了一个竞争比为s＋2/s＋1等的最好可能的半在线算法，当1≤s≤√2，我们给出了一个2s＋2/s＋2-competitive的半在线算法。接下来，我们研究了已知工件最大加工时间的半在线排序问题。当1≤s≤1＋√17/4时，Cai和Yang给出了已知工件最大加工时间的半在线排序问题的一个2s＋2/2s＋1-competitive的半在线算法，同时他们证明了当1≤s≤1.192时，此问题不存在竞争比小于2s＋2/2s＋1的半在线算法。当s≥3.777时，他们证明了LS算法就是最优的在线算法。我们给出了一个更简单的算法，同时证明了当1≤s≤1＋√17/4时，这个算法都是最优的半在线算法。第六章研究了同型批处理机在线排序问题。一台批处理机一次可以把B个工件作为一批加工，批的加工时间由批中最长工件的加工时间决定。同一批中的工件具有相同的开工时间和完工时间。我们只考虑B=∞的情形。目标函数为极小化最大完工时间。我们给出了这个排序问题的下界1＋√m2＋4－m/2，同时我给出了一个最优的在线算法。4.期刊论文谭金芝.TANJin-zhi两台同型平行机的复合半在线排序问题-浙江大学学报（理学版）2008,35(5)研究了两台同型平行机的一个复合半在线排序问题.即对已知工件加工时间递减和实例最优值,目标为极大化机器最早完工时间的复合半在线排序模型,分析了它的下界,并给出了竞争比为9/8的最优算法.5.学位论文田记多台平行批处理机在线排序和带有运输时间的在线排序2009在线排序是近年来现代排序领域发展最为迅速的模型之一.与经典的离线排序相比较，在线排序最明显的的特点是工件的所有信息是分阶段逐步释放给决策者的，并且，决策者只能根据当前已有的信息来做排序决策.这样的特点不仅仅为研究工作带来大量的困难，而且也让研究者们产生了很大的兴趣.在工业生产和计算机系统中，在线排序都有着广泛的实际应用背景.文献中有很多关于在线排序的定义.最常见的两种是列表在线（online-list）排序和时间在线（online-time）排序.在列表在线排序问题中，工件事先排在一个列表中，并且按照列表中的顺序一个接一个的呈现给决策者.在下一个工件出现之前，决策者必须将当前工件安排在某一台机器上.工件一旦出现，决策者就知道该工件的所有信息.在时间在线排序问题中，工件是随时间到来的.每个工件的信息在其到达后决策者才被告知.在工件到达时，决策者可以不立即安排此工件.在本学位论文中，我们考虑的是后一个模型，即，时间在线排序.br　　一个在线算法的优劣往往是通过它的竞争比来衡量的.我们称一个在线算法是ρ-竞争的是指：对于任何一个实例，在线算法产生的目标函数值至多是离线情形下