Formal structure-based algorithms for large scale resource scheduling optimization

US8412551B2 · kind B2 · utility

Assignee

• ABB RESEARCH LTD. · CH

Inventors

• Xiaoming Feng · Cary, US
• Yuan Liao · Cary, US
• John D. Finney · Raleigh, US
• Adolfo Fonseca · Raleigh, US

Key dates

• Filing date: Oct 21, 2004
• Grant date: Apr 2, 2013
• Expiry date: Aug 13, 2029

Classification

• Technology area (CPC G): Physics
• CPC primary: G06Q10/06314
• WIPO field: IT methods for management
• WIPO sector: Electrical engineering

Abstract

A method and computer program product for optimization of large scale resource scheduling problems. Large scale resource scheduling problems are computationally very hard and extremely time consuming to solve. This invention provides a Lagrangian relaxation based solution method. The method has two distinct characteristics. First, the method is formal. It is completely structure-based and does not use any problem domain specific knowledge in the solution process, either in the dual optimization or the primal feasibility enforcement process. Second, updating the Lagrangian multipliers after solution of every sub-problem without using penalty factors results in fast and smooth convergence in the dual optimization. The combination of high quality dual solution and the structure-based primal feasibility enforcement produces a high quality primal solution with very small solution gap. An optimal solution is first found to the dual of the resource scheduling problem by sequentially finding a solution to a plurality of sub-problems and updating a set of values used in the dual problem formulation after each sub-problem solution is obtained. Coupling constraint violations are systematicall…