敏捷供应链插单调度优化的启发式算法

针对在敏捷供应链已有生产计划基础上进行的插单调度问题,以单工厂和多供应商组成的两级供应链系统为研究对象,采用时间槽表示可用调度时间,以最小化供应链总成本为目标,建立了调度优化问题的整数规划(IP)模型,设计了求解该模型的逐批选优启发式(OOSH)算法。通过算例将其与距离优先和作业周期优先决策算法比较,验证了启发式算法的有效性,显示了敏捷供应链协同调度可以有效提高供应链的市场竞争力。     

求解Flow-shop调度问题的HSGATS算法研究

通过研究流程企业典型生产加工方式的Flow-shop加工调度问题,分析了求解这一调度问题的各种算法的性能,特别是混合遗传算法中的混合策略,进而提出了一种以启发式搜索算法为前置算法、遗传算法为主体算法、禁忌搜索算法为后置算法的新的混合遗传算法-HSGATS算法,并针对置换Flow-shop调度问题提出了具体的算法设计和实现方法;通过对大量置换Flow--ShopBenchmark问题进行实验求解和其他算法的比较分析,验证了此算法是十分有效的。     

有保质期产品的经济批量调度问题研究

对于经济批量调度问题,以往的研究主要采用公共周期法和基本时段法,这两种方法花费的成本较高且常常得不到可行的调度。本研究采用批量变动法求解此类问题,并考虑产品保质期因素,采用装箱启发式算法求解产品的生产顺序。对仿真实例的计算结果表明,该调度方法花费的成本要低于公共周期法和基本时段法。     

基于GA的时变路网中车辆动态派遣的研究

为了使网络中的车辆调度问题更加符合实际交通状况,针对时变网络中的车辆调度问题进行了研究。将传统车辆调度模型进行了修改,目标函数中考虑了车辆的总行驶费用、总迟到惩罚、车辆总启用费用3种因素,以提高模型的适应性和通用性。由于车辆调度问题属于NP难问题,提出了采用遗传算法对问题进行求解。采用标准的VRP问题进行测试,仿真结果表明该算法简单可行,较BC-Saving启发式算法有更好的求解性能。     

一类Job- shop 车间生产计划和调度的集成优化

讨论一类Job—shop车间的生产计划和调度的集成优化问题，给出了该问题的非线性混合整数规划模型，并采用混合遗传算法进行求解。该模型利用调度约束来细化生产计划，以保证得到可行的调度解。在混合算法中，利用启发式规则来改善初始解集，并采用分段编码策略将计划和调度解映射为染色体。算例研究表明，该算法对求解该类问题具有很好的效果。     

蚁群算法在服务器集群批量任务调度中的应用

服务器集群中的负载均衡和作业调度是影响系统性能的重要因素.本文描述服务器集群批量任务的作业调度问题,对该问题建立了基于图的模型.由于使用一般的启发式算法或动态规划算法解决该问题具有局限性,本文引入蚁群算法进行求解,并针对该问题具体求解提出了启发式距离合适的计算方法.最后在仿真的基础上,讨论了算法的优化效果和收敛性,结果表明蚁群算法解决该问题具有优异的性能.     

半导体黄光区调度问题研究

对半导体黄光区调度问题进行了研究,建立了半导体黄光区调度的数学模型,分别提出了用于求解该问题的启发式方法和粒子群算法方案,阐明了两种算法方案的具体实现过程。通过对仿真实例进行计算和结果比较,表明了粒子群算法优于启发式方法,取得了不错的优化效果。     

求解一类并行多机调度问题的混合启发式算法

该文研究了一类工件具有不同释放时间的并行多机调度问题，调度目标为使总流程时间最小。针对该类调度问题具有强NP—hard的特点，首先构造了的一种启发式算法，该算法能够在很短的时间内找到次优解。由于通常启发式算法会随着问题规模的扩大导致求解的质量有所下降，结合遗传算法的全局搜索能力，提出了一种混合启发式算法进一步改善解的质量。仿真结果表明该算法很好地结合了启发式算法和遗传算法的特点，能够在较短的时间内求解较大规模的调度问题，算法的计算量小，鲁棒性好。     

一种求解置换Flow Shop调度问题的DRPFSP算法

针对置换Flow Shop调度问题,在对经典启发式算法进行研究的基础上,提出了一种用于求解此类问题的DRPFSP算法。算法首先对加工时间矩阵A进行数据标准化处理;然后通过引入一个概率矩阵P2×m和相应的降维函数f_p(A)=PA,将含有m台机器的原问题转化为含2台机器的新问题;再运用Johnson算法对新问题进行求解得到一个调度序列π⁰;最后结合插入邻域快速评价法对π⁰进行处理以获得原问题的一个调度方案π。实验结果表明,相对于经典的启发式算法,DRPFSP算法能更有效地对置换Flow Shop调度问题进行求解。     

柔性Job shop集成化计划调度模型及其求解算法

考虑不同加工工艺路径的成本因素，从集成化的角度研究了柔性Job shop计划和调度问题，针对问题的结构特点，建立了两层混合整数规划模型，提出门槛接受，遗传算法与启发式规则相结合的混合求解算法，综合考虑各层次决策问题进行求解，实例计算表明，该算法可迅速求得问题的近优解，表现出良好的求解性能。     

A heuristic algorithm to minimize total weighted tardiness on a single machine with release times

This paper attempts to solve a single machine‐scheduling problem, in which the objective function is to minimize the total weighted tardiness with different release dates of jobs. To address this scheduling problem, a heuristic scheduling algorithm is presented. A mathematical programming formulation is also formulated to validate the performance of the heuristic scheduling algorithm proposed herein. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. Overall, this algorithm can find the optimal solutions for 2200 out of 2400 randomly generated problems (91.67%). For the most complicated 20 job cases, it requires less than 0.0016 s to obtain an ultimate or even optimal solution. This heuristic scheduling algorithm can therefore efficiently solve this kind of problem.     

基于差分进化算法多处理机任务调度研究

本文主要基于现代启发式差分算法讨论多处理机调度,多处理机调度是NP组合优化问题,目前多采用启发算法。差分进化算法是最近提出的进化算法,主要根据父代个体之间矢量差构造下一代,是一种全局优化搜索方式。本文考虑采用差分进化矢量优先级模型描述调度顺序进行调度,与模拟退火算法比较得到较好调度结果。     

基于蚁群算法的分布多处理机系统任务调度研究

本文主要基于现代蚁群算法讨论分布式系统调度。蚁群算法是一种构造型启发算法,在离散优化问题中得到广泛应用。分布式系统调度属于NP-hard,为了提高算法性能,把问题任务图的优先级作为启发信息。最后,采用随机产生的任务图将调度结果和模拟退火算法、遗传算法等进行了比较。     

一种启发式算法求解批量计划和排序集成问题

文章针对基于JIT思想建立的一种批量计划和作业排序集成问题,建立整体模型,设计了一种启发式算法采用集成方法求求解。针对问题的特点和遗传算法的特性,各层优化时均采用遗传算法求解,借鉴递阶优化方法的思想,首先从优化作业排序层出发,将其优化结果作为约束来优化批量计划层,然后利用利用批量优化的结果再重新来协调优化作业排序层,进而进一步去求解更好的批量计划。基于这种协调传递的思想,使各层的优化形成一个闭环,直到满足循环终止条件,得到比较理想的结果。最后通过算例试验表明,这种启发式算法与采用整体求解方法相比,具有比较满意的寻优性能和收敛速度。     

多机相关任务均匀衡调度问题的复杂性与新算法

本文讨论了多处理机系统中的一种相关任务均衡调度问题 ,证明了该问题是 NP完全问题 ,并给出了一个新的启发式算法。该算法克服了现有算法的不足。数值实例和仿真结果表明 ,该算法有令人满意的优化效果     

一种求解多处理机调度问题的a-平坦化调度算法

在分析多处理机调度问题的基础上,提出了α-平坦的概念,并将其引入到多处理机调度问题中;基于此,提出了一种新的基于α-平坦的求解多处理机调度问题的算法。算法首先对作业集合做平坦化处理,然后再对处理后所得的新问题进行求解,最终获得原调度问题的一个近似解。实验结果表明,通过该算法可以求得较好的结果,相对于其它启发式算法,该算法具有较好的稳定性。     

A Heuristic Algorithm for Task Scheduling Based on Mean Load on Grid

Efficient task scheduling is critical to achieving high performance on grid computing environment. The task scheduling on grid is studied as optimization problem in this paper. A heuristic task scheduling algorithm satisfying resources load balancing on grid environment is presented. The algorithm schedules tasks by employing mean load based on task predictive execution time as heuristic information to obtain an initial scheduling strategy. Then an optimal scheduling strategy is achieved by selecting two machines satisfying condition to change their loads via reassigning their tasks under the heuristic of their mean load. Methods of selecting machines and tasks are given in this paper to increase the throughput of the system and reduce the total waiting time. The efficiency of the algorithm is analyzed and the performance of the proposed algorithm is evaluated via extensive simulation experiments. Experimental results show that the heuristic algorithm performs significantly to ensure high load balancing and achieve an optimal scheduling strategy almost all the time. Furthermore, results show that our algorithm is high efficient in terms of time complexity.     

Two-machine flowshop scheduling with bicriteria problem

This paper attempts to solve a two-machine flowshop bicriteria scheduling problem with release dates for the jobs, in which the objective function is to minimize a weighed sum of total flow time and makespan. To tackle this scheduling problem, an integer programming model with N²+3N variables and 5N constraints where N is the number of jobs, is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, a heuristic scheduling algorithm is presented. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. The average solution quality of the heuristic algorithm is above 99% and is much better than that of the SPT rule as a benchmark. A 15-job case requires only 0.018 s, on average, to obtain an ultimate or even optimal solution. The heuristic scheduling algorithm is a more practical approach to real world applications than the integer programming model.     

树型网格计算环境下的独立任务调度

任务调度是实现高性能网格计算的一个基本问题,然而,设计和实现高效的调度算法是非常具有挑战性的.讨论了在网格资源计算能力和网络通信速度异构的树型计算网格环境下,独立任务的调度问题.与实现最小化任务总的执行时间不同(该问题已被证明是NP难题),为该任务调度问题建立了整数线性规划模型,并从该线性规划模型中得到最优任务分配方案??各计算节点最优任务分配数.然后,基于最优任务分配方案,构造了两种动态的需求驱动的任务分配启发式算法:OPCHATA(optimization-based priority-computation heuristic algorithm for task allocation)和OPBHATA(optimization-basedpriority-bandwidth heuristic algorithm for task allocation).实验结果表明:在异构的树型计算网格环境下实现大量独立任务调度时,该算法的性能明显优于其他算法.     

基于图匹配的多处理机调度算法

本文对具有高通讯延迟的多处理机系统（机群系统）上的任务调度算法进行了研究，与以往算法主要考虑任务图的关键路径不同，本文给出了任务图的调度与其偶图匹配的对应关系，并由此提出了一种新的启发式算法，通过模拟试验显示本算法具有较好的调度效果。