铝作为地球上含量最丰富的金属元素,在许多领域具有广泛的应用。铝冶炼加工企业的生产订单具有多品种、小批量的特点,这加大了生产组织的难度;同时,客户对交货期的要求也越来越严格,通常要求订单在一定的时间范围内生产完成,这也进一步加大了生产排程的难度。铝冶炼过程包括多个生产工序,熔炼阶段是其中重要的一环。如何将不同的订单分配到不同的并行熔炼炉上生产,对提高生产效率,降低能量消耗具有重要的影响。本文以铝熔炼生产过程为背景,提炼出一类新型并行机调度问题进行建模和优化算法研究。主要研究内容如下:1)以订单在熔炼炉上的分配以及洗炉次数为决策变量,考虑订单需求、洗炉操作等工艺约束,以最小化制造期（Makespan）为目标,建立了铝熔炼生产调度问题的整数规划模型。基于模型推导出了问题的理论下界,采用差分进化算法求得了问题的上界。数值实验结果显示差分进化算法获得的上界同理论下界之间具有较小的间隙。2)以计算出的下界和上界为输入,提出了求解问题最优解的二分搜索精确算法框架。针对二分搜索中的上界和下界判别问题,从对偶的视角出发,将给定制造期前提下的可行调度问题转换为带有调整时间的装箱问题（Bin Packing Problem with Setup Time,BPPST）,并针对BPPST问题提出了基于列生成的分支-定价算法。数值实验结果显示所提出的二分搜索精确算法能够在合理时间内求得中等规模问题的最优解,验证了算法的有效性。3)研究了带有时间窗约束的铝熔炼生产调度问题的新型建模方法。在实际的生产过程中,客户的订单往往带有交货期的要求,故在上述问题中加入时间窗约束,保证订单在用户要求的交货期内生产完成,并且给予每个订单一定的柔性时间进行排程。通过以上分析,基于时间块建立了带有时间窗的铝熔炼生产调度问题的模型,最后利用商业软件CPLEX求解,通过实验数据对比验证了该模型的正确性。