批处理机调度是调度问题的一个重要分支。不同于经典调度问题,在批处理机调度问题中,一台机器可以同时加工多个工件。由于这类调度问题不仅需要将工件指派到机器上,还包含将工件分批的决策问题,因此比经典调度问题更为复杂,很多已知的批调度问题均是NP难解问题。批处理机调度在现实生产环境中有着广泛的应用,包括半导体芯片生产,钢铁制造,货物运输等。合理的调度方案可以大幅提高生产效率,节省生产成本,因此对批处理机调度问题的研究有着重要的现实意义。尽管当前已有不少文献对批处理机调度问题进行研究,但这些研究仍然有着不足之处。一是研究的问题主要侧重于工件具有相同尺寸的较简单情形,较少涉及不同尺寸工件情况。二是求解方法多是设计精确求解算法解决小规模问题或是用简单启发式算法获得近似解,对于复杂的构造式方法较少有人研究。三是研究的目标集中在以makespan为代表的生产效率型目标,而对于调度问题中的能源效率则鲜有关注。针对当前研究中存在的问题,本研究主要做了以下工作:(1)从聚类视角下研究了不同尺寸工件批处理机调度问题。论证了差异工件单机环境下的批调度问题实质为一种广义聚类问题,为求解该问题提供了一个新的途径。提出了批的空间浪费比的概念,将最小化C max的目标函数变换为最小化批的加权空间浪费比,从而可以更容易地寻找启发式信息指导分批过程,两者的等价性也在文中给出了证明。此外,以批的空间浪费比为基础,进一步定义了批间的距离度量,提出了批的约束凝聚聚类算法CACB,并通过实验验证了算法的有效性。(2)将不同尺寸工件的批处理机调度问题推广到工件动态到达的并行机环境,提出并证明了该问题的两个不同下界。在此基础上设计了两种智能优化算法。一是基于工件序列编码的遗传算法,通过工件序列和Best-Fit规则生成分批,并设计了一个ERT-LPT算法来安排批在机器上的加工。另外一种是基于构造式分批的蚁群算法,算法同时考虑工件在尺寸和加工维度的特点作为启发式信息,指导蚂蚁不断寻找适合的工件加入当前批,直到所有分批构造完毕。对两种算法的性能及偏好,通过大量仿真实验进行了比较。(3)将能源效率问题融入调度领域的研究中。构建了在分时电价条件下,以最小化电力成本和makespan为目标的柔性流水车间批调度问题的模型。设计了三种不同的多目标优化算法来求解该问题:即偏好向量蚁群系统PVACS,基于NSGA-II和基于SPEA2的进化算法,并比较了三种算法在不同评价指标下的性能。