调度研究的问题是在一定的时间范围内将有限的资源分配给不同的任务,一个可行的调度方案必须满足问题中涉及的任务、资源及时间等所有约束,调度的目标是从所有可行方案中找出一个最优或满意解。对调度问题的研究始于二十世纪中期,在过去几十年中调度领域内新问题、新理论和新方法层出不穷。时间依赖调度便是调度领域内相对新颖的一个研究课题。在时间依赖调度问题中,存在一个或多个元素与时间紧密关联。事实上,“时间依赖调度”一词,最初被用来描述工件的加工持续时间依赖于其加工开始时间的问题。在该问题中,工件的加工时间不再是一个固定值,而是随着加工开始时间的不同而变化的,这也是当前研究受到最多关注的一类时间依赖调度问题。然而除此之外,加工一个工件获得的收益(或引起的惩罚)、加工不同工件之间需要的转换时间也可能依赖于开工时间(或完工时间),这两种特点可分别称为时间依赖的收益和时间依赖的转换时间,在生产制造、物流配送等行业中广泛存在,在敏捷卫星任务规划中也显得尤为突出。本文首先分析了敏捷卫星任务规划中的时间依赖收益、选择与调度相结合以及时间依赖转换时间这三类特点,这三类特点在其他调度领域也同样存在;然后着重就以下几点开展研究并做出了一些有创新性的贡献:(1)提出了考虑提早-延期惩罚调度问题的求解算法考虑提早-延期惩罚的调度问题是一种典型的具有时间依赖收益特点的调度问题。机器加工一个工件引起的惩罚项不是一个固定值,而是依赖于工件的完工时间。考虑每个工件具有不等的释放时间、交货期、提早和延期惩罚系数,分别为单机环境和并行机环境下的调度问题建立了数学模型。单机环境下,提出了求解问题的模因演化算法。其中,在给定工件加工序列的情况下,考虑工件具有不同的释放时间和转换时间,提出了一种改进的最优定时算法来确定各工件的加工时间并计算目标函数值,通过和经典遗传算法以及OPL的实验比较,验证了算法的优化性能。并行机环境下,一是将求解单机问题的模因演化算法进行了扩展使之应用于并行机环境,二是在给定工件加工序列的情况下提出了一种改进的构造启发式算法确定工件的加工机器及开工时间,通过实验分析给出了这两种算法各自的适用场景。(2)提出了订单受理与调度问题的求解算法订单受理与调度问题是一个同时结合了选择与调度特点和时间依赖收益特点的问题。为最大化完工订单的收益,需要将选择和调度这两个决策过程集成考虑,从所有订单中选择出一部分加工并为各订单安排加工时间,加工订单获得的收益依赖于订单的完工时间。建立了该问题的数学模型,提出了求解该问题的差异化控制遗传算法。算法中针对该问题的特点提出了一种衡量个体之间差异大小的准则,使用差异化控制策略使算法在搜索过程中始终保持一个差异化种群,引入基于析构与构造策略的迭代贪婪启发式算法作为局部搜索算法。通过与其他五种算法在大量标准测试算例上的测试,验证了本文算法优良的优化性能。(3)提出了具有多时间依赖特点调度问题的求解算法研究了一个同时结合了时间依赖转换时间、选择与调度结合和时间依赖收益特点的调度问题。该问题是在订单受理与调度问题的基础上,引入时间依赖转换时间以及提早-延期惩罚,非常复杂、难以求解。本文采用位于0和1之间的实数作为编码方式,每个实数表示工件的实际完工时间占整个时间窗口长度的比率。当给定一个实值向量时,根据向量中的各实数预先确定对应工件的开工时间和完工时间,并且根据工件的开工和完工时间计算不同工件之间需要的转换时间。在此基础上建立一个有向无环图,图中最长路径上的节点即为被安排加工的工件,路径的长度即为该实值向量对应的目标函数。提出一种基于该有向图适应度评价的混合差分进化算法,通过和其他三种算法在测试算例上的实验分析验证了算法的有效性。(4)在敏捷卫星任务规划上的应用以我国在研的某型敏捷卫星为例,以工程应用中的姿态转换时间函数作为时间依赖转换时间的计算方式,将本文的时间依赖调度方法应用到敏捷卫星任务规划问题上,实验结果显示本文的时间依赖调度方法能够显著提升敏捷卫星的成像质量。