GAP REDUCTION TECHNIQUES FOR STOCHASTIC ALGORITHMS

• US 20110099138A1
• Filed: 03/05/2009
• Published: 04/28/2011
• Est. Priority Date: 03/05/2008
• Status: Active Grant

• Current Assignee: Brown University
• Original Assignee: Brown University
• Inventors: Dooms, Gregoire, Van Hentenryck, Pascal
• Granted Patent: US 8,527,444 B2
• Time in Patent Office: Days
• US Class Current: 706/46
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

In one exemplary embodiment of the invention, a method includes: receiving, by an input, input data descriptive of a stochastic scheduling optimization problem; generating, by a processor, at least one solution to the stochastic scheduling optimization problem using a one-step anticipatory algorithm, where the one-step anticipatory algorithm is configured to reduce an anticipatory gap of the stochastic scheduling optimization problem, where the anticipatory gap is a measure of stochasticity of the stochastic scheduling optimization problem, where the one-step anticipatory algorithm operates by determining a set of possible decisions for the stochastic scheduling optimization problem, generating a plurality of scenarios and solving the plurality of scenarios to obtain the at least one solution; and outputting, by an output, the generated at least one solution.

Claims

1. A method comprising:

receiving, by an input, input data descriptive of a stochastic scheduling optimization problem;

generating, by a processor, at least one solution to the stochastic scheduling optimization problem using a one-step anticipatory algorithm, where the one-step anticipatory algorithm is configured to reduce an anticipatory gap of the stochastic scheduling optimization problem, where the anticipatory gap is a measure of stochasticity of the stochastic scheduling optimization problem, where the one-step anticipatory algorithm operates by determining a set of possible decisions for the stochastic scheduling optimization problem, generating a plurality of scenarios and solving the plurality of scenarios to obtain the at least one solution; and

outputting, by an output, the generated at least one solution.

2. The method as in claim 1, where the one-step anticipatory algorithm is configured to reduce the anticipatory gap by inserting at least one delay period.

3. The method as in claim 2, where the one-step anticipatory algorithm inserts the at least one delay period by scheduling at least one dummy activity having no cost, no reward and a duration of one time period.

4. The method as in claim 1, where the one-step anticipatory algorithm is configured to reduce the anticipatory gap by evaluating the anticipatory gap on a training set and computing parameters for a model approximating the anticipatory gap.

5. The method as in claim 1, where the one-step anticipatory algorithm is configured to reduce the anticipatory gap by utilizing time scaling.

6. The method as in claim 1, where the one-step anticipatory algorithm is configured to reduce the anticipatory gap by increasing duration globally by a common factor.

7. The method as in claim 1, where the one-step anticipatory algorithm is configured to reduce the anticipatory gap by scaling only remaining time after a certain decision time of a current state.

8. The method as in claim 1, where the one-step anticipatory algorithm is configured to reduce the anticipatory gap by applying at least two different time scalings to at least two different activities of the stochastic scheduling optimization problem.

9. The method as in claim 1, where the one-step anticipatory algorithm is configured to reduce the anticipatory gap by removing from consideration at least one activity of the stochastic scheduling optimization problem based on expected activity performance.

10. The method as in claim 1, where the one-step anticipatory algorithm is configured to reduce the anticipatory gap by applying at least two different time scalings to at least two different activities of the stochastic scheduling optimization problem based on time spent on successful realizations of the individual activities over a total time spent on the individual activities and by removing from consideration at least one activity of the stochastic scheduling optimization problem based on expected activity performance.

11. The method as in claim 1, where the method is implemented by a computer program stored on a computer-readable medium.

12. An apparatus comprising:

a memory configured to store input data descriptive of a stochastic scheduling optimization problem; and

a processor configured to receive the input data from the memory, to generate at least one solution to the stochastic scheduling optimization problem using a one-step anticipatory algorithm, and to output the generated at least one solution,

where the one-step anticipatory algorithm is configured to reduce an anticipatory gap of the stochastic scheduling optimization problem, where the anticipatory gap is a measure of stochasticity of the stochastic scheduling optimization problem, where the one-step anticipatory algorithm operates by determining a set of possible decisions for the stochastic scheduling optimization problem, generating a plurality of scenarios and solving the plurality of scenarios to obtain the at least one solution.

13. The apparatus as in claim 12, where the one-step anticipatory algorithm is configured to reduce the anticipatory gap by performing at least one of:

inserting at least one delay period, evaluating the anticipatory gap on a training set and computing parameters for a model approximating the anticipatory gap, utilizing time scaling and removing from consideration at least one activity of the stochastic scheduling optimization problem based on expected activity performance.

14. The apparatus as in claim 12, where the one-step anticipatory algorithm is configured to reduce the anticipatory gap by applying at least two different time scalings to at least two different activities of the stochastic scheduling optimization problem based on time spent on successful realizations of the individual activities over a total time spent on the individual activities and by removing from consideration at least one activity of the stochastic scheduling optimization problem based on expected activity performance.

15. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine for performing operations, said operations comprising:

receiving input data descriptive of a stochastic scheduling optimization problem;

generating at least one solution to the stochastic scheduling optimization problem using a one-step anticipatory algorithm, where the one-step anticipatory algorithm is configured to reduce an anticipatory gap of the stochastic scheduling optimization problem, where the anticipatory gap is a measure of stochasticity of the stochastic scheduling optimization problem, where the one-step anticipatory algorithm operates by determining a set of possible decisions for the stochastic scheduling optimization problem, generating a plurality of scenarios and solving the plurality of scenarios to obtain the at least one solution; and

outputting the generated at least one solution.

16. The program storage device as in claim 15, where the one-step anticipatory algorithm is configured to reduce the anticipatory gap by performing at least one of:

inserting at least one delay period, evaluating the anticipatory gap on a training set and computing parameters for a model approximating the anticipatory gap, utilizing time scaling and removing from consideration at least one activity of the stochastic scheduling optimization problem based on expected activity performance.

17. The program storage device as in claim 15, where the one-step anticipatory algorithm is configured to reduce the anticipatory gap by applying at least two different time scalings to at least two different activities of the stochastic scheduling optimization problem based on time spent on successful realizations of the individual activities over a total time spent on the individual activities and by removing from consideration at least one activity of the stochastic scheduling optimization problem based on expected activity performance.