典型车间调度问题中的算法理论分析

发布时间：2021-01-30 03:24

　　车间调度问题是指被调度的工件需要在不同的机器上进行加工,每台机器同时最多只能加工一个工件,而每个工件同时也最多只能在一台机器上加工,工件的加工不允许中断,问题是确定工件在机器上的加工顺序和时间,使得目标函数最优化。由于车间调度问题广泛存在于制造业和物流系统中,而且大多数车间调度问题都是NP难的,因此探讨问题的启发式进行近似求解成为学术界和工业界的主要研究手段。如何从理论上分析和评价启发式的性能是调度领域具有挑战性的研究课题。本文对流水车间和开放车间两类典型车间调度模型进行了研究,分别设计了新的启发式并从理论上对这些启发式进行了渐近分析,针对问题已有的一些典型启发式从理论上进行了渐近分析和最坏情况分析（离线）或最坏竞争分析（在线）。最后通过数值实验仿真验证了所分析的调度启发式的性能。具体内容概括如下：1)针对流水车间最小化最大完工时间问题,提出了单个工件优先（SJF）启发式,并证明了当问题规模趋近于无穷大时该启发式是渐近最优的。为了进一步从数值上对提出的启发式进行评价,提出了一个新的下界,证明了该下界的渐近最优性,并指出其最坏情况比为机器数m,且为紧界。最后,通过数值实验仿真与所提出的下... 

【文章来源】：东北大学辽宁省 211工程院校 985工程院校 教育部直属院校

【文章页数】：133 页

【学位级别】：博士

【部分图文】：

车间调度问题中各模型之间关系

图2.2比值的下降趋势 Fig.2.2Thedeereasingtrendoftheratios从图2.2中，可以观察到，随着机器数的减少，比值越接近于1，换句话说，目标函数值随着机器数的减少而越来越接近其下界值。这是因为机器数越少，排序过程中产生的空闲时间越少，从而减小了目标函数值与其相应的下界值之间的误差。对于固定的机器数，前面已经证明了随着工件数的增长，目标函数值越来越接近其下界值。2.7本章小结本部分针对流水车间最小化最大完工时间问题，提出了SJF启发式，并证明了当问题规模趋近于无穷大时

我们看到，当工件数增加机器数减少时，DSJF启发式和FCFS规则的目标函数值越来越接近最优解。对于中等规模问题，DSJF启发式的性能要优于FCFS规则。图3.4比较了5台机器，Rt=l时，二者的比值。一一黯一一一一一一一目目目 目目目DSJFFF .........FCFSSS50叫祠门﹄图3.4当m一5，Rt=1时，DsJF启发式与FCFS规则比较 Fig.3.4TheeomParisonofDSJFheuristiewithFCFSmarinerwhenm=sandRt=l‘‘‘’。551一.磊一一-一一一刁 刁;;;:……妞。羹羹羹羹羹羹羹 羹日日日日 日日日 515RtttDSJF ...........FcFSSSSS 1.055 1.05毖 1.045闷曰舀 1.04图3.5当m二5，n=1000时，DsJF启发式与FCFS规则比较 Fig.3.5TheeomParisonofD


本文编号：3008144