制造业作为实体经济的重要组成部分,是保持国家和社会稳定发展的重要保障。我国一直大力推进智能制造的发展,制造业的未来将更加推进信息化和工业化的深度融合。这也意味着需要高效科学的生产调度来管控整个生产过程,尤其是针对于高科技、高自动化的制造产业。生产调度能够直接影响整个制造过程的生产计划和运筹控制,科学合理的生产调度可以更加有效的提高资源利用率,降低成本,减少生产时间,提升产品产量及质量。所以在新形势下,面向不同问题的有针对性的生产调度研究是十分必要的。本文就是基于芯片加工过程需要在特殊的并行设备上通过特制的具有不同集成电路图的光掩模板对晶圆进行曝光处理。由于光掩模板的限制,管理者需要优化晶圆的生产加工顺序,提高机器利用率,确保资源使用的最大化。双台并行机作为复杂系统研究的基础模型,本文提出在模具限制下以最小化最大完工时间为目标的双台并行机调度问题,即P2|fi|Cax问题。论文通过对P2|fi|Cax问题的研究,提出融合问题特性的启发式算法和分支定界算法两种解决思路。分支定界算法能够精确求得问题的最佳解,求解问题的规模有限;启发式算法不受问题规模的限制,能够得到近似最佳解。论文首先建立了问题的混合整数规划模型及其下界模型。论文在将加工时间较短的工作放在调度后面,用于平衡机器的负载以减小机器的完工时间的LPT思想上提出HLPT算法、LAPT算法和CHL算法三种启发式算法。根据工件排列组合的特点结合分支定界的思想提出P-B&B算法。论文对算法的结构及过程进行详细的论证和阐述。证明所提出的HLPT算法、LAPT算法和CHL算法三种启发式算法所得近似最佳解的最差情况上界比值ξ=4/3。比Chung(2019)提出的TLPT算法、DMLPT算法及CTD算法三种启发式算法最差上界比值ξ=3/2小。证明P-B&B算法的下界1和下界2的正确性,无空闲排序的最佳性和几种分剪支情况。本文也通过C++编程实现算法计算机仿真实验来评价和检验算法的质量。针对算法解决的问题规模不同,产生小规模工件数量的实验问题300个和大规模工件数量的实验问题320个。启发式算法通过大小不同规模的数据实验,由目标值的百分比偏差、最佳状况的数量和运行时间等指标显示:CHL算法在不同数据规模的实验中都是六种算法里求解质量最佳的算法;其次,LAPT算法整体上优于对比组最好的CTD算法,尤其是在大规模数据的实验;而HLPT算法质量要介于TLPT算法和DMLPT算法之间。另外,分支定界法只能够解决小规模问题,由此通过比较P-B&B算法与AMPL软件调用CPLEX求解问题数学模型所得出最佳解的工件数量来比较求解能力。P-B&B算法求解的工件数量比软件多30%,所以其求解质量更好。