• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Workshop on Approximation and Online Algorithms >Non-clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times
【24h】

Non-clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times

机译：非批长调度，以最小化具有设置时间的机器上的最大流量时间

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Consider a problem in which n jobs that are classified into k types arrive over time at their release times and are to be scheduled on a single machine so as to minimize the maximum flow time. The machine requires a setup taking s time units whenever it switches from processing jobs of one type to jobs of a different type. We consider the problem as an online problem where each job is only known to the scheduler as soon as it arrives and where the processing time of a job only becomes known upon its completion (non-clairvoyance). We are interested in the potential of simple "greedy-like" algorithms. We analyze a modification of the FIFO strategy and show its competitiveness to be Θ({the square root of}n), which is optimal for the considered class of algorithms. For k = 2 types it achieves a constant competitiveness. Our main insight is obtained by an analysis of the smoothed competitiveness. If processing times p_j are independently perturbed to p_j = (1 + X_j)_(p_j), we obtain a competitiveness of O(σ~(-2) log~2 n) when X_j is drawn from a uniform or a (truncated) normal distribution with standard deviation σ. The result proves that bad instances are fragile and "practically" one might expect a much better performance than given by the Ω({the square root of}n)-bound.
机译：考虑一个问题，其中分类为k类型的作业在其释放时间内到达时间，并且要在单个机器上调度，以便最小化最大流量时间。每当它从处理One类型的作业切换到不同类型的作业时，机器需要采用时间单位的设置。我们将问题视为一个在线问题，其中每个作业只在调度器到达时才已知，并且在其完成时只知道作业的处理时间（非Clairvoyance）。我们对简单“贪婪”算法的潜力感兴趣。我们分析了FIFO策略的修改，并呈现为θ（{n的平方根）的竞争力，这对于考虑的算法类是最佳的。对于k = 2种，它实现了持续的竞争力。我们的主要见解是通过分析平滑竞争力而获得的。如果处理次数P_J独立地扰乱P_J =（1 + X_J）_（P_J），则当X_J从均匀或A（截断）绘制时，我们获得O（Σ〜（-2）log〜2 n）的竞争力标准偏差σ正态分布。结果证明，错误的实例是脆弱的，“实际上”可能期望比ω（{n的平方根）给出的性能更好。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号