最小化最大运输完工时间和最大流程的在线排序问题

发布时间：2019-03-09 11:17

【摘要】：排序论是运筹学中最有活力的领域之一,大量不同机器环境下的排序模型已经被学者们广泛研究.我们根据工件的不同特点,排序问题分为离线排序和在线排序.在离线排序问题中,工件的所有信息是在排序之前就已经知道的.而本文所要研究的是按时在线排序问题,也就是指工件的到达时刻,加工时间等只有在到达之后才被了解,决策者只能根据当前已到达工件的信息来进行排序决策.在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更好的在线算法.
[Abstract]:......
【学位授予单位】：郑州大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O223

【参考文献】