带释放时间的并行机调度问题的ILS & SS算法

研究工件带释放时间的两类并行机最小化总完成时间的调度问题.针对问题提出了一种新的基于变深度环交换邻域结构的Iterated local search(ILS)算法.1)提出了变深度环交换邻域结构.2)基于变深度环交换和传统Swap的混合邻域,提出了带有两种kick策略的ILS算法.3)为了加强ILS逃出局部最优的能力,将Scatter search(SS)搜索方法引入了ILS算法中;算法将当前最好解和次好解进行分散处理,再从处理后的解开始继续迭代.为了验证算法的有效性,对两类并行机问题分别随机产生100组数据进行试验.实验结果表明:对于同构并行机问题,引入SS的ILS算法的计算结果与下界的平均偏差为0.99%,而没有引入SS的ILS算法的为1.06%;对于无关并行机问题,引入SS搜索方法后,ILS算法的计算结果改进了6.06%,并明显优于多点下降算法.     

并行机成组调度问题的启发式算法

研究了优化目标为总拖后/提前时间最小化的并行机成组调度问题,提出了一种三阶段启发式近似求解算法。首先把并行机问题看成单机问题,以最小化总拖后时间为优化目标排列工件的加工次序;然后将工件按第一阶段所求得的次序指派到最先空闲的并行的机器上;最后采用改进的GTW算法对各机器上的工件调度插入适当的空闲时间。计算表明该算法能够在很短的时间内给出大规模调度问题的近似最优解。     

基于增强型kick策略的ILS算法求解一类聚类问题

提出一种新型的基于环交换邻域的迭代局部搜索算（ILS）．用于求解一类聚类问题,算法的主要特点是：1）基于环交换的邻域结构;环交换邻域与传统的Swap和Insert邻域相比,算法在一次迭代中允许多个点同时移动;2）针对聚类问题提出了增强型的kick移动策略：根据每组内点的密度分布摄动聚类中心,对给定的解重新聚类,实验结果表明,基于环交换的迭代局部搜索算法对求解该类聚类问题是有效的．     

求解异构并行机调度问题的混合烟花算法

以加工时间可控的机器调度为研究对象,考虑一类以优化能耗和延迟成本为目标的异构并行机调度问题。对该调度问题进行描述,并构建混合整数线性规划模型;提出混合烟花求解算法(HFWA),设计特定的编解码方法以表示问题的解,并融入反向学习初始化方法以提升初始解的质量;构建基于变邻域搜索算法的局部优化流程用以强化基本算法的寻优性能。仿真实验验证了该算法的可行性和有效性。     

蚁群算法求解非等同并行机调度问题的研究

针对非等同并行机服务调度问题,以机场除冰调度服务为背景并以最小化旅客延误数为目标,提出了一种改进的蚁群算法。该算法根据调度模型的特点,充分考虑模型的约束条件并运用了一种改进的信息素更新策略求解并行机调度问题。仿真结果表明,改进的蚁群算法收敛速度快且结果较优,明显优于FIFO算法,适合求解非等同并行机调度问题。     

约束满足混合算法求解并行机Job-Shop调度问题

分析并行机Job-Shop调度问题的特点并建立其约束满足优化模型,结合约束满足与变邻域搜索技术设计了一个求解该问题的混合优化算法。该算法采用变量排序方法和值排序方法选择变量并赋值,利用回溯和约束传播消解资源冲突,生成初始可行调度,然后应用局部搜索技术增强收敛性,并通过结合问题特点设计的邻域结构的多样性提高求解质量。数据实验表明,提出的算法与其他两种算法相比,具有一定的可行性和有效性。     

解优先级约束并行机调度问题的人工免疫算法

针对家纺企业车间调度的实际情况,建立了优先级特殊工艺约束下并行多机拖后调度模型,并提出一种新颖的人工免疫算法对其求解。该算法是依据生物的免疫机理,将目标函数作为抗原,将问题的解作为抗体,对抗体采用向量组编码的方式进行编码,通过克隆、变异及一种新颖的基于浓度的种群多样性更新选择方法,提高了种群多样性,并通过局部搜索改善了种群质量,加快了收敛速度。仿真结果表明,与遗传算法相比较,该算法能更快更准确地收敛到全局最优解。     

改进蚁群算法在具有退化特征并行机调度上的应用

本文讨论了非抢占式独立并行机的退化调度问题,在这个问题中工件的加工时间是线性增加的,目标函数是极小化总完工时间。为了有效的解决这种复杂的车间调度问题,针对并行机调度的特点,本文提出了一种改进的蚁群算法,对信息素更新策略以及选择概率做了修改。通过实例仿真,与传统的粒子群算法,遗传算法进行比较,实验结果表明,本文提出的改进蚁群算法具有较好的收敛性与稳定性。     

复杂并行机调度问题基于分解的优化算法

针对纺织生产过程中广泛存在的带特殊工艺约束的大规模并行机调度问题，提出了一种基于分解的优化算法。首先将原调度问题分解为机台选择和工件排序两个子问题，然后针对机台选择子问题提出一种进化规划算法，并采用一种具有多项式时间复杂度的最优算法求解工件排序子问题，以得到问题特征信息（即每台机器对应拖期工件数的最小值），该问题特征信息用以指导进化规划算法的迭代过程。不同规模并行机调度问题的数值计算结果及实际制造企业应用效果表明，本文提出的算法是有效的。     

A new ILS algorithm for parallel machine scheduling problems

This paper addresses the non-preemptive scheduling problem of scheduling jobs on identical parallel machines to minimize the maximum completion time or makespan. The problem has been proved to be NP-hard in the strong sense. The NP-hardness of the problem motivates us to develop a new methodology to obtain near-optimal solutions. We formulate the problem as an integer programming and then propose a new iterated local search (ILS) algorithm based on a variable number of cyclic exchanges to solve it. The properties of the solutions are derived and the results are used to improve the computational efficiency of our algorithm. Computational experiments show that the cyclic exchange neighborhood embedded in an iterated local search framework is effective for solving the scheduling problems with up to 1000 jobs and 40 machines within a reasonable amount of computation time. Received: April 2005 / Accepted: January 2006     

求解Job Shop调度问题的一种新的邻域搜索算法

利用了混合邻域结构进行搜索来求解Job Shop调度问题．算法使用的混合邻域结构不仅使邻域搜索具有效率,而且有助于搜索有效地跳出局部极小值的陷阱,让计算走向前景更好的区域．算法采用的“单机调度”和“同工件工序调整”的跳坑策略能够帮助搜索找到更好的局部极小值．采用国际文献中所有的10工件10机器算例以及另外7个难算例作为本算法的测试实验集,与目前国际上最好的近似算法和另外一种先进算法进行了比较．实算结果验证了算法的寻优性能．     

基于准时制思想的炼钢—连铸生产动态调度算法

通过对炼钢—连铸生产动态调度问题的分析,建立了基于准时制思想的炼钢—连铸生产动态调度模型．提出了一种基于多个邻域结构和种群进化策略的进化迭代局部搜索算法,用于求解该模型．基于实际生产数据的仿真试验证明了所提出模型和算法的有效性．     

考虑多类型时间依赖资源约束的敏捷卫星调度优化

随着现代空间科技的迅猛发展,光学遥感图像数据的应用需求越来越广泛,大力推动了光学对地观测卫星的发展.然而,由于高昂的发射成本的约束,对地观测卫星的资源是有限的,远远无法满足各类数据需求.因此,提高对地观测卫星的使用效率,提高其任务执行率,具有非常重要的应用价值.本文聚焦于敏捷对地观测卫星的任务调度问题,即在给定的调度周期内,对有限的卫星资源制定合理的任务调度方案,在满足一定星上资源约束下,最大化观测任务收益.该问题难点在于星上的资源是非常有限的,例如存储图像数据的固存资源、用于采集数据和卫星姿态切换的能量资源及执行任务活动耗费的时间资源.需要注意的是,能量消耗量和时间消耗量依赖于任务的执行时间,这是敏捷卫星相对传统的非敏捷卫星独有的特性.不同任务场景对不同类型资源的需求不同,多种资源约束互相耦合,资源约束具有时间依赖特性,这些难点无疑极大地增加了卫星调度的求解难度.为高效地求解该问题,本文构建了多类型时间依赖资源约束的敏捷卫星调度整数规划模型,并针对问题特性提出了一种基于自适应选择因子的迭代局部搜索启发式算法.自适应选择因子综合考虑了目标收益、资源消耗量、资源约束的松弛量,采用动态变化的资源重要度,能快速自适应地根据当前场景下各种类型的资源数据使用量来确定最佳局部搜索方向,从而在有限时间内找到高质量的解.实验结果证明,本文所提出的算法在多种情况下相比当前最好算法求解效果显著更优.此外,算法独有的自适应选择因子相比传统的选择因子的求解质量更高,这是因为所设计的自适应选择因子兼顾了目标收益和资源消耗量之间权衡关系的同时,采用动态变化的资源重要度准确捕捉了资源需求的迫切程度.     

An improved scatter search algorithm for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times

In this paper, a scatter search algorithm with improved component modules is proposed to solve the single machine total weighted tardiness problem with sequence-dependent setup times. For diversification generation module, both random strategy based heuristics and construction heuristic are adopted to generate the diversified population. For improvement module, variable neighborhood search based local searches are embedded into the algorithm to improve the trial solutions and the combined solutions. For reference set update module, the number of edges by which the two solutions differ from each other is counted to measure the diversification value between two solutions. We also propose a new strategy in which the length of the reference set could be adjusted adaptively to balance the computing time and solving ability. In addition, a discrete differential evolution operator is proposed with another two operators constitute the combination module to generate the new trial solutions with the solutions in the subsets. The proposed algorithm is tested on the 120 benchmark instances from the literature. Computational results indicate that the average relative percentage deviations of the improved algorithm from the ACO_AP, DPSO, DDE and GVNS are −5.16%, −3.33%, −1.81% and −0.08%, respectively. Comparing with the state-of-the-art and exact algorithms, the proposed algorithm can obtain 78 optimal solutions out of 120 instances within a reasonable computational time.     

混合流水车间调度的变邻域禁忌搜索算法

针对混合流水车间系统的最小化Makespan调度问题,提出一种基于关键路径理论的变邻域禁忌搜索算法,讨论其关键技术。在该算法中,提出基于关键路径的毗邻域概念,防止搜索算法陷入局部最优解,采用变邻域搜索策略,在无法改进解时,实现对移动毗邻域的搜索。仿真结果表明,该算法获得的调度结果优于简化禁忌搜索和启发式算法。     

一种新的项目调度解表示方法

基于解集合的准启发式方法是解决资源约束下项目调度问题的有效方法,解的表示形式一直是这种方法的一个重要研究问题。只有充分利用解的形式和目标函数之间的联系,才可能达到在少数枚举下得到尽可能好的解。详细分析了解空间性质,提出了用额外关系表示一个可行解的方法,给出了这种表示方法的理论依据。并介绍了用该方法产生邻域的方法。     

一种基于分散搜索的多星测控调度遗传算法

多星测控调度是一个具有大搜索空间的多峰问题。针对简单遗传算法求解易陷入局部最优和不稳定的缺陷,借鉴分散搜索多样化采样、局部寻优的特点,提出一种基于分散搜索的混合遗传算法,在全局的随机搜索中嵌入全局的定向搜索。在描述问题的基础上,提出可进行细粒度搜索的可行解表示方式,构建算法的整体流程,并设计由输入参数控制的多样化初始集产生方法、基于质量和多样性原则的参考集生成和更新方法、吸取被组合个体优良成份的解组合方法及基于启发式局部搜索的解提高方法等算法要素。仿真表明新算法在求解质量上比简单遗传算法有明显提高。