...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Mathematical methods of operations research >Scheduling for a processor sharing system with linear slowdown
【24h】

Scheduling for a processor sharing system with linear slowdown

机译：具有线性放缓的处理器共享系统的调度

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

获取外文期刊封面封底 >>

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

摘要

We consider the problem of scheduling arrivals to a congestion system with a finite number of users having identical deterministic demand sizes. The congestion is of the processor sharing type in the sense that all users in the system at any given time are served simultaneously. However, in contrast to classical processor sharing congestion models, the processing slowdown is proportional to the number of users in the system at any time. That is, the rate of service experienced by all users is linearly decreasing with the number of users. For each user there is an ideal departure time (due date). A centralized scheduling goal is then to select arrival times so as to minimize the total penalty due to deviations from ideal times weighted with sojourn times. Each deviation penalty is assumed quadratic, or more generally convex. But due to the dynamics of the system, the scheduling objective function is non-convex. Specifically, the system objective function is a non-smooth piecewise convex function. Nevertheless, we are able to leverage the structure of the problem to derive an algorithm that finds the global optimum in a (large but) finite number of steps, each involving the solution of a constrained convex program. Further, we put forward several heuristics. The first is the traversal of neighbouring constrained convex programming problems, that is guaranteed to reach a local minimum of the centralized problem. This is a form of a "local search", where we use the problem structure in a novel manner. The second is a one-coordinate "global search", used in coordinate pivot iteration. We then merge these two heuristics into a unified "local-global" heuristic, and numerically illustrate the effectiveness of this heuristic.
机译：我们考虑调度到具有相同确定性需求大小的有限数量的拥塞系统到达的抵达问题。拥塞是处理器共享类型的意义，即在任何给定时间的系统中的所有用户都同时供应。然而，与经典处理器共享拥塞模型相比，处理放缓与系统中的用户数量在任何时候成比例。也就是说，所有用户所经历的服务率是线性减少的用户数量。对于每个用户，有一个理想的出发时间（截止日期）。然后将集中式调度目标选择到达时间，以最小化由于从苏诊断时间加权的理想时间偏差而最小化的总惩罚。每个偏差惩罚都是二次，或更大的凸起的。但由于系统的动态，调度目标函数是非凸的。具体地，系统目标函数是非平滑分段凸起功能。尽管如此，我们能够利用问题的结构来推导出一种算法，该算法在（大但）有限的步骤中找到全局最佳步骤，每个步骤涉及受约束的凸面程序的解决方案。此外，我们提出了几种启发式方法。首先是相邻受限凸编程问题的遍历，保证达到集中问题的局部最小值。这是一种“本地搜索”的形式，在那里我们以新颖的方式使用问题结构。第二是用于坐标迭代迭代的单坐标“全球搜索”。然后，我们将这两个启发式合并到统一的“本地 - 全球”启发式中，以数字方式说明了这种启发式的有效性。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号