论文部分内容阅读
将NP难的最小化最长完工时间无等待流水作业计划问题等价转化为最小化总空闲时间的问题.分析任务之间的独立性,给出算法基本算子的目标增量性质,通过计算目标增量而不是整个目标函数值来判断新作业计划的优劣,可将算法的时间复杂度降低1阶.提出生成初始作业计划算法,实验分析出迭代构造解和再改进解的有效方法;构造出有效的快速迭代启发式算法FCH(fast composite heuristic).FCH和目前求解该问题的有效算法比较,实验结果表明,FCH接近目前的最好性能,需要最少的计算时间.FCH可为大规模无等待作业计划、实时调度和重调度等问题提供有效方法.
The problem of waiting for no-wait pipeline planning is transformed into the problem of minimizing the total idle time.This paper analyzes the independence between tasks and gives the target incremental properties of algorithm basic operators, Target increment rather than the whole objective function to judge the advantages and disadvantages of the new job plan, the time complexity of the algorithm can be reduced by one step.Analyzing the algorithm of generating initial job plan and experimentally analyzing the effective methods of iterative construction solution and further improvement solution, FCH (fast composite heuristic), which is an efficient fast iterative heuristic algorithm, is constructed. Compared with the current efficient algorithms for solving this problem, the experimental results show that FCH can be a large-scale No waiting for job planning, real-time scheduling and rescheduling issues such as providing an effective method.