带指数学习效应和凸资源分配的单机排序问题研究

【目的】研究在全部工件加工时间可变的情况下具有指数学习效应和凸资源分配的单机排序问题,其中工件的实际加工时间具有指数学习效应,并依赖于分配它的不可再生资源数量。目标是确定资源的最优分配和工件最优排序,使得最大完工时间和资源消耗费用的3种组合最优,即最大完工时间和资源消耗费用的加权和最小、资源消耗费用限制下的极小化最大完工时间和最大完工时间限制下的极小化资源消耗费用问题。【方法】对给定排序,用约束优化和无约束优化问题的最优性条件能够求得其最优资源分配。【结果】分析最优解满足的性质,证明最优解能够通过多项式时间得到,并给出了具体求解算法。【结论】算法分析表明求解算法的时间复杂度为O(nlog n),其中n为工件个数。     

基于一般时间相关和位置相关的单机排序问题研究

【目的】研究了工件加工时间、开工时间与所在位置相关的单机排序问题,以扩展这类问题的研究范围。【方法】工件加工时间是开工时间和所在位置的一般非增函数。工件开工时间越晚,加工位置越靠后,实际加工时间则越短。受相关论文的启发,对此问题用经典算法进行了讨论。【结果】目标函数为极小化最大完工时间和总完工时间的问题证明了SPT算法仍是最优算法。对极小化加权总完工时间问题分析了最坏竞争比;在正常加工时间和权重或工期存在特殊关系时对加权总完工时间和最大延迟问题证明了经典算法是最优的。【结论】对所研究的单机排序问题给出了若干结果。
     

基于一般时间相关和位置相关的单机排序问题研究

【目的】研究了工件加工时间、开工时间与所在位置相关的单机排序问题,以扩展这类问题的研究范围。【方法】工件加工时间是开工时间和所在位置的一般非增函数。工件开工时间越晚,加工位置越靠后,实际加工时间则越短。受相关论文的启发,对此问题用经典算法进行了讨论。【结果】目标函数为极小化最大完工时间和总完工时间的问题证明了SPT算法仍是最优算法。对极小化加权总完工时间问题分析了最坏竞争比;在正常加工时间和权重或工期存在特殊关系时对加权总完工时间和最大延迟问题证明了经典算法是最优的。【结论】对所研究的单机排序问题给出了若干结果。     

带有释放时间的半连续型批处理机调度问题(运筹学与控制论)

半连续批处理机调度问题,是从钢铁工业加热炉对管坯的加热过程中提炼出来的。工件按批加工,同一批中工件的加工时间等于此批中工件的最大加工时间,且工件必须按周期一个紧挨着一个进入、离开处理机。批处理机的容量为C,即最多可同时加工C个工件,批的容量为批中工件的个数,批的处理时间与批中工件的加工时间、批处理的容量和批的容量有关。本文研究释放时间与加工时间一致时,对于目标函数为最大完工时间问题,即时间表长问题,分析其最优解的性质,从而将问题转化为工件按释放时间非减顺序排列后,对工件进行分批,使得最大完工时间最小。在此基础上给出了一个复杂性为O(n2)的动态规划算法,证明了这个算法的最优性,并用数值例子进一步说明了算法的计算过程。     

带有安装时间以及可分批加工的供应链排序问题

研究了单制造商多客户的供应链排序问题;同一客户的工件可以分批进行加工,不同客户的工件不可以在一批中加工;当相邻的两批工件属于不同客户时则需要相应的安装时间.以生产和运输总费用最小为目标函数,建立了集成排序模型;分别用工件的加权总完工时间和最大延迟作为排序目标,采用动态规划的技巧给出了最优算法,并分析算法复杂性.     

链式约束下的一种半连续型批处理机调度问题

半连续型批处理机调度问题是一种新型的批调度问题,它是从钢铁工业加热炉对管坯的加热过程中提炼出来的,与传统批处理机调度问题的批进批出方式不同,其主要特征为批中工件的进入、加工和离开都连续进行,同一批工件中工件的加工时间均等于这批工件中加工时间的最大者,批的大小为这批工件的个数,批的加工时间是从该批中的第一个工件进入机器,到最后一个工件离开机器所用的时间,因此批的加工时间取决于该批的大小、批中工件的最大加工时间及机器的容量。研究了这种新模型具有优先约束的情况,对链式约束下的极小化最大完工时间问题进行了讨论,证明了最优解的性质,从而给出了一个复杂性为O(n2)的动态规划算法,能够获得对应问题的最优解。     

基于截断学习效应的流水作业排序问题研究

【目的】给出具有截断学习效应的加权总完工时间流水作业排序问题的最优解。【方法】建立具有截断学习效应的加权总完工时间流水作业排序问题的数学模型,给出优势性质、下界和上界,并采用分支定界算法求解该问题的最优解。【结果】数值模拟结果表明:启发式算法得到的解比较准确,最大误差为 0.4117 ,分支定界算法的效率比较高,处理 100 个工件所用的最大时间不超过 460s 。【结论】计算结果表明分支定界算法能够很快地给出该问题的最优排序。
     

关于误工的两个代理单机排序问题

【目的】研究与误工相关的两个代理单机排序问题。【方法】第一个代理工件的到达时间与工期满足一致关系,目标函数为总误工或最大误工。第二个代理工件可中断,目标函数为总误工工件个数,在模型确定的情况下结合Lawler算法或EDD规则确定一个最优排序规则,使得满足第二个代理目标可行的情况下,第一个代理的目标函数值最小。【结果】在上述模型最优排序规则确定的前提下,求出最优排序方案使得第一个代理的目标函数最小。【结论】提出了总误工问题的一个拟多项式时间动态规划算法,给出了最大误工问题时间复杂度的证明。
     

基于截断学习效应的流水作业排序问题研究

【目的】给出具有截断学习效应的加权总完工时间流水作业排序问题的最优解。【方法】建立具有截断学习效应的加权总完工时间流水作业排序问题的数学模型,给出优势性质、下界和上界,并采用分支定界算法求解该问题的最优解。【结果】数值模拟结果表明:启发式算法得到的解比较准确,最大误差为0.411 7,分支定界算法的效率比较高,处理100个工件所用的最大时间不超过460s。【结论】计算结果表明分支定界算法能够很快地给出该问题的最优排序。     

工件带运输时间的单机分批排序问题

主要考虑了在线和离线两种模型下的工件带运输时间的单机分批排序问题.工件一但被加工完将会被马上运往目的地.我们考虑了三种限制模型:(1)在线模型:批量B无穷大,工件的加工时间和运输时间一致,即:若工件Ji的加工时间Pi大于等于工件Jj的加工时间pj,那么它们的运输时间有qi≥qj.(2)在线模型:批量B无穷大,工件的最大运输时间和最小的运输时间的比小于等于1 平方根5/2.对于(1),(2)这两种模型我们给出了一个竞争比为1 平方根5/2的在线算法,并且这个结果是最好的.(3)离线模型:批量B有限,当工件的到达时间是整数并且加工时间P=1时,我们给出了一个时间复杂性为O(n2lnn)的多项式时间算法,当工件的加工时间不是1,但工件的到达时间的个数是一个常数m时,我们给出了一个时间复杂性为O(2m-1nlnn)的多项式时间算法.