Formal structure-based algorithms for large scale resource scheduling optimization

摘要

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 systematically reduced and the set of values are updated until a feasible solution to the primal resource scheduling problem is obtained. An initial set of multiplier values is further determined by solving a relaxed version of the primal problem where most of the local constraints except the variable bounds are relaxed.