调整时间与工序顺序相关的车间作业调度问题（SDST-JSP）广泛存在于制造工业中，如纺织、半导体生产等。由于其比经典车间作业调度问题（JSP）能更好地建模实际生产调度，故具有非常重要的实际应用价值。　　 本文在分别改进遗传算法和禁忌搜索算法的基础上，提出将两者相结合的混合算法GA+TS。设计启发式算法与随机算法相结合的初始解生成策略，以保持种群的优良性和多样性；构造新的交叉算子（ROX），以有效保存父代的优良基因；提出具有扰动因子的解码算法（RG&T），在生成活跃调度的基础上，扩大算法搜索空间；构造新的启发式算法（BidirS和ListS），为禁忌搜索算法提供铰好的初始解：提出五种新的邻域结构，有效地增强算法的局部搜索能力；采用禁忌表动态变长策略，提高对解空间有效搜索；采用短期记忆和长期记忆相结合的策略，以充分利用搜索历史信息，避免循环搜索，从而扩大算法对解空间的覆盖率；提出遗传算法与禁忌搜索算法相结合的混合启发式算法，通过加强遗传算法局部搜索能力，提高禁忌搜索算法初始解的多样性，从而提高算法总体眭能。　　 通过基于BT标准的测试实例，将GA+TS与目前最好的两个算法SB+GLS和GA+LS进行比较。实验结果表明所提算法在相对误差方面要优于其它两个算法，故能有效地解决SDST-JSP问题。