车间调度问题是指被调度的工件需要在不同的机器上进行加工,每台机器同时最多只能加工一个工件,而每个工件同时也最多只能在一台机器上加工,工件的加工不允许中断,问题是确定工件在机器上的加工顺序和时间,使得目标函数最优化。由于车间调度问题广泛存在于制造业和物流系统中,而且大多数车间调度问题都是NP难的,因此探讨问题的启发式进行近似求解成为学术界和工业界的主要研究手段。如何从理论上分析和评价启发式的性能是调度领域具有挑战性的研究课题。本文对流水车间和开放车间两类典型车间调度模型进行了研究,分别设计了新的启发式并从理论上对这些启发式进行了渐近分析,针对问题已有的一些典型启发式从理论上进行了渐近分析和最坏情况分析(离线)或最坏竞争分析(在线)。最后通过数值实验仿真验证了所分析的调度启发式的性能。具体内容概括如下：1)针对流水车间最小化最大完工时间问题,提出了单个工件优先(SJF)启发式,并证明了当问题规模趋近于无穷大时该启发式是渐近最优的。为了进一步从数值上对提出的启发式进行评价,提出了一个新的下界,证明了该下界的渐近最优性,并指出其最坏情况比为机器数m,且为紧界。最后,通过数值实验仿真与所提出的下界进行比较,验证了SJF启发式的渐近最优性。2)针对带有释放时间的流水车间最小化最大完工时间问题,提出了动态单个工件优先(DSJF)启发式,并证明了当问题规模趋近于无穷大时该启发式是渐近最优的。从DSJF启发式渐近最优性的证明过程,又得到了先来先服务(FCFS)规则也是渐近最优的推论。对于该问题,提出了一个新的下界,证明了该下界的渐近最优性,并指出其最坏情况比为机器数m,且为紧界。最后,通过数值实验仿真验证了DSJF启发式的渐近最优性和新下界的性能。3)针对流水车间最小化总加权完工时间问题,提出了一个新的下界,并对该下界的性能进行了理论分析。理论分析分为渐近分析和最坏情况分析两个方面：在渐近分析方面,证明了当问题规模趋近于无穷大时,新下界是渐近最优的；在最坏情况分析方面,新下界的最坏情况比为机器数m,且为紧界。最后,通过数值实验仿真验证了新下界的性能。4)针对带有释放时间的流水车间最小化完工时间平方和问题,应用两个典型在线启发式求解该问题,第一个启发式是首台机器最短可用加工时间优先(SPTA-F)策略；第二个启发式是平均最短可用加工时间优先(SPTA-A)策略。通过理论分析,证明了当问题规模趋近于无穷大时这两个启发式都是渐近最优的,并指出SPTA-F启发式的最坏竞争比是无界的,而SPTA-F启发式的最坏竞争比为机器数的平方m2,且为紧界。对于该问题,经过对两个下界性能的分析,提出了一个渐近最优的新下界。最后,通过数值实验仿真验证了两个启发式的渐近最优性和新下界的性能。5)针对开放车间最小化最大完工时间问题,证明了典型启发式循环排序(RS)策略的渐近最优性,并指出该启发式的最坏情况比为机器数m,且为紧界。为了进一步改进RS启发式求解中等规模问题的性能,提出了基于RS的MRS启发式。最后,通过数值实验仿真验证了RS启发式的渐近最优性和MRS启发式的性能。6)针对带有释放时间的开放车间最小化最大完工时间问题,证明了当问题规模趋近于无穷大时,典型启发式紧排序(DS)策略是渐近最优的。为了进一步改进DS启发式求解中等规模问题的性能,提出了基于DS的动态最短加工时间优先—紧排序(DSPT-DS)启发式。最后,通过数值实验仿真验证了DSPT-DS启发式的性能。7)针对开放车间最小化总完工时间问题,提出了最短加工时间分块(SPTB)启发式,并证明了当问题规模趋近于无穷大时,SPTB启发式是渐近最优的。最后,通过数值实验仿真验证了SPTB启发式的渐近最优性,进一步的计算结果表明了所提出启发式的性能优于此问题的典型匹配算法。