Using constraint programming to obtain a machine maintenance schedule for maintenance tasks

Abstract

Information about a set of maintenance tasks and time windows includes a cost value per task per time window. Based on the information, a data model generator generates a data model, including task elements; time elements; cost elements; a total cost element; a constraint that requires each task element be assigned a time window from a respective domain, such that each time element is assigned a task count from a respective domain; a constraint that requires each cost element be assigned a cost value associated with a time window assigned (or to be assigned) to a task element corresponding to the cost element; and a constraint that requires the total cost element be assigned a total cost value that is a sum of the cost values assigned (or to be assigned) to the cost elements. Based on the data model, a CP solver determines a proposed maintenance schedule.

What is claimed is: 
     
       1. A method, comprising:
 identifying a set of machine maintenance tasks to be performed for a set of machines; 
 identifying a set of time windows for performing the set of machine maintenance tasks; 
 identifying a set of cost values for performing the set of machine maintenance tasks during the set of time windows; 
 generating a constraint programming data model, comprising:
 specifying a set of task elements representing the set of machine maintenance tasks;
 wherein a domain of a first task element, of the set of task elements, indicates possible time windows to be assigned to the first task element; and 
 wherein the possible time windows includes at least a subset of the set of time windows; 
 
 specifying a set of time elements representing at least the set of time windows;
 wherein a domain of a first time element, of the set of time elements, indicates possible task counts to be assigned to the first time element; 
 
 specifying a set of cost elements corresponding to the set of task elements;
 wherein a domain of a first cost element, of the set of cost elements, indicates possible cost values to be assigned to the first cost element; and 
 wherein the possible cost values includes at least a subset of the set of cost values; 
 
 specifying a total cost element;
 wherein a domain of the total cost element indicates possible total cost values to be assigned to the total cost element; 
 
 specifying a first constraint requiring at least that a first time window assigned to the first task element is one of the possible time windows, and a first task count assigned to the first time element is one of the possible task counts; 
 specifying a second constraint requiring at least that the first cost element be assigned with a first cost value that is (a) one of the possible cost values and (b) is associated with performing a first machine maintenance task, represented by the first task element, during the first time window; 
 specifying a third constraint requiring that the total cost element be assigned with a first total cost value that is (a) one of the possible total cost values and (b) is a sum of respective cost values assigned, or to be assigned, to the set of cost elements; 
 
 iteratively applying at least the constraint programming data model to a constraint programming solver to determine a set of one or more solutions satisfying at least the first constraint, the second constraint, and the third constraint, wherein the constraint programming solver is configured to computationally perform one or more of a backtracking algorithm or a forward-checking algorithm to determine the set of one or more solutions; 
 determining that, out of the set of solutions, a particular solution is associated with the total cost element that is assigned with a lowest total cost value; 
 returning a particular proposed machine maintenance schedule, for the set of machines, based on the particular solution, 
 wherein at least a subset of the set of machine maintenance tasks is executed according to the particular proposed machine maintenance schedule; 
 wherein the method is performed by one or more devices, each including one or more hardware processors. 
 
     
     
       2. One or more non-transitory machine-readable media storing instructions which, when executed by one or more processors, cause:
 identifying a set of machine maintenance tasks to be performed for a set of machines; 
 identifying a set of time windows for performing the set of machine maintenance tasks; 
 identifying a set of cost values for performing the set of machine maintenance tasks during the set of time windows; 
 generating a constraint programming data model, comprising:
 specifying a set of task elements representing the set of machine maintenance tasks;
 wherein a domain of a first task element, of the set of task elements, indicates possible time windows to be assigned to the first task element; and 
 wherein the possible time windows includes at least a subset of the set of time windows; 
 
 specifying a set of time elements representing at least the set of time windows;
 wherein a domain of a first time element, of the set of time elements, indicates possible task counts to be assigned to the first time element; 
 
 specifying a set of cost elements corresponding to the set of task elements;
 wherein a domain of a first cost element, of the set of cost elements, indicates possible cost values to be assigned to the first cost element; and 
 wherein the possible cost values includes at least a subset of the set of cost values; 
 
 specifying a total cost element;
 wherein a domain of the total cost element indicates possible total cost values to be assigned to the total cost element; 
 
 specifying a first constraint requiring at least that a first time window assigned to the first task element is one of the possible time windows, and a first task count assigned to the first time element is one of the possible task counts; 
 specifying a second constraint requiring at least that the first cost element be assigned with a first cost value that is (a) one of the possible cost values and (b) is associated with performing a first machine maintenance task, represented by the first task element, during the first time window; 
 specifying a third constraint requiring that the total cost element be assigned with a first total cost value that is (a) one of the possible total cost values and (b) is a sum of respective cost values assigned, or to be assigned, to the set of cost elements; 
 
 iteratively applying at least the constraint programming data model to a constraint programming solver to determine a set of one or more solutions satisfying at least the first constraint, the second constraint, and the third constraint, wherein the constraint programming solver is configured to computationally perform one or more of a backtracking algorithm or a forward-checking algorithm to determine the set of one or more solutions; 
 determining that, out of the set of solutions, a particular solution is associated with the total cost element that is assigned with a lowest total cost value; 
 returning a particular proposed machine maintenance schedule, for the set of machines, based on the particular solution, 
 wherein at least a subset of the set of machine maintenance tasks is executed according to the particular proposed machine maintenance schedule. 
 
     
     
       3. The one or more media of  claim 2 , wherein iteratively applying at least the constraint programming data model to the constraint programming solver to determine the set of solutions comprises:
 applying at least the constraint programming data model to the constraint programming solver to applying at least the constraint programming data model to the constraint programming solver to determine a first solution of the set of solutions; 
 determining a first total cost value assigned to the total cost element associated with the first solution; 
 modifying the constraint programming data model, wherein modifying the constraint programming data model comprises:
 removing, from the domain of the total cost element, any total cost values that are greater than or equal to the first total cost value; 
 
 applying at least the constraint programming data model that has been modified to the constraint programming solver to determine a second solution of the set of solutions; 
 wherein a second total cost value assigned to the total cost element associated with the second solution is less than the first total cost value. 
 
     
     
       4. The one or more media of  claim 2 , wherein:
 iteratively applying at least the constraint programming data model to the constraint programming solver to determine the set of solutions comprises:
 applying at least the constraint programming data model to the constraint programming solver to determine a first solution of the set of solutions; 
 determining a first total cost value assigned to the total cost element associated with the first solution; 
 modifying the constraint programming data model, wherein modifying the constraint programming data model comprises:
 removing, from the domain of the total cost element, any total cost values that are greater than or equal to the first total cost value; 
 
 applying at least the constraint programming data model that has been modified to the constraint programming solver; 
 determining that no solution is possible for the constraint programming model that has been modified; 
 
 determining that, out of the set of solutions, the particular solution is associated with the total cost element that is assigned with the lowest total cost value comprises:
 responsive to (a) determining that no solution is possible for the constraint programming model that has been modified and (b) determining that a last-determined solution, out of the set of solutions, is the first solution:
 identifying the first solution as the particular solution associated with the total cost element that is assigned with the lowest total cost value. 
 
 
 
     
     
       5. The one or more media of  claim 2 , wherein iteratively applying at least the constraint programming data model to the constraint programming solver to determine the set of solutions comprises:
 identifying a particular value between a lowest total cost value, out of the possible total cost values in the domain of the total cost element and a highest total cost value, out of the possible total cost values in the domain of the total cost element, as an initial cutoff value; 
 modifying the constraint programming model, wherein modifying the constraint programming model comprises:
 removing, from the domain of the total cost element, any total cost values that are greater than or equal to the initial cutoff value; 
 
 applying at least the constraint programming model that has been modified to the constraint programming solver to determine a first solution of the set of solutions; 
 wherein a first total cost value assigned to the total cost element associated with the first solution is less than the initial cutoff value. 
 
     
     
       6. The one or more media of  claim 2 , wherein the set of solutions comprises all possible solutions for the constraint programming data model. 
     
     
       7. The one or more media of  claim 2 , wherein returning the particular proposed machine maintenance schedule is responsive to receiving an interrupt to an iterative process for minimizing the total cost element. 
     
     
       8. The one or more media of  claim 7 , further storing instructions which cause:
 subsequent to returning the particular proposed machine maintenance schedule responsive to receiving the interrupt:
 resuming iteratively applying at least the constraint programming data model to the constraint programming solver to determine a second solution; 
 wherein a first total cost value assigned to the total cost element associated with the particular solution is greater than a second total cost value assigned to the total cost element associated with the second solution; 
 returning a second proposed machine maintenance schedule based on the second solution. 
 
 
     
     
       9. The one or more media of  claim 2 , further storing instructions which cause:
 determining a subset of the cost values that is associated with performing the first machine maintenance task on a first machine, of the set of machines, during the possible time windows based at least on a first machine attribute associated with the first machine. 
 
     
     
       10. The one or more media of  claim 9 , wherein the first machine attribute comprises one or more of: a failure probability of the first machine, and a production schedule of the first machine. 
     
     
       11. The one or more media of  claim 9 , wherein an effect on each of the subset of the set of cost values due to the first machine attribute is same. 
     
     
       12. The one or more media of  claim 2 , further storing instructions which cause:
 determining a subset of the set of cost values that is associated with performing the first machine maintenance task during the possible time windows based at least on a first task attribute associated with the first machine maintenance task. 
 
     
     
       13. The one or more media of  claim 12 , wherein the first task attribute comprises one or more of:
 a particular time window, of the set of time windows, assigned to the first machine maintenance task according to a current machine maintenance schedule; and 
 a time window restriction for the first machine maintenance task. 
 
     
     
       14. The one or more media of  claim 2 , further storing instructions which cause:
 determining that a particular time window, of the set of time windows, is assigned to the first machine maintenance task according to a current machine maintenance schedule; 
 determining a first cost value for performing the first machine maintenance task during the first time window; 
 determining a second cost value for performing the first machine maintenance task during a second time window of the set of time windows; 
 wherein a first difference between the particular time window and the first time window is less than a second difference between the particular time window and the second time window; 
 wherein a first effect on the first cost value due to the first difference is less than a second effect on the second cost value due to the second difference. 
 
     
     
       15. The one or more media of  claim 2 , further storing instructions which cause:
 generating a constraint programming search directive, comprising:
 specifying one or more operations for prioritizing assignment of the first task element with a time window of the set of time windows that is (a) nearest to a particular time window assigned to the first machine maintenance task according to a current maintenance schedule and (b) remains available. 
 
 
     
     
       16. The one or more media of  claim 2 , wherein generating the constraint programming data model further comprises:
 specifying a fourth constraint requiring that the first time window assigned to the first task element be before a second time window assigned to a second task element of the set of task elements. 
 
     
     
       17. The one or more media of  claim 2 , wherein generating the constraint programming data model further comprises one of:
 specifying a fourth constraint requiring that the first time window assigned to the first task element and a second time window assigned to a second task element of the set of task elements be same; or 
 specifying a fifth constraint requiring that the first time window assigned to the first task element and a second time window assigned to a second task element of the set of task elements be different. 
 
     
     
       18. The one or more media of  claim 2 , wherein generating the constraint programming data model further comprises:
 specifying a soft constraint indicating a preference for assigning a time window of the set of time windows to the first task element that is nearest to a particular time window. 
 
     
     
       19. The one or more media of  claim 2 , wherein:
 the possible time windows further includes an overflow time window, wherein any of the set of task elements assigned with the overflow time window is not performed according to the particular proposed maintenance schedule; 
 the possible cost values further includes an overflow cost value associated with the overflow time window, wherein the overflow cost value is greater than each of the set of cost values. 
 
     
     
       20. The one or more media of  claim 2 , further storing instructions which, when executed by the one or more processors, cause:
 generating a set of instructions which, when executed by a second set of one or more hardware processors, cause performance of at least a subset of the set of machine maintenance tasks according to the particular proposed machine maintenance schedule. 
 
     
     
       21. The one or more media of  claim 2 , further storing instructions which, when executed by the one or more processors, cause:
 presenting, at a graphical user interface (GUI), a current machine maintenance schedule for performing at least a subset of the set of machine maintenance tasks; 
 overlaying the particular proposed machine maintenance schedule on top of the current machine maintenance schedule. 
 
     
     
       22. The one or more media of  claim 2 , wherein the particular proposed maintenance schedule indicates that the first machine maintenance task is scheduled for the first time window. 
     
     
       23. The one or more media of  claim 2 , further storing instructions which cause:
 determining a subset of the cost values that is associated with performing the first machine maintenance task on a first machine, of the set of machines, during the possible time windows based at least on (a) a first machine attribute associated with the first machine, and (b) a first task attribute associated with the first machine maintenance task;
 wherein the first machine attribute comprises one or more of: (a) a failure probability of the first machine, and (b) a production schedule of the first machine; 
 wherein the first task attribute comprises one or more of: (a) a particular time window, of the set of time windows, assigned to the first machine maintenance task according to a current machine maintenance schedule, and (b) a time window restriction for the first machine maintenance task; 
 
 generating a set of instructions which, when executed by a second set of one or more hardware processors, cause performance of at least a subset of the set of machine maintenance tasks according to the particular proposed machine maintenance schedule; 
 presenting, at a graphical user interface (GUI), a current machine maintenance schedule for performing at least a subset of the set of machine maintenance tasks; 
 overlaying the particular proposed machine maintenance schedule on top of the current machine maintenance schedule; 
 wherein: 
 generating the constraint programming data model further comprises one or more of:
 specifying a fourth constraint requiring that the first time window assigned to the first task element be before a second time window assigned to a second task element of the set of task elements; 
 specifying a fifth constraint requiring that the first time window assigned to the first task element and a third time window assigned to a third task element of the set of task elements be same; 
 specifying a sixth constraint requiring that the first time window assigned to the first task element and a fourth time window assigned to a fourth task element of the set of task elements be different; 
 
 iteratively applying at least the constraint programming data model to the constraint programming solver to determine the set of solutions comprises:
 identifying a particular value between a lowest total cost value, out of the possible total cost values in the domain of the total cost element and a highest total cost value, out of the possible total cost values in the domain of the total cost element, as an initial cutoff value; 
 modifying the constraint programming model, wherein modifying the constraint programming model comprises: 
 removing, from the domain of the total cost element, any total cost values that are greater than or equal to the initial cutoff value; 
 applying at least the constraint programming model, which has been modified to exclude any total cost values greater than or equal to the initial cutoff value from the domain of the total cost element, to the constraint programming solver to determine a first solution of the set of solutions; 
 responsive to receiving an interrupt: returning a temporary proposed machine maintenance schedule based on the first solution; 
 subsequent to receiving the interrupt: 
 determining a first total cost value assigned to the total cost element associated with the first solution, wherein the first total cost value assigned to the total cost element associated with the first solution is less than the initial cutoff value; 
 modifying the constraint programming data model, wherein modifying the constraint programming data model comprises: 
 removing, from the domain of the total cost element, any total cost values that are greater than or equal to the first total cost value; 
 applying at least the constraint programming data model, which has been modified to exclude any total cost values greater than or equal to the first total cost value from the domain of the total cost element, to the constraint programming solver to determine a second solution of the set of solutions; 
 determining a second total cost value assigned to the total cost element associated with the second solution, wherein the second total cost value is less than the first total cost value; 
 modifying the constraint programming data model, wherein modifying the constraint programming data model comprises: 
 removing, from the domain of the total cost element, any total cost values that are greater than or equal to the second total cost value; 
 applying at least the constraint programming data model, which has been modified to exclude any total cost values greater than or equal to the second total cost value from the domain of the total cost element, to the constraint programming solver; 
 determining that no solution is possible for the constraint programming model, which has been modified to exclude any total cost values greater than or equal to the second total cost value from the domain of the total cost element; 
 
 determining that, out of the set of solutions, the particular solution is associated with the total cost element that is assigned with the lowest total cost value comprises:
 responsive to (a) determining that no solution is possible for the constraint programming model and (b) determining that a last-determined solution, out of the set of solutions, is the second solution:
 identifying the second solution as the particular solution associated with the total cost element that is assigned with the lowest total cost value; 
 
 
 the particular proposed maintenance schedule indicates that the first machine maintenance task is scheduled for the first time window. 
 
     
     
       24. A system, comprising:
 one or more devices, each including one or more hardware processors; 
 one or more non-transitory computer-readable media; and 
 program instructions stored on the one or more non-transitory computer-readable media which, when executed by the one or more processors, cause the system to perform operations comprising: 
 identifying a set of machine maintenance tasks to be performed for a set of machines; 
 identifying a set of time windows for performing the set of machine maintenance tasks; 
 identifying a set of cost values for performing the set of machine maintenance tasks during the set of time windows; 
 generating a constraint programming data model, comprising:
 specifying a set of task elements representing the set of machine maintenance tasks;
 wherein a domain of a first task element, of the set of task elements, indicates possible time windows to be assigned to the first task element; and 
 wherein the possible time windows includes at least a subset of the set of time windows; 
 
 specifying a set of time elements representing at least the set of time windows;
 wherein a domain of a first time element, of the set of time elements, indicates possible task counts to be assigned to the first time element; 
 
 specifying a set of cost elements corresponding to the set of task elements;
 wherein a domain of a first cost element, of the set of cost elements, indicates possible cost values to be assigned to the first cost element; and 
 wherein the possible cost values includes at least a subset of the set of cost values; 
 
 specifying a total cost element;
 wherein a domain of the total cost element indicates possible total cost values to be assigned to the total cost element; 
 
 specifying a first constraint requiring at least that a first time window assigned to the first task element is one of the possible time windows, and a first task count assigned to the first time element is one of the possible task counts; 
 specifying a second constraint requiring at least that the first cost element be assigned with a first cost value that is (a) one of the possible cost values and (b) is associated with performing a first machine maintenance task, represented by the first task element, during the first time window; 
 specifying a third constraint requiring that the total cost element be assigned with a first total cost value that is (a) one of the possible total cost values and (b) is a sum of respective cost values assigned, or to be assigned, to the set of cost elements; 
 
 iteratively applying at least the constraint programming data model to a constraint programming solver to determine a set of one or more solutions satisfying at least the first constraint, the second constraint, and the third constraint, wherein the constraint programming solver is configured to computationally perform one or more of a backtracking algorithm or a forward-checking algorithm to determine the set of one or more solutions; 
 determining that, out of the set of solutions, a particular solution is associated with the total cost element that is assigned with a lowest total cost value; 
 returning a particular proposed machine maintenance schedule, for the set of machines, based on the particular solution, 
 wherein at least a subset of the set of machine maintenance tasks is executed according to the particular proposed machine maintenance schedule.