姚永辉[1]2017年在《最小化最大运输完工时间和最大流程的在线排序问题》文中提出排序论是运筹学中最有活力的领域之一,大量不同机器环境下的排序模型已经被学者们广泛研究.我们根据工件的不同特点,排序问题分为离线排序和在线排序.在离线排序问题中,工件的所有信息是在排序之前就已经知道的.而本文所要研究的是按时在线排序问题,也就是指工件的到达时刻,加工时间等只有在到达之后才被了解,决策者只能根据当前已到达工件的信息来进行排序决策.在LKβ模型下,在时刻t,在线算法能预见到将在时间区间(t,t + β]内到达的所有工件的信息;不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工.分批排序模型按分批方式的不同分两大类:平行分批排序模型和继列分批排序模型.平行分批排序是指多个工件可以放在同一批在一台机器上同时开工同时完工,每一批的加工时间等于该批中工件的最大加工时间.继列分批排序是指一批中的工件是相继加工的,它们的完工时间等于批中最后一个工件的完工时间.每批的加工时间等于该批中所有工件的加工时间之和.批容量b是指每批至多可以加工b工件,一般分为有界和无界两种情形.本文我们研究的是几种特殊的在线分批排序问题,研究的模型用三参数法表示记为:(1) 1|online, p-batch,pj = 1,b = ∞, LKβ|Dmax(= maxj{Cj + qj});(2) 1|online,p-batch,pj = 1,b = ∞,f-family|Dmax(= maxj{Cj + qi});(3) Pm|on-line, s-batch|Fmax(= maxj{Cj - rj})模型(1)的基本描述:在该问题中,我们研究的是具有前瞻区间和运输时间的单机无界平行分批在线排序问题,工件具有相同的加工时间,目标是最小化最大运输完工时间.对于我们研究的模型,在本文第二章中给出了该问题的一个在线算法:当0 ≤ β ≤1/6时,该算法是竞争比为1+α*的最好可能的在线算法,其中α*= α是方程α2 + (β + 1)α +β-1 = 0的正根;当β> 1/6,该算法的竞争比为3/2.模型(2)的基本描述:在该问题中,我们研究的是具有f个互不相容工件组和运输时间的单机无界平行分批在线排序问题,工件具有相同的加工时间,目标是最小化最大运输完工时间.对于我们研究的模型.在本文第三章中给出了一个竞争比为1 + αf的最好可能的在线算法,其中αf是方程fαf2 + αf - f = 0的正根.模型(3)的基本描述:我们讨论了最小化最大流程时间的继列分批在线排序问题.在本文第四章中证明了当m ≥ 2时,问题Pm|on-line,s-batch|Fmax不存在竞争比小于1 + αm的在线算法,其中αm为方程αm2 + (m+ 1)αm = 1的正根;当m = 1时,问题1|on-line,s-batch|Fnax不存在竞争比小于1 + α的在线算法,其中α = (?);同时我们也证明了问题Pm|on-line,s-batch,pj=1|Fmax不存在竞争比小于1 +βm的在线算法,其中βm为方程(s + 1)βm2+(ms + m + s + 2)βm - s = 0 (βm > 0)的正根.在本章4.3节中我们尝试给出m = 1时的一个在线算法H1,并证明该算法的竞争比为2,说明了这个算法的界是紧的,在m ≥ 2时,在线算法就变得较为复杂,目前无法得知比2更好的在线算法.
酒明珠[2]2014年在《自由下线平行分批排序的计算复杂性》文中认为平行分批排序是重要的现代排序模型之一.其特点是多个工件可以放置在同一个工件批中同时进行加工,每个工件批的加工时间就等于该批中工件的最长加工时间.工件批中最多可以放置的工件数称为批容量,记为6.b=∞的情形称为无界模型,而b<n的情形称为有界模型,其中n表示工件总数.传统的平行分批排序中假设同一批中的工件具有相同的开工时间和相同的完工时间.也就是说,如果工件批β的开工时间为S,加工时间为p,则工件批β中所有工件的开工时间均为S,完工时间均为S+p.工件可自由下线的平行分批排序突破了传统的平行分批排序的假设,并对工件定义了新的完工时间.如果工件批β的开工时间为S,则工件批β中任一工件Ji的开工时间定义为S,而完工时间定义为S+pj,其中pj是工件Jj的加工时间.利用三参数表示法,工件可自由下线的平行分批排序问题可以表示为1|pbatch,b,rj,drop-line|γ工件可自由下线的平行分批排序在集装箱运输以及信息技术等领域都有着广泛的应用.然而,文献中对这一专题的研究才刚刚起步.本文在前人工作的基础上对工件可自由下线的平行分批排序问题的计算复杂性进行了研究.主要结果如下：·问题1|p-batch,b<n,drop-line|∑Cj可以在O(nb(b-1))时间内求解.·在限制恰好分K=[n/b]个工件批的前提下,问题1|p-batch,b<n,drop-line|∑Cj可以在O((nK-1)K log K+n log n)时间内求解.·问题1|p-batch,b<n,drop-line,SPT|∑Cj可以在O(bn+n log n)时间内求解.·问题1|pbatch,b=∞,rj((?)),drop-line|∑fj可以在O(n2PP2)时间内求解,其中P=maxj rj+∑jpj.·问题1|p-batch,b=∞,rj((?)),drop-line|fmax可以在O(n3log P)时间内求解,其中P=maxjrj+∑jpj.
李文华, 原晋江, 林诒勋[3]2007年在《批数确定的分批排序问题最优解的结构性质》文中提出研究了目标函数为总完工时间、工件恰分N批的单机分批排序问题最优解的结构性质,其中N为1与工件数之间的任意整数.分批方式为继列分批和平行分批.
易杰[4]2016年在《成组排序与重新排序问题研究》文中指出排序,一般就是要在满足给出的加工约束条件下,给定一个合适的加工顺序,使得待加工工件以给定顺序加工时能够使得一个或者多个目标函数达到最优.成组和分批,其实是柔性制造系统发展过程出现的能够显著提高工作效率的新技术.重新排序则是为了解决生产计划确定后、实际生产前,生产计划被一些突发状况(计划取消、插入或延后等)打乱,需要重新安排合适的生产计划的情况.本文分别研究了以下几个问题:成组重新排序、基于一般学习效应的重新排序以及重新分批排序.具体分为以下几个部分:第一部分中,我们研究了在最大错位的限制下,目标函数为最小化总完工时间的成组重新排序问题.其对应的模型如下:第二部分中,我们考虑了一类特殊的重新排序问题——基于一般学习效应的重新排序问题.在最大序列和总序列的错位限制下,研究了基于一般学习效应且目标函数为最小化总完工时间的重新排序问题.其对应的模型如下:第三部分中,我们考虑了分批重新排序问题,但此问题中“重新”的意义与上两部分的有所不同.其对应的模型如下:本文通过研究这些模型的结构性质,给出了对应的算法及算法可行性和最优性的证明.
赵晟珂[5]2008年在《管理运筹学中的两个问题》文中研究表明运筹学在经济管理领域有广泛的应用．众所周知，运筹学研究的根本目的在于对资源进行最优化配置，用数学的理论与方法指导社会管理，提高生产效率，创造经济效益．管理科学的初衷也同样是为了解决对于有限资源的有效使用问题，因而将运筹学的方法运用到经济管理中，将现实问题归结为数学问题，通过数学模型的建立来解决管理最优化问题具有重大现实意义．对策论和排序问题均是运筹学研究领域的热门问题，在经济管理方面有着坚实的应用背景和深刻的理论意义．本文基于这点，结合社会及生产管理中存在的问题，运用运筹学的方法对两个管理问题进行了探讨．本文共分为三章．第一章由三部分组成．前两部分分别就对策论和排序问题的来源、研究的背景及研究现状进行了简单介绍．最后则对本文的主要研究成果及创新点进行了简要论述．第二章从对策论的角度出发，针对我国当前医疗体制改革的现状，通过建立和求解对策模型从而得到一些有益的启示．我国当前的医疗体制改革正处于探索阶段．目前，国内对这一问题的研究大多单纯从管理学的角度入手，而利用对策论的相关理论与方法从数学的角度进行研究本文尚属首次．本文主要利用建立的对策模型对医疗体制改革这一重大现实问题进行了分析，探讨了医疗体制改革中所涉及的政府主管部门、医疗机构、患者三方之间的制衡关系及影响因素．并分别就政府主管部门的监管、医疗机构自身的管理和社会诚信制度建设等管理方面存在的问题给出了一些有益的建议．第三章研究了两类同类机分批排序问题．产生于上个世纪九十年代的分批排序问题是半导体生产管理的一类重要问题．本文首次考虑了批处理机在有准备时间的条件下，目标函数是加权总完工时间的排序模型，即Q_m，R_i|B，p_j=p|∑w_jC_j、Q_m，R_i|B，p_j=p，r_j∈{r_1，…，r_k}|∑w_jC_j两个问题．并在已有的FBLW(fully batch largest weight)和ECT(earliest completion time first)算法的基础上提出了两个新的算法，并证明了该算法可以给出所研究问题的一个最优排序，并且其运行时间分别为O(n log n)和O(2~(mT)n log n)，即关于该问题的一个多项式，因而说明所给出的算法是解决其问题的最优算法．
王磊[6]2008年在《可控分批排序及供应链排序问题研究》文中认为排序问题是一类重要的组合优化问题,有着深刻的实际背景和广阔的应用前景,它广泛应用于管理科学、计算机科学、工农业生产、交通运输等许多领域,已经取得了许多有意义的成果.分批排序和可控排序是两类很重要的现代排序模型,本文中把这两类排序模型相结合,讨论加工时间离散可控的单机分批排序问题.另外,对于近年来出现的将供应链管理和排序理论相结合的供应链排序问题,对于其中一个模型,考虑了平行机分批配送问题.论文共分三章:第一章首先介绍了排序问题的应用背景及问题描述,然后给出了必要的预备知识,最后概述了本文研究的主要问题及研究结果.第二章主要讨论加工时间离散可控的单机分批排序问题:分别考虑机器容量有限及无限两种情况下,分别使最大完工时间和总完工时间加上加工时间可控所需费用的总和为最小作为优化的目标,讨论了这四个问题的最优解的性质,并在此基础上提出了相应的多项式时间最优算法.第三章主要讨论平行机分批配送问题中的一个模型,首先指出该问题是强NP-hard的.如果工件满足一致性假设,本文给出了一个伪多项式时间的动态规划算法.最后,对于两种特殊情形给出了多项式时间最优算法.
金世国[7]2007年在《几类特殊的分批排序问题》文中指出平行分批排序和在线排序是两个发展比较迅速的排序模型。平行分批排序是指机器可以同时加工多个工件，每批包含的工件同时开工同时完工，批的加工时间是这批工件中加工时间的最大者。在线排序是指工件信息在其到达之前是一无所知的，并且一旦工件被安排后就不允许再改变。本文主要考虑了几类特殊的分批排序问题。首先研究了工件具有相容约束的带有运输的单机平行分批排序问题。在这里，我们有一台批处理机和充分多的车辆。有n个同工时的工件J_1，J_2…，J_n，每个工件的加工时间为p，运输时间为q_j．这些工件间有的工件可以在同一批中加工，而有的则不能在同一个批中加工。一批完工后并行地运输。这里的目标函数是工件最后运达顾客的时间。我们把这些工件分别对应于一个图G中不同的顶点，如果工件是相容的，则图G中对应的顶点间就可以连边，否则就不连边。通过这一转换，我们就把工件的相容性约束通过图论中具体的团来刻画，从而使解决相容性约束条件下的排序问题显得更加直观。于是我们所考虑的模型可记为1|p-batch；p_j=p，q_j；G|D_(max)，其中，图G就是代表我们所讨论的工件相容约束性，D_(max)=max{D_j|D_j=C_j+q_j，1≤j≤n}。由张群发的硕士学位论文[8]可知1|p-batch；p_j=p；G|C_(max)是NP-困难的，从而我们的问题亦是NP-困难的。相容约束图限定为某些特殊图类时，本文给出了多项式时间算法。主要结论如下：(1)相容约束图G限定为分裂图时，文中给出了问题1|p-batch；p_j=p，q_j；G|D_(max)的时间界为O(n~2)的最优算法。(2)相容约束图G限定为完全二部图时，文中给出了问题1|p-batch；p_j=p，q_j；G|D_(max)的时间界为O(n log n)的最优算法。(3)相容约束图G限定为完全m部图时，文中给出了问题1|p-batch；p_j=p，q_j；G|D_(max)的时间界为O(n log n)的最优算法。(4)相容约束图G限定为直径不超过4的树时，文中给出了问题1|p-batch；p_j=p，q_j；G|D_(max)的时间界为O(n log n)的最优算法。其次，本文对带有禁用区间的目标为最小化最大完工时间的单机平行分批排序问题进行了研究。在经典排序中，所有机器都是假设在整个加工过程中一直可用。然而，这个假设往往太过理想，在实际生产过程中，情形可能并非如此。由于对机器的预防性维修或机器突然出现故障都会导致机器在某一段时间内不能使用，有时候我们也把机器不能使用的这一段时间叫做机器的禁用区间。我们假设机器的禁用区间是在工件就绪前已经确定的。工件就只能在剩下的时间内加工。文中考虑两种禁用情形：若一个批在禁用区间之前未能完工而它在机器重新可用后可以接续加工，这种情形称为可继续的，用记号r-a来表示；若该批不可接续而只能重启，即从头开始加工，我们称为不可继续的，用记号nr-a表示，这是借文献[10]的用法。本文对离线情形，要么给出了多项式时间算法，要么给出了近似算法；对一般在线情形，给出了其竞争比的下界可任意大的证明，并对特殊情形给出了最好可能的算法。本文最后对带有强制工件的单机在线分批排序问题进行了讨论。这里所有工件都是在线的，但是，其中有一些特殊工件，它们要求单独成批，其它工件不能与其共批，并且一旦到达就要对其立即加工，我们称其为强制工件(master job)，其它工件称为自由工件。假设强制工件间不冲突。该模型可记为1|master job；p-batch，b；on-line,r_j|C_(max)，文中考虑了和强制工件相冲突的批可中断(pmtn)与需要重启(restart)两种情形，主要结果如下：(5)给出了问题1|master job(restart)；p-batch，b=∞；on-line．r_j|C_(max)的竞争比下界及最好可能算法。(6)给出了问题1|master job(restart)；p-batch，b＜n；on-line，r_j|C_(max)的竞争比下界及最好可能算法。
王成飞[8]2008年在《带配送时间的在线分批调度问题》文中提出排序问题是一类重要的组合优化问题，它被广泛应用于管理科学、计算机科学、工农业生产、交通运输等许多领域，一直受到国内外学术界的重视．分批排序问题和在线排序问题是两类新兴的现代排序模型，有着重要的应用背景，而带配送时间的在线分批排序问题是排序论在供应链理论中应用的重要体现．本文主要研究带配送配送时间的在线分批排序问题．论文共分为三章：第一章主要介绍了排序问题产生的背景，计算复杂性理论，分批排序，在线与半在线排序的概念以及本文的主要结果和创新点．第二章主要对分批加工在两种配送模型下的在线算法进行了分析．这两种模型分别为：分批加工、独立配送模型以及分批加工、按批配送模型．首先证明了在独立配送模型下我们考虑的两个问题的竞争比均为1+δ，其中δ＝(?)；并首次提出了独立配送模型下的一个半在线理论；首次提出了一种新的配送模型：按批配送模型，并对按批配送与独立配送的同一个算法的竞争比进行了分析．第三章首次研究了成比例排序问题BPP的同类机分批排序，目标函数为极小化工件的最大完工时间，这类问题也是NP--完备的．我们对同类机的情形给出了近似算法QBFF和QM，并且证明了它们的竞争比分别不超过兰b/a+1(其中a=min{a_j})和3/2+ρ(其中ρ=(m-1)S_1/(?)S_j)．
焦峰亮[9]2008年在《单机双目标分批排序中的几个问题》文中研究说明排序论又称时间表理论，已经发展成为运筹学的一个重要分支，作为一门应用科学，它有深刻的实际背景和广阔的应用前景。分批排序问题、多目标排序问题是近年来新兴起的两类现代排序模型，因其显著的现实意义，更具研究价值。本文将以上两种现代排序模型相结合，讨论了几类特殊的单机双目标分批排序问题。论文主要结构安排如下：第一章(绪论)首先介绍了排序问题的应用背景及问题描述，然后给出了必要的预备知识，最后概述了本文的主要研究结果。第二章主要研究了两类批容量无限的单机双目标平行分批排序问题模型：约束模型与线性加权模型。目标函数主要涉及一些常见目标函数，如C_(max)，L_(max)，∑w_jC_j等的组合，通过动态规划就相应问题分别给出了多项式时间算法，并作了时间复杂性分析。最后我们证明在本文约束模型解决前提之下，问题对应的主次指标模型也可相应解决。第三章主要研究了平行分批排序问题(p-batch)中一类主指标为∑w_jC_j，次指标为C_(max)的主次指标排序问题。首先讨论了单机上批容量无限模型(b≥n)，通过动态规划给出了一个多项式时间算法，并分析了算法时间复杂性；然后对m台同型机上批容量有限模型(b<n)且所有工件的加工时间都相等的这一特殊情形，给出了一个近似算法，并证明了算法的最差性能比为2-1/m。
何程[10]2009年在《多目标分批排序及其相关课题》文中认为在过去的50年中,机器排序问题已成为组合最优化中最活跃的研究课题之一。然而,在大多数经典的排序文献中,只考虑机器一次至多加工一个工件,且目标函数只有一个。随着时间的推移,分批排序和多目标排序已蓬勃发展起来。可是将两者(分批排序和多目标排序)结合起来的研究尚不多见。由于电子加工业及其它产业的高速发展,以及决策者的不同利益需求,将分批排序与多目标排序结合起来考虑,应该提到议事日程上。设n个无关的工件J_1,J_2,…,J_n,它们将在一台分批处理机上加工。工件J_j的加工时间、工期、期限和权分别为p_j、d_j、(?)_j和w_j(j=1,…,n)。以S_j和C_j分别表示工件J_j的开始加工时间和完工时间。给定一个序σ,L_j(σ)=C_j(σ)—d_j与L_(max)(σ)=max_(j=1)~n L_j(σ)分别表示工件J_j的延迟与序σ的最大延迟。T_j=max{0,L_j}为工件J_j的延误,U_j为它的单位惩罚因子。本论文主要考虑分批处理机上同时最小化双目标排序问题。所谓的分批处理机是指机器可同时加工多个工件,放在一起加工的工件集称为一批,同一批中的工件具有相同的开工时间和完工时间。根据批的加工时间的不同定义,分批处理机又分为平行分批处理机和序列分批处理机。对前者,一批的加工时间等于这一批中最长工件的加工时间。这一模型是由半导体加工的烘烤、计算机系统及其它领域的操作抽象而来的。对后者,一批的加工时间等于这一批中所有工件的加工时间之和,且在每一批加工开始前,都有一个常数s的安装时间。这一模型起源于现实生活中这样的要求:当一批工件加工完成后,需要一段时间来调换工具、维修机器等。另一方面,两个目标函数可以代表两个决策者的不同利益。这一方向发展的基本动机源于这样的事实:质量评估通常是一个多维概念。并且决策者常常追求多个目标同时最优化一对所有目标函数找出全部的Pareto最优序。称一个可行序σ是关于目标函数f和g的Pareto最优序,是指不存在可行序π,使得f(π)≤f(σ),g(π)≤g(σ),且其中这两个不等式至少有一个严格成立。本学位论文的主要研究成果如下:1.单机平行分批的双目标排序前人分别对双目标及平行分批两方面已得到一些结果。例如,证明了同时最小化最大延迟和最大费用函数的单机排序问题可在O(n~3log n)时间内解决。在平行分批处理机上,当机器容量无界时,最小化最大延迟问题已有O(n~2)时间的动态规划算法。而我们考虑两方面的结合,即同时最小化最大延迟和最大完工时间的平行分批排序问题,并给出一个O(n~3)时间的多项式时间算法,可以求出全部Pareto最优解。对多目标优化问题而言,求出全部Pareto最优解是最完整的解答。另外,当机器容量有界,且工件的加工时间为常数时,以总延误为主指标,次指标分别是误工工件数、加权误工工件数和加权总完工时间的分层最小化问题已有O(n~3)时间算法。我们统一地给出O(n log n)时间算法,改进了上述时间界。2.单机序列分批的双目标排序对于序列分批的单目标排序问题,当机器容量无界时,最小化最大延迟问题已有O(n~2)时间的算法;最小化加权总完工时间也已有了O(n)时间的算法。对于双目标问题,没有已知结果。我们在O(n~2)时间内解决了同时最小化最大延迟和最大完工时间问题。此外,对同时最小化最大完工时间和总完工时间问题,在机器容量无界或有界的情形下,我们分别给出O(n~2)时间算法。以上算法均可求出全部Pareto最优解,获得完全的解答。3.单机双目标排序已知最小化具有截止时间的误工工件数问题是NP-困难的。对如下特殊情形的误工工件数问题,文献中已有O(n~2)时间的后向算法。(ⅰ)如果d_j≤d_j,那么(?)_i≤(?)_j与P_i≤P_j;(ⅱ)如果P_i≥p_j,那么d_i—d_j≤p_i—p_j。为建立统一的理论,我们提出了一种对偶算法一前向的贪婪算法,对情形(ⅰ),它有更好的时间界O(n log n)。对情形(ⅱ),得到相同的时间界,但方法有不同特点。并且我们还研究了工件加工时间相等的情形,也找到了O(n log n)时间算法。因为不同的决策者对同一个工件的工期要求可能不同(它们分别代表各自的期望利益),所以可设每一个工件J_j具有两个工期d_j~((1))和d_j~((2))(1≤j≤n)。这样,对一个给定的序σ,就诱导了两个目标函数最大延迟L_(max)~((1))与L_(max)~((2))。我们证明同时最小化关于两个工期集合的最大延迟问题可在O(n~3 log n)时间内解决,求出全部Pareto最优解,且时间界是紧的。
参考文献：
[1]. 最小化最大运输完工时间和最大流程的在线排序问题[D]. 姚永辉. 郑州大学. 2017
[2]. 自由下线平行分批排序的计算复杂性[D]. 酒明珠. 郑州大学. 2014
[3]. 批数确定的分批排序问题最优解的结构性质[J]. 李文华, 原晋江, 林诒勋. 郑州大学学报(理学版). 2007
[4]. 成组排序与重新排序问题研究[D]. 易杰. 河南工业大学. 2016
[5]. 管理运筹学中的两个问题[D]. 赵晟珂. 曲阜师范大学. 2008
[6]. 可控分批排序及供应链排序问题研究[D]. 王磊. 曲阜师范大学. 2008
[7]. 几类特殊的分批排序问题[D]. 金世国. 郑州大学. 2007
[8]. 带配送时间的在线分批调度问题[D]. 王成飞. 曲阜师范大学. 2008
[9]. 单机双目标分批排序中的几个问题[D]. 焦峰亮. 曲阜师范大学. 2008
[10]. 多目标分批排序及其相关课题[D]. 何程. 郑州大学. 2009