机器具有可用性限制的加权总完工时间问题

研究一种带有学习和恶化效应,并且机器具有可用性限制的排序问题。讨论的目标函数为加权总完工时间的单机和两台机器的平行机问题。在某些实际生产过程中,工件加工时间的变化既受生产设备长时间使用,导致恶化现象的影响,也受生产设备或工人加工效率提高的影响。因此,在这种模型中,工件的实际加工时间不仅与它的所排位置有关,而且还与工件的开始加工时间有关。此外,由于机器发生故障或进行维护与保养等原因,导致其在某一区间内无法加工工件。针对某种学习和恶化效应模型下机器在任意时间段维修的单机和2台机器的平行机的某些情况,分别给出了拟多项式时间动态规划算法,分析了算法复杂性,并给出相应数值例子表明算法的有效性。     

时间相关的单机排序的最坏竞争比分析 (运筹学与控制论)

本文研究了工件的加工时间具有开工时间和加工所在位置相关的单机排序问题。工件的加工时间是序列中加工所在的位置和开工时间的非增函数,目标函数为最小化的误工工件个数和最小化总误工。本文对于所研究的2个目标函数利用Moore-Hodgson算法和EDD规则分别提出的启发式算法,对于目标函数位误工工件个数情形给出了最坏竞争比近似于2,最小化总误工给出非常数的最坏竞争比。进一步如果工件的加工时间和工期具有一致关系,分别给出了2个多项式时间算法。     

时间相关的单机排序的最坏竞争比分析

本文研究了工件的加工时间具有开工时间和加工所在位置相关的单机排序问题.工件的加工时间是序列中加工所在的位置和开工时间的非增函数,目标函数为最小化的误工工件个数和最小化总误工.本文对于所研究的2个目标函数利用Moore-Hodgson算法和EDD规则分别提出的启发式算法,对于目标函数位误工工件个数情形给出了最坏竞争比近似于2,最小化总误工给出非常数的最坏竞争比.进一步如果工件的加工时间和工期具有一致关系,分别给出了2个多项式时间算法.     

有安装时间的单机排序问题

工件具有安装时间的排序问题最近几年受到越来越多的关注,主要讨论了一类有安装时间且与加工位置有关的单机排序模型。在该模型中,所有工件在机器上加工时,一次只能加工一个工件,工件的相邻加工工序之间不允许出现空闲,工件的实际加工时间不是一成不变的,它不仅与工件的基本加工时间有关,同时还与工件所处的加工位置有关,工件的安装时间是依赖于已加工工件的实际加工时间的简单函数,即p-s-d形式。对目标函数为极小化最大完工时间,极小化完工时间和以及极小化总完工时间差等问题进行讨论,分别给出了多项式算法和算法复杂性。还证明了对于目标函数为完工时间,提前完工时间以及误工时间的加权和最小化问题是多项式可解的。     

具有到达时间和禁用区间的单机平行批排序

研究工件带有到达时间且机器带有可用性限制(禁用区间)的单机平行批排序问题.假设机器在一些不交的时间区间上不可用.工件以平行批的形式在机器可用的时间区间上加工,并且不可中断.一个批的加工时间是这一批中加工时间最长的工件的加工时间.对任意的正则目标函数,当工件带有到达时间且机器带有可用性限制时,给出了单机平行批排序问题的一个拟多项式时间算法.     

带凸资源依赖的一类单机排序问题

就工件的实际加工时间是之前已加工工件的正常加工时间和的指数学习效应且具有凸资源依赖的单机排序问题展开讨论。在所有工件的正常加工时间均相同的假设下,对最小化加工全程和资源消耗总费用的和、最小化完工时间和资源消耗总费用的和,最小化总提前、总延误、总共同交货期和资源消耗总费用的函数以及最小化总提前、总延误、总松弛交货期和资源消耗总费用的函数四个目标函数分别给出了多项式时间可求解的算法。
     

带凸资源依赖的一类单机排序问题

就工件的实际加工时间是之前已加工工件的正常加工时间和的指数学习效应且具有凸资源依赖的单机排序问题展开讨论。在所有工件的正常加工时间均相同的假设下,对最小化加工全程和资源消耗总费用的和、最小化完工时间和资源消耗总费用的和,最小化总提前、总延误、总共同交货期和资源消耗总费用的函数以及最小化总提前、总延误、总松弛交货期和资源消耗总费用的函数4个目标函数分别给出了多项式时间可求解的算法。     

带有可变加工时间和可用性限制的排序问题

研究带有恶化效应、学习效应和可用性限制的单机和2台平行机的排序问题。在这个模型中,工件的实际加工时间与其基本加工时间、加工过程中所排位置及开始加工时间有关;同时由于维修、保养等原因,使得机器在某段时间不能加工工件,即机器具有可用性限制,且维修之后机器性能完全恢复,讨论的目标函数为总完工时间。对于可以在任意时间只维修一次的单机问题,以及只有一台机器具有可用性限制的2台平行机问题,分别给出了拟多项式时间的动态规划算法。特别对于一台机器只在零时刻开始维修另一台机器无可用性限制的特殊情况,通过将其转化为指派问题,给出了复杂性为O(n4)的多项式时间最优算法,并通过一个数值例子说明了其计算过程。     

钢铁生产中管坯加热的单机连续型批调度策略研究

连续型批处理机调度问题是从钢铁生产线提炼出来的一种新型的批调度模型,该调度模型中,批的加工时间取决于该批的大小、批中工件的最大加工时间及机器的容量。研究目标函数为最小加权总完工时间的单机连续型批调度问题,分析最优解的性质,讨论最优的批内、批间序及分批策略,给出工件权值与加工时间逆序情况下的动态规划算法。     

基于流水线调度问题的模型与局部搜索算法

在基于流水线的调度问题中,所有工件按照相同的顺序访问机器,但部分或全部工件可以不必在某些机器上进行加工.标准flowshop问题是这种流水线调度问题的一个特例.研究了带序依赖和机器依赖加工准备时间的流水线调度问题,针对该问题建立了一个基于序列的0～1混合整数规划模型,目标函数是总加权完工时间最小,提出了相应的局部搜索算法,实验结果证明了算法的有效性和可应用性,所提出的局部搜索算法的求解思路对同类流水线调度问题具有指导意义。