...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Exact and heuristic solution approaches for the Integrated Job Scheduling and Constrained Network Routing Problem
【24h】

Exact and heuristic solution approaches for the Integrated Job Scheduling and Constrained Network Routing Problem

机译：集成作业调度和受限网络路由问题的精确启发式解决方案

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper examines the problem of scheduling a number of jobs on a finite set of machines such that the overall profit of executed jobs is maximized. Each job has a certain demand, which must be sent to the executing machine via constrained paths. A job cannot start before all its demands have arrived at the machine. Furthermore, two resource demand transmissions cannot use the same edge in the same time period. The problem has application in grid computing, where a number of geographically distributed machines work together for solving large problems. The machines are connected through an optical network. The problem is formulated as an IP problem and is shown to be NP-hard. An exact solution approach based on Dantzig–Wolfe decomposition is proposed. Also, several heuristic methods are developed by combining heuristics for the job scheduling problem and for the constrained network routing problem. The methods are computationally evaluated on test instances arising from telecommunications with up to 500 jobs and 500 machines. Results show that solving the integrated job scheduling and constrained network routing problem to optimality is very difficult. The exact solution approach performs better than using a standard IP-solver; however, it is still unable to solve several instances. The proposed heuristics generally have good performance. Especially, the First Come First Serve scheduling heuristic combined with a routing strategy, which proposes several good routes for each demand, has good performance with an average solution value gap of 3%. All heuristics have very small running times.
机译：本文研究了在有限的一组机器上调度多个作业的问题，以使已执行作业的总利润最大化。每个作业都有一定的需求，必须通过约束路径将其发送到执行机器。作业无法在其所有需求到达机器之前就开始。此外，两个资源需求传输不能在相同时间段内使用相同的边缘。该问题已在网格计算中得到应用，在网格计算中，许多地理上分散的机器协同工作以解决大问题。机器通过光网络连接。该问题被表述为IP问题，并且显示为NP难题。提出了一种基于Dantzig-Wolfe分解的精确求解方法。而且，通过结合用于作业调度问题和约束网络路由问题的启发式方法，开发了几种启发式方法。这些方法是在具有多达500个作业和500台计算机的电信测试实例上进行计算评估的。结果表明，将集成的作业调度和约束的网络路由问题解决到最优是非常困难的。精确的解决方案方法比使用标准IP解决方案的性能更好。但是，它仍然无法解决多个实例。所提出的启发式方法通常具有良好的性能。特别是，“先来先服务”调度启发式方法与路由策略相结合，可以为每个需求提供多个良好的路由，并且具有良好的性能，平均解决方案价值差距为3％。所有启发式方法的运行时间都非常短。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号