摘要: 同类机调度问题是一类重要的平行机调度问题，其中假设机器的处理速度具有恒定的差异，是同型机调度问题的进一步拓展。在现实生产生活环境中，如多次购置的同类机器设备，由于批次不同而具有不同的处理速度;完成同类工作的不同员工具有相对稳定的操作... 展开 同类机调度问题是一类重要的平行机调度问题，其中假设机器的处理速度具有恒定的差异，是同型机调度问题的进一步拓展。在现实生产生活环境中，如多次购置的同类机器设备，由于批次不同而具有不同的处理速度;完成同类工作的不同员工具有相对稳定的操作效率的差异等等，均可以抽象为同类机调度问题。可见同类机调度问题具有广泛的现实背景。 通常，生产调度问题关注的是生产过程中的优化，旨在统筹考虑生产制造过程中的各种约束条件，达到某个或多个目标的最优化，因此是典型的组合最优化问题，并且成为运筹、管理、工业工程等学科的重要内容。近几年，越来越多的研究学者基于生产过程的优化，进一步研究生产过程与其供应过程中上游原材料供应或下游配送等环节的协同最优化。其中考虑配送的生产调度问题较传统生产调度问题更加关注作业完工后将其配送至客户的过程，显然作业完工时间与客户接收到货物的时间相比，后者更能体现客户满意度，因此该类调度问题更加贴近现实情况，并受到人们的重视。 本文研究了两类直接配送模式下的同类机调度问题，假定作业完工后可直接配送给客户，系统的整体目标是追求最大客户收货时间Cmax的最小化。在调度领域，直接配送时间又称为尾时间，除了直观的将作业直接配送至客户的时间这一现实背景之外，如高温产品的冷却时间、涂彩产品的晾晒等也可以抽象为作业的直接配送时间。我们首先假定所有的直接配送时间为给定的固定常数，基于对该类问题解的特点分析，构建了一种模拟退火算法，并通过大量的实验数据验证了该算法的解质量优于现有LDT和LPDT算法。接着，我们假定作业的直接配送时间是可变的。采用先进的配送工具或设备能够减少作业直接配送时间，从而提高系统整体效率。现实中，效率的提高往往意味着更多成本的投入，因此我们假定作业的直接配送时间取值与某种额外资源数量成线性减函数关系。调度的目标是在给定总的额外资源数量的情形下最小化最大客户收货时间Cmax。我们提出了一种资源分配算法RAA，在此基础上结合LDT、LPDT、模拟退火算法等为该类直接配送时间可控的同类机调度问题构建了多种优化算法，最后通过大量计算机仿真实验数据对各种算法的性能进行了分析和验证。 收起