在半导体制造企业中,最终测试流程占有的市场规模越来越大,占用的资金越来越密集,由于测试流程中表现出不确定性、可重入性以及批处理等特点,因此对半导体测试站的研究已成为近年来研究调度问题的热点。而批处理操作在整条测试流程中占据的操作时间最长,是测试过程中的瓶颈工序,所以,优化批处理机的调度问题在提高整条测试流程的调度效率上显得尤为重要。批处理机的调度问题来解决的是工件分批和批调度两个关键问题。随着批处理机的调度问题变得极其复杂,且大多数被证明为NP难问题,依据传统的最优化方法和启发式方法已很难解决,而智能算法在解决复杂问题时表现突出,本文通过引入智能算法寻找批处理机调度问题的最优解或者较优解。本文首先给出了批处理机调度问题的描述方法,介绍两种常用的分批方法,以及目前对于解决该调度问题的优化算法；然后建立单批处理机调度问题的模型,引入提前和拖期(Earliness and Tardiness, E/T)目标函数,提倡工件提前或者拖期交货都不鼓励的思想,依据此问题建立模型,提出基于汉明距离的变邻域搜索算法(Variable Neighborhood Search based on Hamming Distance, HDVNS)的优化算法,通过仿真实验,与遗传算法(Genetic Algorithm, GA)比较,证明HDVNS具有很好的鲁棒性；其次针对平行式批处理机调度问题,根据工件的单位提前和拖期成本,提出两种基于约翰逊法则的初始解产生的方式,仿真实验结果表明,这两种初始解产生方式以其他方式相比,算法优化过程表现效果良好：根据工件在平行式批处理机进行处理时,是先分批还是先把工件分配到机器,提出两种策略,最后通过实验数据显示,两种策略表现效果相差不大,但是工件先分配到机器上的方式在多数算例中,算法的平均运行时间要稍短一些。最后是对本论文的研究内容进行总结和展望。