• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Proceedings of the Twenty-Third International conference on Automated planning and Scheduling >Optimally Scheduling Small Numbers of Identical Parallel Machines
【24h】

Optimally Scheduling Small Numbers of Identical Parallel Machines

机译：最优地调度少量相同的并行机

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

摘要

Given a set of n different jobs, each with an associated running time, and a set of k identical machines, our task is to assign each job to a machine to minimize the time to complete all jobs. In the OR literature, this is called identical parallel machine scheduling, while in AI it is called number partitioning. For eight or more machines, an OR approach based on bin packing appears best, while for fewer machines, a collection of AI search algorithms perform best. We focus here on scheduling up to seven machines, and make several new contributions. One is a new method that significantly reduces duplicate partitions for all values of k, including k = 2. Another is a new version of the Complete-Karmarkar-Karp (CKK) algorithm that minimizes the makespan. A surprising negative result is that dynamic programming is not competitive for this problem, even for k = 2. We also explore the effect of precision of values on the choice of the best algorithm. Despite the simplicity of this problem, a number of different algorithms have been proposed, and the most efficient algorithm depends on the number of jobs, the number of machines, and the precision of the running times.
机译：给定一组n个不同的作业，每个作业具有关联的运行时间，以及一组k台相同的机器，我们的任务是将每个作业分配给一台机器，以最大程度地减少完成所有作业的时间。在OR文献中，这称为相同并行机调度，而在AI中，其称为数字分区。对于八台或八台以上的计算机，基于bin装箱的OR方法似乎是最好的，而对于较少的计算机，一组AI搜索算法的效果最好。在这里，我们主要关注最多调度七台机器，并做出一些新的贡献。一种是显着减少k的所有值（包括k = 2）的重复分区的新方法，另一种是Complete-Karmarkar-Karp（CKK）算法的新版本，该算法可最大程度地减小制造期。令人惊讶的负面结果是，即使对于k = 2，动态编程也无法解决该问题。我们还探讨了值精度对最佳算法选择的影响。尽管此问题很简单，但已提出了许多不同的算法，而最有效的算法取决于作业数量，机器数量和运行时间的精度。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号