首页> 外文期刊>OR Spectrum >Exact and approximate methods for parallel multiple-area spatial scheduling with release times
【24h】

Exact and approximate methods for parallel multiple-area spatial scheduling with release times

机译:具有释放时间的并行多区域空间调度的精确方法和近似方法

获取原文
获取原文并翻译 | 示例
       

摘要

Spatial scheduling problems involve scheduling jobs that each require certain amounts of two-dimensional space within a processing area of limited width and length. Thus, this requires not only assigning time slots to each job but also locations and orientations within the limited physical processing space as well. Such problems, often encountered in shipbuilding and aircraft manufacturing, are generally difficult to solve, and there is a relatively small amount of literature addressing these problems compared to other types of scheduling. In this paper, we consider a particularly complex class of spatial scheduling problems that involve scheduling each job into one of several possible processing areas in parallel to minimize the total amount of tardy time. In addition, each job has a release time before which it may not be processed. We introduce two methods for solving this type of problem: an integer programming (IP) model and a heuristic algorithm. We perform computational tests and comparisons of each method over a large number of generated benchmark problems with varying characteristics, and also compare these to a more naïve heuristic. Solving the IP model was effective for small problems but required excessive amounts of time for larger ones. The heuristic was effective and produced solutions of comparable quality to the IP model for many problems while requiring very little computational time.
机译:空间调度问题涉及调度作业,每个作业都需要在有限的宽度和长度的处理区域内一定量的二维空间。因此,这不仅需要为每个作业分配时隙,而且还需要在有限的物理处理空间内分配位置和方向。在造船和飞机制造中经常遇到的此类问题通常难以解决,与其他类型的调度相比,解决这些问题的文献相对较少。在本文中,我们考虑一类特别复杂的空间调度问题,该问题涉及将每个作业并行调度到几个可能的处理区域之一中,以最大程度地减少延迟时间。此外,每个作业都有一个释放时间,在此之前可能无法处理。我们介绍了两种解决此类问题的方法:整数编程(IP)模型和启发式算法。我们对大量生成的具有不同特征的基准问题进行每种方法的计算测试和比较,并将它们与更简单的启发式方法进行比较。解决IP模型对于小问题有效,但对于大问题则需要大量时间。启发式方法是有效的,并且针对许多问题提供了与IP模型可比的质量的解决方案,同时只需要很少的计算时间。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号