Encoding of a schedule into a binary structure

• US 9,841,990 B2
• Filed: 03/10/2016
• Issued: 12/12/2017
• Est. Priority Date: 08/28/2015
• Status: Expired due to Fees

• Current Assignee: Servicepower Inc.
• Original Assignee: Servicepower Inc.
• Inventors: Syrichas, Alex, Crispin, Alan
• Primary Examiner(s): Kim, Sisley
• Application Number:
  US15/066,104
• Publication Number:
  US 20170060623A1
• Time in Patent Office: 642 Days
• Field of Search: None
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06N 10/00 Quantum computing, i.e. information processing based on quantum-mechanical phenomena
• CPC Class Codes: G06N 10/60 Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• 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
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

A method determines a schedule indicator value for each of a plurality of schedule data entries based on whether each of a set of recorded tasks has been allocated to one or more identifier data names in one or more of a set of time periods in accordance with the first schedule data to generate schedule portion data. A hard constraint indicator value is determined for each of a plurality of hard constraint data entries based on whether at least one hard constraint has been violated by the allocation of the set of recorded tasks to one or more of the identifier data names in one or more of the time periods in accordance with the schedule data to generate hard constraint portion data. The data structure is generated based on the determined schedule portion and hard constraint portion data encoding the schedule data into a data structure.

Claims

1. A method for encoding first schedule data into a data structure for use in a quantum annealing optimization process, the method comprising:

determining, by a process optimization computing device, a schedule indicator value for each of a plurality of schedule data entries based on whether each of a first set of recorded tasks has been allocated to one or more of a plurality of identifier data names in one or more of a first set of time periods in accordance with the first schedule data to generate schedule portion data;

determining, by the process optimization computing device, a hard constraint indicator value for each of a plurality of hard constraint data entries based on whether at least one of a plurality of hard constraints has been violated by the allocation of the first set of recorded tasks to one or more of the plurality of identifier data names in one or more of the first set of time periods in accordance with the first schedule data to generate hard constraint portion data; and

generating, by the process optimization computing device, the data structure for use in a quantum annealing optimization process based on the determined schedule portion data and the determined hard constraint portion data, thereby encoding the first schedule data into a data structure for use in a quantum annealing optimization process.

2. The method according to claim 1 wherein the data structure is a binary data structure, wherein the schedule indicator data entries are binary schedule indicator data entries and wherein the hard constraint data entries are binary hard constraint data entries.

3. The method according to claim 1 wherein the hard constraint data entries indicate, for each identifier data name of the plurality of identifier data names and for each hard constraint of the plurality of hard constraints, whether each of the plurality of hard constraints has been violated by the task allocations for each of the plurality of identifier data names in accordance with the first schedule data.

4. The method according to claim 1 further comprising:

determining, by the process optimization computing device, a task assignment indicator value for each of a plurality of task assignment data entries based on whether each of the first set of recorded tasks has been allocated to one of the plurality of identifier data names in accordance with the first schedule data to generate task assignment portion data,

wherein the generating the data structure is further based on the task assignment portion data.

5. The method according to claim 1 further comprising:

determining, by the process optimization computing device, a conflict indicator value for each of a plurality of conflict data entries based on whether each the plurality of identifier data names has been allocated two or more of the first set of recorded tasks in one or more of the first set of time periods in accordance with the first schedule data to generate conflict portion data,

wherein the generating the data structure is further based on the conflict portion data.

6. The method according to claim 1 further comprising:

receiving, by the process optimization computing device, a set of soft constraints defining one or more soft constraints in the allocation of tasks; and

determining, by the process optimization computing device, a soft constraint indicator value for each of a plurality of soft constraint data entries based on whether each of the plurality of soft constraints has been violated by the allocation of the first set of recorded tasks to one or more of the plurality of identifier data names in one or more of the first set of time periods in accordance with the first schedule data to generate soft constraint portion data,

wherein the generating the data structure is further based on soft constraint portion data.

7. The method according to claim 1 further comprising:

determining, by the process optimization computing device, a condition indicator value for each of a plurality of condition portion data entries based on whether each of a plurality of conditions is met for each of the plurality of identifier data names in accordance with the first schedule data,

wherein the plurality of conditions are used to determine the output of a cost function for the first schedule data for use in the quantum annealing optimization process,

wherein the generating the data structure is further based on the condition portion data.

8. The method according to claim 1 further comprising outputting, by the process optimization computing device, the data structure for the first schedule data to a quantum annealing optimizer.

9. The method according to claim 1 further comprising applying, by the process optimization computing device, a quantum annealing optimization process using the data structure for the first schedule data for identifying a candidate schedule for allocating the first set of recorded tasks to the plurality of identifier data names for the first set of time periods, wherein the candidate schedule meets each of the plurality of hard constraints.

10. The method according to claim 1 wherein the data structure is generated as one of a table or an array.

11. A non-transitory computer readable medium having stored thereon instructions for encoding first schedule data into a data structure for use in a quantum annealing optimization process comprising machine executable code which when executed by a processor, causes the processor to perform steps to and that comprise:

determine a schedule indicator value for each of a plurality of schedule data entries based on whether each of a first set of recorded tasks has been allocated to one or more of a plurality of identifier data names in one or more of a first set of time periods in accordance with the first schedule data to generate schedule portion data;

determine a hard constraint indicator value for each of a plurality of hard constraint data entries based on whether at least one of a plurality of hard constraints has been violated by the allocation of the first set of recorded tasks to one or more of the plurality of identifier data names in one or more of the first set of time periods in accordance with the first schedule data to generate hard constraint portion data; and

generate the data structure for use in a quantum annealing optimization process based on the determined schedule portion data and the determined hard constraint portion data, thereby encoding the first schedule data into a data structure for use in a quantum annealing optimization process.

12. The medium according to claim 11 wherein the data structure is a binary data structure, wherein the schedule indicator data entries are binary schedule indicator data entries and wherein the hard constraint data entries are binary hard constraint data entries.

13. The medium according to claim 11 wherein the hard constraint data entries indicate, for each identifier data name of the plurality of identifier data names and for each hard constraint of the plurality of hard constraints, whether each of the plurality of hard constraints has been violated by the task allocations for each of the plurality of identifier data names in accordance with the first schedule data.

14. The medium according to claim 11, further comprising:

determine a task assignment indicator value for each of a plurality of task assignment data entries based on whether each of the first set of recorded tasks has been allocated to one of the plurality of identifier data names in accordance with the first schedule data to generate task assignment portion data,

wherein the generate the data structure is further based on the task assignment portion data.

15. The medium according to claim 11 further comprising:

determine a conflict indicator value for each of a plurality of conflict data entries based on whether each the plurality of identifier data names has been allocated two or more of the first set of recorded tasks in one or more of the first set of time periods in accordance with the first schedule data to generate conflict portion data,

wherein the generate the data structure is further based on the conflict portion data.

16. The medium according to claim 11 further comprising:

receive a set of soft constraints defining one or more soft constraints in the allocation of tasks; and

determine a soft constraint indicator value for each of a plurality of soft constraint data entries based on whether each of the plurality of soft constraints has been violated by the allocation of the first set of recorded tasks to one or more of the plurality of identifier data names in one or more of the first set of time periods in accordance with the first schedule data to generate soft constraint portion data,

wherein the generate the data structure is further based on soft constraint portion data.

17. The medium according to claim 11 further comprising:

determine a condition indicator value for each of a plurality of condition portion data entries based on whether each of a plurality of conditions is met for each of the plurality of identifier data names in accordance with the first schedule data,

wherein the plurality of conditions are used to determine the output of a cost function for the first schedule data for use in the quantum annealing optimization process,

wherein the generate the data structure is further based on the condition portion data.

18. The medium according to claim 11 further comprising output the data structure for the first schedule data to a quantum annealing optimizer.

19. The medium according to claim 11 further comprising apply a quantum annealing optimization process using the data structure for the first schedule data for identifying a candidate schedule for allocating the first set of recorded tasks to the plurality of identifier data names for the first set of time periods, wherein the candidate schedule meets each of the plurality of hard constraints.

20. The medium according to claim 11 wherein the data structure is generated as one of a table or an array.

21. A process optimization computing device, comprising:

one or more processors;

a memory coupled to the one or more processors which are configured to be capable of executing programmed instructions stored in the memory to and that comprise;

determine a schedule indicator value for each of a plurality of schedule data entries based on whether each of a first set of recorded tasks has been allocated to one or more of a plurality of identifier data names in one or more of a first set of time periods in accordance with the first schedule data to generate schedule portion data;

determine a hard constraint indicator value for each of a plurality of hard constraint data entries based on whether at least one of a plurality of hard constraints has been violated by the allocation of the first set of recorded tasks to one or more of the plurality of identifier data names in one or more of the first set of time periods in accordance with the first schedule data to generate hard constraint portion data; and

generate the data structure for use in a quantum annealing optimization process based on the determined schedule portion data and the determined hard constraint portion data, thereby encoding the first schedule data into a data structure for use in a quantum annealing optimization process.

22. The device according to claim 21 wherein the data structure is a binary data structure, wherein the schedule indicator data entries are binary schedule indicator data entries and wherein the hard constraint data entries are binary hard constraint data entries.

23. The device according to claim 21 wherein the hard constraint data entries indicate, for each identifier data name of the plurality of identifier data names and for each hard constraint of the plurality of hard constraints, whether each of the plurality of hard constraints has been violated by the task allocations for each of the plurality of identifier data names in accordance with the first schedule data.

24. The device according to claim 21, wherein the one or more processors are configured to be capable of executing one or more additional programmed instructions stored in the memory to and that comprise:

determine a task assignment indicator value for each of a plurality of task assignment data entries based on whether each of the first set of recorded tasks has been allocated to one of the plurality of identifier data names in accordance with the first schedule data to generate task assignment portion data,

wherein the generate the data structure is further based on the task assignment portion data.

25. The device according to claim 21 wherein the one or more processors are configured to be capable of executing one or more additional programmed instructions stored in the memory to and that comprise:

determine a conflict indicator value for each of a plurality of conflict data entries based on whether each the plurality of identifier data names has been allocated two or more of the first set of recorded tasks in one or more of the first set of time periods in accordance with the first schedule data to generate conflict portion data,

wherein the generate the data structure is further based on the conflict portion data.

26. The device according to claim 21 wherein the one or more processors are configured to be capable of executing one or more additional programmed instructions stored in the memory to and that comprise:

receive a set of soft constraints defining one or more soft constraints in the allocation of tasks; and

determine a soft constraint indicator value for each of a plurality of soft constraint data entries based on whether each of the plurality of soft constraints has been violated by the allocation of the first set of recorded tasks to one or more of the plurality of identifier data names in one or more of the first set of time periods in accordance with the first schedule data to generate soft constraint portion data,

wherein the generate the data structure is further based on soft constraint portion data.

27. The device according to claim 21 wherein the one or more processors are configured to be capable of executing one or more additional programmed instructions stored in the memory to and that comprise:

determine a condition indicator value for each of a plurality of condition portion data entries based on whether each of a plurality of conditions is met for each of the plurality of identifier data names in accordance with the first schedule data,

wherein the plurality of conditions are used to determine the output of a cost function for the first schedule data for use in the quantum annealing optimization process,

wherein the generate the data structure is further based on the condition portion data.

28. The device according to claim 21 wherein the one or more processors are configured to be capable of executing one or more additional programmed instructions stored in the memory to and that comprise output the data structure for the first schedule data to a quantum annealing optimizer.

29. The device according to claim 21 wherein the one or more processors are configured to be capable of executing one or more additional programmed instructions stored in the memory to and that comprise apply a quantum annealing optimization process using the data structure for the first schedule data for identifying a candidate schedule for allocating the first set of recorded tasks to the plurality of identifier data names for the first set of time periods, wherein the candidate schedule meets each of the plurality of hard constraints.

30. The device according to claim 21 wherein the data structure is generated as one of a table or an array.