生产调度在企业生产管理中一直起到至关重要的作用,调度所研究的问题就是将有限的资源进行合理的分配与安排,对一个或多个目标进行优化。调度方案的合理与否直接影响企业制造现场的生产效率,进一步影响企业的生存能力和竞争力,随着制造业的飞速发展,生产方式不断变化,生产规模也不断变大,逐渐涌现了一些新的调度问题,其中有一种调度问题叫做分批调度问题,也叫做批处理机调度问题,不同于经典调度问题中一台机台在同一时间只能加工一个工件的情况,在分批调度问题中一台机台可以同时加工若干个工件。而分批调度问题本质上可以分为两个子问题:工件指派到机台的问题和工件批次分配问题。工件的分批调度可以比较高效地分配和利用资源,分批调度问题也因此成了调度问题中比较重要的一个分支。工件的分批调度问题在生产实际中普遍存在,尤其是在半导体行业晶圆制造过程中。本论文以最小化最大完工时间为优化目标,研究了带有不相容工件簇限制的并行机分批调度问题,问题中含有多种限制条件,包括工件尺寸不相同限制,工件随机到达时间限制。在对实际问题进行分析之后,对问题进行合理的简化并引入相关假设,以若干个变量和不等式建立了一个混合整数规划模型。另外根据该调度问题和目标函数的特性从三种角度分别提出了RO启发式算法、PO启发式算法和SO启发式算法,利用同一算例作为示例,展示了三种启发式算法的求解结果,同时提出一个下界作为评价算法求解效果的标准,并证明了这个下界的正确性。另外,本文提出了改进的人工免疫系统算法(AIS)和离散粒子群算法(DPSO),除了对算法的整体结构进行优化之外,考虑到问题特性,将较好的分批方法与两种算法结构相结合,使两种万用启发式算法可以有效解决本研究问题。最后通过随机产生的450个实验问题,利用C++语言进行仿真实验对所提出的算法进行性能分析和评价。通过实验结果的数据分析得出如下结论:三种启发式算法可以在较短的时间内得到不错的解,而RO启发式算法和PO启发式算法表现更佳,但随着问题规模的扩大,三种启发式算法的求解效果都变差;改进的人工免疫系统算法和改进的离散的粒子群算法的求解表现比较稳定,但改进的人工免疫系统算法的表现从整体上来说要好于改进的离散粒子群算法;而RO启发式算法求得的解作为初始解可以有效提高改进的人工免疫系统算法的求解效率。