丁际环[1]2001年在《分批排序问题及带机器准备时间的同类机排序问题》文中进行了进一步梳理论文包括叁部分，序言介绍了一些背景知识；第一部分研究了单台批处理机器、工件带有到达时间以完工时间之和为目标函数的排序问题。证明了当工件有两类到达时间时，这一问题，即问题是NP-完备的，并给出了此问题的一个2-近似算法；对问题的一般情形，即问题给出了(1+B)-近似算法。第二部分主要研究一类带机器准备时间的阴台同类机在线及半在线排序问题，即问题。对此问题的在线模型给出了LS算法的两种最坏情况界分析，最坏情况界分别为和，并且当m=2和3时LS算法为最好的在线算法。对问题的特殊情形，即当时，证明了LS算法的最坏情况界为，并且界是紧的；对问题的已知加工时间递减的半在线模型，证明了LS算法的最坏情况界为并且上述各最坏情况界对最大机器完工时间和最大工件完工时间两种目标函数均成立。
柏庆国[2]2005年在《单机在线分批排序和平行机半在线排序问题》文中指出排序论又称时间表理论,其作为运筹学的一个分支,作为一门应用科学,有着深刻的实际背景和广阔的应用前景。而其中的在线分批排序以及带机器准备时间的半在线问题,因其明显的实际意义,吸引了国内外许多学者。本文主要研究了这两类问题。 论文分叁章来叙述。 第一章是引言,主要介绍了排序的生产背景发展、及其一些相关的基本知识。 第二章主要研究了工件有尺寸的单机在线分批排序(叁元素表示法表示为1|r_j,B,s_j|C_(max))及同类机在线分批排序(Q_m|r_j,B|C_(max))。对于这两类问题,目前很少有人涉及。工件有尺寸的单机在线分批排序是指工件不但有不同的加工时间而且有不同的尺寸。假定机器的尺寸为B,若工件J_j的尺寸(s_j)大于B/2则称此工件为大工件否则称为小工件。若每一大工件的加工时间不小于任何一小工件的加工时间则称此问题为工件加工时间和工件尺寸一致的排序问题,简称一致性排序。 本章第一部分我们将分批时只考虑工件个数的单机在线分批排序问题([25])推广到工件有尺寸且所有工件有两个到达时间的一致性单机在线分批排序问题,并且给出了一个竞争比不超过33/14的算法。 第二部分讨论了工件有尺寸的一般情形的单机在线分批排序问题并给出了一个竞争比不超过161/60的算法。 本章最后对于分批时只考虑工件个数的单机在线分批排序问题([25])推广到m台同类机的情形,设计了一个在线算法并证明了此算法的竞争比为1+sum from i=1 to m-1 b_i/b_m。 第叁章讨论了两台机器上知道工件的最大加工时间和工件加工时间总和两种半在线模型,此时目标函数是极小工件完工时间。用叁元素法可表示为P_2,a_j|P_(max)|
王琳[3]2003年在《单机分批排序和平行机在线排序问题》文中指出排序问题有深刻的实际背景。无论在工农业生产，还是在国防、科研、交通运输以及各种服务行业，每天都会遇到它。排序问题是运筹学的一个较年轻的分支，而其中的分批排序以及在线排序问题，因其明显的实际意义，更是吸引了国内外许多学者。本文主要研究了这两类排序问题。 论文共分叁章。 第一章(绪言)主要介绍了排序的产生背景、发展及其一些相关的基本知识。 第二章研究了目标函数为sum from j=1 to n (w_j V_j)的批处理问题。模型为：一台批处理机要加工n个工件，已知每个工件的加时间p_j，权重w_j以及交货期d_j，问怎样分批，怎样排序，使得目标函数sum from j=1 to n (w_j V_j)达到最小。我们把此问题记为1｜B｜sum from j=1 to n (w_j V_j)。 若给定一个排序，我们可以很容易地得出每个工件J_j(j=1，2，…，n)的完工时间C_j及其迟后工程V_j=min{T_j，p_j}，这里T_j=max{C_j-d_j，0}。迟后工程V_j是工件J_j在其交货期d_j之后加工的部分。若V_j=0，说明工件J_j是提前完工的；若0＜V_j＜p_j，则工件J_j是部分提前完工的；而若V_j=p_j，则说明工件J_j是在其交货期d_j之后才开始加工的。 Potts等[31]证明了1｜｜sum from j=1 to n (w_j V_j)即使w_j=1时也是NP-完备的，由此我们知道1｜B＜n｜sum from j=1 to n (w_j V_j)是NP-hard的。而B≥n是一个比较有趣的情形，Lee和Uzsoy对于单机分批排序问题在这种情形下只要到达时间个数为常数最大完工时间极小化问题是多项式可解的(见[4])；Deng和Zhang在这种情形下证明了分批排序问题有到达时间的时候极小化完工时间和是NP完备的，对于这种情形的在线情况他们给出了竞赛比(competitive ratio)为 曲阜师范大学硕士学位毕业论文 iiiIG18的算法（见问）在这种情形下，表面上看似所有工件一批就可加工，事实上由于工件的性能不同可能造成目标值加大。本文我们则是证明在这种情况下问题的NP完备性。 定理2二 问题1h二0；B叁叫二广；。。二是＊厂完备的。 为证明该问题是NP一完备的，我们将证明着名的二划分问题可多项式变换到该问题． 给定二划分问题的一个实例如下： 已知一个m个正整数组成的集合G一切1，…，··，。。），问是否存在c的一个子集X，使得 ＿IH 3 O。＝A＝＊3 a。 e－“Zrt－ JEX j＝1 我们构造一个排序模型；可多项式变化到二划分问题，从而证明了问题1卜一0；BZ叫二广；K的＊P完备性． 第叁章首次提出并研究了带机器准备时间的平行机在线（Oil上fill）排序问题，这里工件是可打断的（l＞r。。mPtive）。具体模型为：。n台平行机＊；；…；从。需加工 n个工件人；…；人，每个工件是在线到达（oneb，olle）且可打断的，机器人人的准备时间为az，怎样安排加工顺序，使工件的最大完工时间（makesPan）尽可能地小，称此问题为带机器准备时间的平行机在线排序问题。它是带机器准备时间的平行机排序和平行机在线排序问题的综合和推广；具有广泛的应用背景。 这里工件在线到达（one by one）指的是工件的情况并不是提前知道的，只有将工件 Jj人安排完以后我们才能知道工｛＋ Jj的一些情况p工件的加工时间P。等厂工件是可打断的，也就是说，工件在加工过程中可以被中途打断，然后过一段时间或立即可以在同一台机器或另外一台机器上继续加工，并且总的加工时间不变。但任一工件不能被两台机器同时加工。tV 曲阜师范大学硕士学位毕业论文 首先我们先给出一些记号：设 。x” 七时刻：排完第七个工件后的时刻， ＊：M刻机器地要加工完已排好的工件所需的时间， Q：＝t：＋ah OPT‘：对工件集广，…；人）在offline下所得的最优解，LB‘为其对应的下界， S’＝C＝1Pj十二二az。 对于加工时间分别为PI，PZ；…，尸。的。个工件，若它们零时刻到达且可打断，机器有各自的速度s；与准备时间a；叁0，则机器的完工时间有叁个显然日下界：m丑；＜；＜ma。，mini＜。＜。a。十 maxi＜人＜。一ISk，（】广1＆十二动az＊二动s；，这里Ph表示前k个最大的工件加工时间之和，Sk为前k最大的机器速度之和。这样我们有 0、grwtt WWffi DK＞。。o 十＞，，山D un 二 ＂lax ＜ max a一、milla一十 max——。＿＞ic上．1） 1195。151s。ISks。－lbk＞．二ISll 下面我们给出算法过程中必须满足的条件： k）在任一日亥u t，以叁＊ 叁…叁＊； O）在任一＊亥u t，QX＜ rLB’； 忆）在任?
唐国春[4]2006年在《2003年到2005年排序(调度)学科在中国的发展(I)》文中提出介绍2003年到2005年9月我国(包括内地和港澳台地区)排序(调度)论研究的概况和发展;综述正式发表的排序(调度)论研究的论文和专着;提供研究现代(新型)排序(包括可控排序、成组分批排序、在线排序、同时加工排序、准时排序和窗时排序、机器不同时开工排序、资源受限排序、随机排序、模糊排序和多目标排序等)、其他排序(包括经典排序和其他新型排序)、与排序有关的问题以及排序(调度)论应用的情况;内容分为正文、参考文献和附录:英汉排序(调度)词汇。材料由中国运筹学会排序分会各位委员提供,唐国春负责撰写,分I,II两部分,两次刊登;简写稿发表在《2006年中国科学技术蓝皮书》。
武光华[5]2010年在《可拒绝排序和两台同类机半在线排序问题》文中认为排序论,也可被称为时间表理论。它作为运筹学的一个重要部分,是一门应用性很强的科学,它有着很深的现实背景和广阔的应用前景.本文主要研究了两类可拒绝和一类半在线的排序问题。经典的排序模型中,人们往往假定机器必须加工所有的工件且它们的加工时间都是给定的。然而在许多现实应用中,如果某个工件加工时间或加工费用很大,我们就会考虑是否要加工该工件。我们既可以选择付出一定的费用而拒绝加工该工件也可以选择不付费而加工它。目标函数不再是传统的极小化最大完工时间,总完工时间,最大延迟等,而是同时考虑时间与费用.我们称这种排序为可拒绝排序.在大多经典排序理论中,排序问题被划分成离线和在线两种.如果工件的所有信息被提前告知,我们称它为离线的。相比之下,如果工件信息没有被提前告知,而是逐个到达,且要求该工件一旦到达便马上排序,然后下一个工件的信息才被释放,我们称这种排序为在线排序。最近几年,因为生产生活的需求,半在线(semi on-line)模型逐渐得到人们的重视。半在线排序是指早已安排好的工件不准再移动,但是在排序前早已经知道后面工件的些许信息,例如已知工件的最大加工时间等等.论文共分为叁章.第一章是本文的绪论部分,主要介绍排序问题的由来、研究现状及一些必需的预备知识,并且介绍了本文的主要研究成果.第二章考虑的是两种带拒绝费用的排序问题,目标函数是在不超过总拒绝费用阀值的前提下使总完工时间和最大完工时间最小.首先,我们证明了问题都是NP-难的。然后我们针对这两个问题设计出了两个伪多项式时间的动态规划算法和FPTAS.第叁章考虑的是带机器准备时间的两台同类机已知工件最大加工时间的半在线排序问题,讨论了极小化最大工件完工时间这个目标函数,并给出了一个竞争比为分段函数的近似算法.
刘嘉诚[6]2007年在《关于同类机半在线排序问题的若干研究》文中认为所谓排序，就是在一定的约束条件下对工件和机器按时间进行分配和安排加工次序，使一个或多个目标达到最优。它可以分为经典排序和现代排序。相对于经典排序而言，现代排序是非经典的、新型的排序。近几十年来，有关现代排序的研究有了很大的发展，新的排序模型也不断涌现。常见的现代排序模型有可控排序、成组分批排序、多目标排序、在线排序和半在线排序等等。第一章，主要介绍了排序的产生背景、发展，及其一些符号等相关的基础知识。第二章，考虑已知工件最大加工时间的同类机半在线排序问题，目标为极小化机器最大负载．对于叁台特殊同类机问题，当s_1=s_3=s≥1=s_，并且最大加工时间已知时，给出了竞争比不大于4s+2/3s(1＜s≤2)和3s+1/2s(s＞2)的半在线算法。第叁章，讨论了两台同类机的半在线问题，目标为极小化工件最大完工时间。对已知所有任务总加工时间和最大任务加工时间的半在线问题，给出了竞争比为4s+2/3s+2的最优半在线算法。
马英[7]2010年在《考虑维护时间的机器调度问题研究》文中研究说明传统的机器调度问题通常假定在整个调度期内机器一直可用。然而,在实际生产过程中,为了减少因机器失效或机器故障而导致的产品质量下降、维护成本增加和生产效率降低等问题,企业一般都会在调度期之前预先安排机器维护,因此在调度问题中考虑这种预防维护时间更具现实意义。本文首先较为详尽的研究了考虑维护时间的单机调度问题,包括维护时段固定且加工时间恒定、维护时段固定且加工时间可变、维护时段可调且加工时间恒定以及维护时段可调且加工时间可变等四类问题。对于多机调度问题,重点研究了维护时段固定且加工时间恒定的问题,以此说明了把单机调度问题的求解方法拓展到相应多机调度问题的思路,其他叁类问题均可按照这种思路进行求解。受维护时段的影响,工件在加工过程中可能会被中断,基于实际生产过程中的不同情况,本文分别考虑了被中断工件可续、不可续和部分可续叁种情形。上述问题的目标函数假定为与生产效率有关的最大完工时间及(加权)完工时间和。根据问题的复杂性不同,本文给出了不同的求解方法:对于NP-难问题,本文一方面致力于设计能求解尽可能大规模问题的精确算法,另一方面,鉴于精确算法在时间和空间性能上的不足,本文也致力于构造高效的启发式算法,从而能够在合理的时间内求得大规模问题高质量的满意解;另外,在某些特殊情形下,有些问题是多项式可解的,对于这些问题,本文通过证明某种多项式时间算法能够为其提供最优解来说明其多项式可解性。具体而言,本文的主要研究内容和创新点如下:(1)对于维护时段固定且加工时间恒定的单机调度问题,研究了部分可续情形下的两种目标函数。对于最大完工时间最小化问题,简单说明了此问题的NP-难性,给出了最大加工时间优先(Longest processing time first,LPT)规则的最坏情况相对误差界,进而提出了两个基于LPT规则的启发式算法:LPT-PI和MLPT,其中LPT-PI以LPT规则作为初始解,并结合基于成对交换技术的邻域搜索对解进行改进,而MLPT通过改进LPT算法执行过程中的某一类特殊情况来得到更优的启发式解。另外,还证明了MLPT的最坏情况相对误差界,并通过大规模实验对算法性能进行了对比分析。对于加权完工时间和最小化问题,简单说明了问题的NP-难性,提出了最优解的性质,并在此基础上构造了动态规划和分枝定界两种精确算法。大量随机数据的实验结果表明这两种算法都是有效的,且不论从能解问题规模,还是从寻得最优解所需时间方面,分枝定界算法都要优于动态规划算法。(2)对于维护时段固定且加工时间可变的单机调度问题,研究了最大完工时间及完工时间和两种目标函数。证明了这两种目标函数下加工时间线性增加和线性减少时的几种可续情形是多项式可解的。对于不可续情形,重点研究了加工时间线性增加时的完工时间和问题。对于该问题,简单说明了其NP-难性,证明了最优解的性质,在此基础上构造了一种动态规划算法,鉴于此算法应用上的局限性,给出了SNPT(Shortest normal processing time)规则的最坏情况相对误差界,进而提出了一种基于SNPT规则和交换技术的启发式算法。大量算例的实验结果显示不仅算法的运行时间很少,相对误差也很小(平均相对误差和最大相对误差分别为0.082%和3.448%),并且将近有一半的算例能得到最优解,因此该启发式算法能够很高效的解决此类问题。而对于其他目标函数和加工时间函数下的不可续情形,通过分析与上述问题求解方法上的相似性,给出了其求解思路。(3)对于维护时段可调的单机调度问题,重点研究了加工时间恒定的问题,考虑了完工时间和这个目标函数。对于可续情形,给出了最优解的几个性质,提出了一种SPT算法,并证明了其最优性;对于不可续情形,简单说明了其NP-难性,提出了几个与可续情形类似的最优解的性质和SPT算法,给出了该算法最优的条件,并证明了其最坏情况相对误差界。在最优解性质的基础上,构造了一种动态规划算法和一种分枝定界算法,其中分枝定界算法的初始解是在SPT算法的基础上利用两条性质对维护时段之前的末工件和维护时段之后的工件进行交换所得,而提出的几个下界是基于维护时段固定的相应问题。实验证明了动态规划和分枝定界这两种算法的有效性及互补性。对于加工时间可变的调度问题,首先证明了其可续情形是多项式可解的,并对此问题与相应加工时间恒定问题在求解方法上的相似性进行了总结,进而给出了不可续情形的求解思路。(4)对于多机调度问题,重点研究了维护时段固定且加工时间恒定的问题,考虑了部分可续情形下的两种目标函数。对于最大完工时间最小化问题,说明了问题的NP-难性,建立了整数规划模型,并提出了两台机器上工件互换的四条性质,进而提出了一种启发式算法,该算法首先把所有工件按LPT算法进行分配,得到一个可行解,然后再重复把最大完工时间最大和最小两台机器上的工件进行互换以提高解的质量。该启发式算法和LPT算法的对比实验结果验证了此算法的有效性;对于加权完工时间和最小化问题,说明了问题的NP-难性,给出了最优解的性质,进而提出了一种动态规划算法来求得中小规模问题的最优解,另外还提出了一种基于WSPT(Weighted shortest processing time)规则和交换技术的启发式算法来解决大规模问题,实验结果表明启发式算法的平均相对误差为0.463%,最大相对误差也仅为5.094%,该算法因此不失为一种比较有效的启发式算法。在此基础上,通过比较这两个问题与相应单机问题求解方法上的异同,给出了如何把单机问题的求解方法推广到相应多机问题的思路,按照这种思路,其他的叁类多机问题即可得到解决。
张玮虹[8]2009年在《生产管理中的若干排序问题》文中研究指明排序(也称调度)问题是组合优化中一类有着重要理论意义和广泛背景的问题。本文主要研究生产管理中的两个排序问题:带机器故障的两台机求解带权误工数最小的排序问题和考虑工件加工时间和运输时间的单机在线排序问题。全文共分为四章,第一章首先介绍了与排序问题相关的一些概念以及预备知识,并概括了本文研究的背景和意义。第二章研究机器带故障中断的两台平行机排序问题,工件加工时间均为单位时间,目标是极小化带权误工工件数。当转移时间t=0时,对问题P2|D=∞,t=0, p_(ij)=1|∑w_(ij)U_(ij)给出了最优的算法。当工件转移时间t>0时,对问题P2|D=∞, t≠0, p_(ij) = 1|∑w_(ij)U_(ij),本文给出了一个多项式时间的近似算法,并证明算法解与最优解至多相差一个带权误工数。第叁章研究将加工时间和运输时间一起考虑的单机在线排序问题,目标是极小化最大的工件加工时间和运输时间之和。每个工件J_j都有一个到达时间r_j,一个加工时间p_j和一个运输时间q_j,工件加工过程中不允许被打断,工件到达之前我们不知道工件的任何信息。本章考虑工件的加工时间和运输时间满足一致性关系的模型,即工件J_i和J_j的加工时间满足pi≥pj,则它们的运输时间有q_i≥q_j,用叁参数法将问题表示为1|on-line, r_j,agreeable ( p_j , q_j)|L_(max)。本文给出了竞争比为2~(1/2)的最优在线算法。第四章总结全文并给出了今后进一步的研究方向和研究内容。
参考文献：
[1]. 分批排序问题及带机器准备时间的同类机排序问题[D]. 丁际环. 曲阜师范大学. 2001
[2]. 单机在线分批排序和平行机半在线排序问题[D]. 柏庆国. 曲阜师范大学. 2005
[3]. 单机分批排序和平行机在线排序问题[D]. 王琳. 曲阜师范大学. 2003
[4]. 2003年到2005年排序(调度)学科在中国的发展(I)[J]. 唐国春. 上海第二工业大学学报. 2006
[5]. 可拒绝排序和两台同类机半在线排序问题[D]. 武光华. 曲阜师范大学. 2010
[6]. 关于同类机半在线排序问题的若干研究[D]. 刘嘉诚. 郑州大学. 2007
[7]. 考虑维护时间的机器调度问题研究[D]. 马英. 合肥工业大学. 2010
[8]. 生产管理中的若干排序问题[D]. 张玮虹. 浙江理工大学. 2009