公开(公告)号：US20110246994A1

公开(公告)日：2011-10-06

申请号：US12755089

申请日：2010-04-06

申请人： Tracy J. Kimbrel ,  Tarun Kumar ,  Kevin D. McKenzie ,  Richard D. Prewitt, JR. ,  Maxim Sviridenko ,  Debra Tomkowid

发明人： Tracy J. Kimbrel ,  Tarun Kumar ,  Kevin D. McKenzie ,  Richard D. Prewitt, JR. ,  Maxim Sviridenko ,  Debra Tomkowid

IPC分类号： G06F9/46

CPC分类号： G06Q10/06 ,  G06F9/5027 ,  G06F9/5077 ,  G06F2209/5021 ,  G06F2209/506 ,  G06Q10/10

摘要： A system and method that provides an automated solution to obtaining quality scheduling for users of computing resources. The system, implemented in an enterprise software test center, collects information from test-shop personnel about test machine features and availability, test jobs, and tester preferences and constraints. The system reformulates this testing information as a system of constraints. An optimizing scheduling engine computes efficient schedules whereby all the jobs are feasibly scheduled while satisfying the users' time preferences to the greatest extent possible. The method and system achieves fairness: if all preferences can not be meet, it is attempted to evenly distribute violations of preferences across the users. The test scheduling is generated according to a first application of a greedy algorithm that finds an initial feasible assignment of jobs. The second is a local search algorithm that improves the initial greedy solution.

摘要翻译： 提供自动解决方案以获得计算资源用户的质量调度的系统和方法。 在企业软件测试中心实施的系统从测试人员收集关于测试机特性和可用性，测试作业以及测试者偏好和限制的信息。 该系统将这个测试信息重新定义为一个约束系统。 优化调度引擎计算有效的时间表，其中所有作业都被可行地调度，同时最大限度地满足用户的时间偏好。 该方法和系统实现公平性：如果所有偏好都不能满足，则尝试在用户之间均匀分布违反偏好的行为。 测试调度是根据找到作业的初始可行分配的贪心算法的第一应用产生的。 第二个是本地搜索算法，改进了初始的贪心解决方案。

公开(公告)号：US07765301B1

公开(公告)日：2010-07-27

申请号：US11352328

申请日：2006-02-13

申请人： Tracy J. Kimbrel ,  Robert Krauthgamer ,  Maria Minkoff ,  Baruch M. Schieber ,  Maxim I. Sviridenko ,  Jayram S. Thathachar

发明人： Tracy J. Kimbrel ,  Robert Krauthgamer ,  Maria Minkoff ,  Baruch M. Schieber ,  Maxim I. Sviridenko ,  Jayram S. Thathachar

IPC分类号： G06F15/16 ,  G06F17/30

CPC分类号： G06F9/50 ,  G06Q10/063 ,  G06Q10/06315 ,  H04L29/06 ,  H04L67/1002 ,  H04L67/1008 ,  H04L67/1023 ,  H04L2029/06054

摘要： A benefit task system implements a policy for allocating resources to yield some benefit. The method implemented may be applied to a variety of problems, and the benefit may be either tangible (e.g., profit) or intangible (e.g., customer satisfaction). In one example, the method is applied to server allocation in a Web site server “farm” given full information regarding future loads to maximize profits for the Web hosting service provider. In another example, the method is applied to the allocation of telephone help in a way to improve customer satisfaction. In yet another example, the method is applied to distributed computing problem where the resources to be allocated are general purpose computers connected in a network and used to solve computationally intensive problems. Solution of the Web server “farm” problem is based on information regarding future loads to achieve close to the greatest possible revenue based on the assumption that revenue is proportional to the utilization of servers and differentiated by customer class. The method of server allocation uses an approach which reduces the Web server farm problem to a minimum-cost network flow problem, which can be solved in polynomial time. Similar solutions are applicable to other resource allocation problems.

摘要翻译： 利益任务系统实施分配资源以产生一些益处的政策。 实施的方法可以应用于各种问题，并且益处可以是有形的（例如，利润）或无形的（例如，客户满意度）。 在一个示例中，该方法应用于Web站点服务器“farm”中的服务器分配，给出了有关未来负载的完整信息以最大化Web托管服务提供商的利润。 在另一个例子中，该方法应用于电话帮助的分配，以提高客户满意度。 在另一个例子中，该方法应用于分布式计算问题，其中待分配的资源是连接在网络中的通用计算机，并用于解决计算密集型问题。 Web服务器“农场”问题的解决方案是基于有关未来负载的信息，以实现接近最大收入的假设，即假设收入与服务器的利用率成正比，并根据客户类别进行区分。 服务器分配的方法使用一种将Web服务器场问题降低到最小成本网络流问题的方法，可以在多项式时间内解决。 类似的解决方案适用于其他资源分配问题。

公开(公告)号：US07308415B2

公开(公告)日：2007-12-11

申请号：US10000149

申请日：2001-12-04

申请人： Tracy J. Kimbrel ,  Robert Krauthgamer ,  Maria Minkoff ,  Baruch M. Schieber ,  Maxim I. Sviridenko ,  Jayram S. Thathachar

发明人： Tracy J. Kimbrel ,  Robert Krauthgamer ,  Maria Minkoff ,  Baruch M. Schieber ,  Maxim I. Sviridenko ,  Jayram S. Thathachar

IPC分类号： G06F9/46

CPC分类号： G06F9/50 ,  G06Q10/0631 ,  G06Q10/06312 ,  G06Q10/06315 ,  H04L67/1002 ,  H04L67/1008 ,  H04L67/1023

摘要： A method for server allocation in a Web server “farm” is based on limited information regarding future loads to achieve close to the greatest possible revenue based on the assumption that revenue is proportional to the utilization of servers and differentiated by customer class. The method of server allocation uses an approach of “discounting the future”. Specifically, when the policy faces the choice between a guaranteed benefit immediately and a potential benefit in the future, the decision is made by comparing the guaranteed benefit value with a discounted value of the potential future benefit. This discount factor is exponential in the number of time units that it would take a potential benefit to be materialized. The future benefits are discounted because by the time a benefit will be materialized, things might change and the algorithm might decide to make another choice for a potential (even greater) benefit.

摘要翻译： Web服务器“farm”中的服务器分配方法基于有限的关于未来负载的信息，以实现接近最大可能收入的假设，即假设收入与服务器的利用率成正比，并根据客户类别区分。 服务器分配的方法采用“贴现未来”的方法。 具体来说，当政策面临保证收益立即与潜在利益之间的选择时，通过将担保收益值与潜在未来收益的折扣价值进行比较来做出决策。 这个折扣因子是要实现潜在收益的时间单位数量的指数。 未来的利益是折扣的，因为在实现利益的时候，事情可能会改变，算法可能决定为潜力（甚至更大）的利益作出另一个选择。

公开(公告)号：US07546247B2

公开(公告)日：2009-06-09

申请号：US11861663

申请日：2007-09-26

申请人： Tracy J. Kimbrel ,  Robert Krauthgarner ,  Baruch M. Schieber ,  Maxim I. Sviridenko ,  Jayram S. Thathachar

发明人： Tracy J. Kimbrel ,  Robert Krauthgarner ,  Baruch M. Schieber ,  Maxim I. Sviridenko ,  Jayram S. Thathachar

IPC分类号： G06F17/30

CPC分类号： G06F9/50 ,  G06Q10/0631 ,  G06Q10/06312 ,  G06Q10/06315 ,  H04L67/1002 ,  H04L67/1008 ,  H04L67/1023

摘要： A method for server allocation in a Web server “farm” is based on limited information regarding future loads to achieve close to the greatest possible revenue based on the assumption that revenue is proportional to the utilization of servers and differentiated by customer class. The method of server allocation uses an approach of “discounting the future”. Specifically, when the policy faces the choice between a guaranteed benefit immediately and a potential benefit in the future, the decision is made by comparing the guaranteed benefit value with a discounted value of the potential future benefit. This discount factor is exponential in the number of time units that it would take a potential benefit to be materialized. The future benefits are discounted because by the time a benefit will be materialized, things might change and the algorithm might decide to make another choice for a potential (even greater) benefit.

摘要翻译： Web服务器“farm”中的服务器分配方法基于有限的关于未来负载的信息，以实现接近最大可能收入的假设，即假设收入与服务器的利用率成正比，并根据客户类别区分。 服务器分配的方法采用“贴现未来”的方法。 具体来说，当政策面临保证收益立即与潜在利益之间的选择时，通过将担保收益值与潜在未来收益的折扣价值进行比较来做出决策。 这个折扣因子是要实现潜在收益的时间单位数量的指数。 未来的利益是折扣的，因为在实现利益的时候，事情可能会改变，算法可能决定为潜力（甚至更大）的利益作出另一个选择。

公开(公告)号：US08392926B2

公开(公告)日：2013-03-05

申请号：US12755089

申请日：2010-04-06

申请人： Tracy J. Kimbrel ,  Tarun Kumar ,  Kevin D. McKenzie ,  Richard D. Prewitt, Jr. ,  Maxim Sviridenko ,  Debra Tomkowid

发明人： Tracy J. Kimbrel ,  Tarun Kumar ,  Kevin D. McKenzie ,  Richard D. Prewitt, Jr. ,  Maxim Sviridenko ,  Debra Tomkowid

IPC分类号： G06F9/46

CPC分类号： G06Q10/06 ,  G06F9/5027 ,  G06F9/5077 ,  G06F2209/5021 ,  G06F2209/506 ,  G06Q10/10

摘要： A system and method that provides an automated solution to obtaining quality scheduling for users of computing resources. The system, implemented in an enterprise software test center, collects information from test-shop personnel about test machine features and availability, test jobs, and tester preferences and constraints. The system reformulates this testing information as a system of constraints. An optimizing scheduling engine computes efficient schedules whereby all the jobs are feasibly scheduled while satisfying the users' time preferences to the greatest extent possible. The method and system achieves fairness: if all preferences can not be meet, it is attempted to evenly distribute violations of preferences across the users. The test scheduling is generated according to a first application of a greedy algorithm that finds an initial feasible assignment of jobs. The second is a local search algorithm that improves the initial greedy solution.

摘要翻译： 提供自动解决方案以获得计算资源用户的质量调度的系统和方法。 在企业软件测试中心实施的系统从测试人员收集关于测试机特性和可用性，测试作业以及测试者偏好和限制的信息。 该系统将这个测试信息重新定义为一个约束系统。 优化调度引擎计算有效的时间表，其中所有作业都被可行地调度，同时最大限度地满足用户的时间偏好。 该方法和系统实现公平性：如果所有偏好都不能满足，则尝试在用户之间均匀分布违反偏好的行为。 测试调度是根据找到作业的初始可行分配的贪心算法的第一应用产生的。 第二个是本地搜索算法，改进了初始的贪心解决方案。

公开(公告)号：US07085837B2

公开(公告)日：2006-08-01

申请号：US10000320

申请日：2001-12-04

申请人： Tracy J. Kimbrel ,  Robert Krauthgamer ,  Baruch M. Schieber ,  Maxim I. Sviridenko ,  Jayram S. Thathachar ,  Maria Minkoff

发明人： Tracy J. Kimbrel ,  Robert Krauthgamer ,  Baruch M. Schieber ,  Maxim I. Sviridenko ,  Jayram S. Thathachar ,  Maria Minkoff

IPC分类号： G06F13/00

CPC分类号： G06F9/50 ,  G06Q10/063 ,  G06Q10/06315 ,  H04L29/06 ,  H04L67/1002 ,  H04L67/1008 ,  H04L67/1023 ,  H04L2029/06054

摘要： A benefit task system implements a policy for allocating resources to yield some benefit. The method implemented may be applied to a variety of problems, and the benefit may be either tangible (e.g., profit) or intangible (e.g., customer satisfaction). In one example, the method is applied to server allocation in a Web site server “farm” given full information regarding future loads to maximize profits for the Web hosting service provider. In another example, the method is applied to the allocation of telephone help in a way to improve customer satisfaction. In yet another example, the method is applied to distributed computing problem where the resources to be allocated are general purpose computers connected in a network and used to solve computationally intensive problems. Solution of the Web server “farm” problem is based on information regarding future loads to achieve close to the greatest possible revenue based on the assumption that revenue is proportional to the utilization of servers and differentiated by customer class. The method of server allocation uses an approach which reduces the Web server farm problem to a minimum-cost network flow problem, which can be solved in polynomial time. Similar solutions are applicable to other resource allocation problems.