Generation of schedule by which physical items to be manufactured are assigned into production slots via reducing non-zero factors within coefficient matrix clusters
View Patent ↗A schedule is generated by which physical items to be manufactured are assigned into production slots. The physical items have constraints governing manufacture of the physical items. The method generates coefficient matrix clusters from a mathematical programming problem based on an actual scheduling problem. Each coefficient matrix cluster defines a variable cluster-constraint cluster pair. A variable cluster of each coefficient matrix cluster defines production slot-physical item pairs. A constraint cluster of each coefficient matrix cluster defines a group of constraints. Each coefficient matrix cluster includes coefficient-binary variable pairs, each pair having a binary variable multiplied by a coefficient. For each coefficient matrix cluster, the method reduces non-zero factors within the cluster. Each non-zero factor within the coefficient matrix cluster is defined as a coefficient-binary variable pair such that the binary variable of the pair multiplied by the coefficient of the pair is non-zero. The schedule is then generated.
1. A method for generating a schedule by which a plurality of physical items to be manufactured are assigned into a plurality of production slots, the physical items having a plurality of constraints governing manufacture of the physical items, the method comprising:
generating a plurality of coefficient matrix clusters from a mathematical programming problem that is based on an actual scheduling problem to be solved, each coefficient matrix cluster defining a variable cluster-constraint cluster pair, a variable cluster of each coefficient matrix cluster defining a number of production slot-physical item pairs, a constraint cluster of each coefficient matrix cluster defining a number of constraints that are of a same type,
wherein each coefficient matrix cluster comprises a plurality of coefficient-binary variable pairs, each coefficient-binary variable pair having a binary variable multiplied by a coefficient, the binary variable having a value of one where a corresponding physical item is assigned to a corresponding production slot and a value of zero where the corresponding physical item is not assigned to the corresponding production slot;
for each coefficient matrix cluster, reducing a number of non-zero factors within the coefficient matrix cluster, each non-zero factor within the coefficient matrix cluster defined as a coefficient-binary variable pair such that the binary variable of the coefficient-binary variable pair multiplied by the coefficient of the coefficient-binary variable pair is non-zero; and,
generating the schedule, using a computer, by which the physical items to be manufactured are assigned into the production slots by solving the IP-related problem in relation to the coefficient matrix clusters in which the number of non-zero factors have been reduced,
wherein the physical items are to be manufactured in accordance with the schedule within which the physical items have been assigned into the production slots.
2. The method of claim 1 , further comprising:
generating a plurality of variable clusters, each variable cluster defining a number of physical item-production slot pairs; and,
generating a plurality of constraint clusters, each constraint cluster defining a number of constraints that are of a same type.
3. The method of claim 1 , further comprising manufacturing the physical items in accordance with the schedule within which the physical items have been assigned into the production slots.
4. The method of claim 1 , wherein, for each coefficient matrix cluster, reducing the number of non-zero factors within the coefficient matrix cluster comprises replacing one or more patterns within the coefficient matrix cluster with substitute variables, each pattern defined as a plurality of coefficient-binary variable pairs.
5. The method of claim 1 , wherein, for each coefficient matrix cluster, reducing the number of non-zero factors within the coefficient matrix cluster comprises:
excluding each constraint represented within the coefficient matrix cluster for which a number of non-zero factors is less than or equal to half of a number of binary variables represented within the coefficient matrix cluster.
6. The method of claim 5 , wherein, for each coefficient matrix cluster, reducing the number of non-zero factors within the coefficient matrix cluster comprises:
for each binary variable represented within the coefficient matrix cluster,
counting a number of occurrences a coefficient by which the binary variable is most frequently multiplied within the coefficient matrix cluster; and,
where the number of occurrences is less than or equal to half of a number of constraints within the coefficient matrix cluster, excluding the binary variable from the coefficient matrix cluster.
7. The method of claim 6 , wherein, for each coefficient matrix cluster, reducing the number of non-zero factors within the coefficient matrix cluster comprises:
defining a substitute variable as a linear combination of a number of the coefficient-binary variable pairs that appear most frequently within the coefficient matrix cluster;
adding the substitute variable as a new constraint within the coefficient matrix cluster; and,
removing from the coefficient matrix cluster each coefficient-binary variable pair defined by the substitute variable.
8. The method of claim 1 , wherein the mathematical programming problem solved in relation to the coefficient matrix clusters in which the number of non-zero factors have been reduced comprises one of: an integer programming (IP) problem, a linear programming (LP) problem, and a mixed integer programming (MIP) problem.
9. The method of claim 1 , wherein the physical items to be manufactured are steel coils.
10. The method of claim 1 , wherein the physical items to be manufactured are semiconductor devices.
11. A computer-readable medium having one or more computer programs stored thereon to perform a method for generating a schedule by which a plurality of physical items to be manufactured are assigned into a plurality of production slots, the physical items having a plurality of constraints governing manufacture of the physical items, the method comprising:
generating a plurality of coefficient matrix clusters, each coefficient matrix cluster defining a variable cluster-constraint cluster pair, a variable cluster of each coefficient matrix cluster defining a number of production slot-physical item pairs, a constraint cluster of each coefficient matrix cluster defining a number of constraints that are of a same type,
wherein each coefficient matrix cluster comprises a plurality of coefficient-binary variable pairs, each coefficient-binary variable pair having a binary variable multiplied by a coefficient, the binary variable having a value of one where a corresponding physical item is assigned to a corresponding production slot and a value of zero where the corresponding physical item is not assigned to the corresponding production slot;
for each coefficient matrix cluster, reducing a number of non-zero factors within the coefficient matrix cluster, each non-zero factor within the coefficient matrix cluster defined as a coefficient-binary variable pair such that the binary variable of the coefficient-binary variable pair multiplied by the coefficient of the coefficient-binary variable pair is non-zero;
generating the schedule by which the physical items to be manufactured are assigned into the production slots by solving a mathematical programming problem in relation to the coefficient matrix clusters in which the number of non-zero factors have been reduced,
wherein the mathematical programming problem comprises one of: an integer programming (IP) problem, a linear programming (LP) problem, and a mixed integer programming (MIP) problem; and,
outputting the schedule,
wherein the physical items are to be manufactured in accordance with the schedule within which the physical items have been assigned into the production slots.
12. The computer-readable medium of claim 11 , wherein outputting the schedule comprises programming a manufacturing system in accordance with the schedule within which the physical items have been assigned into the production slots, the manufacturing system manufacturing the physical items.
13. The computer-readable medium of claim 11 , wherein outputting the schedule comprises printing or displaying the schedule for a user so that the user is able to control a manufacturing system in accordance with the schedule within which the physical items have been assigned into the production slots, the manufacturing system manufacturing the physical items.
14. The computer-readable medium of claim 11 , wherein, for each coefficient matrix cluster, reducing the number of non-zero factors within the coefficient matrix cluster comprises:
excluding each constraint represented within the coefficient matrix cluster for which a number of non-zero factors is less than or equal to half of a number of binary variables represented within the coefficient matrix cluster.
15. The computer-readable medium of claim 14 , wherein, for each coefficient matrix cluster, reducing the number of non-zero factors within the coefficient matrix cluster comprises:
for each binary variable represented within the coefficient matrix cluster,
counting a number of occurrences a coefficient by which the binary variable is most frequently multiplied within the coefficient matrix cluster; and,
where the number of occurrences is less than or equal to half of a number of constraints within the coefficient matrix cluster, excluding the binary variable from the coefficient matrix cluster.
16. The computer-readable medium of claim 15 , wherein, for each coefficient matrix cluster, reducing the number of non-zero factors within the coefficient matrix cluster comprises:
defining a substitute variable as a linear combination of a number of the coefficient-binary variable pairs that appear most frequently within the coefficient matrix cluster;
adding the substitute variable as a new constraint within the coefficient matrix cluster; and,
removing from the coefficient matrix cluster each coefficient-binary variable pair defined by the substitute variable.
17. A manufacturing system comprising:
one or more manufacturing components to manufacture a plurality of physical items within a plurality of production slots in accordance with a schedule within which the physical items have been assigned into the production slots; and,
a schedule-generating mechanism to generate the schedule by:
generating a plurality of coefficient matrix clusters, each coefficient matrix cluster defining a variable cluster-constraint cluster pair, a variable cluster of each coefficient matrix cluster defining a number of production slot-physical item pairs, a constraint cluster of each coefficient matrix cluster defining a number of constraint-production slot pairs,
wherein each coefficient matrix cluster comprises a plurality of coefficient-binary variable pairs, each coefficient-binary variable pair having a binary variable multiplied by a coefficient, the binary variable having a value of one where a corresponding physical item is assigned to a corresponding production slot and a value of zero where the corresponding physical item is not assigned to the corresponding production slot;
for each coefficient matrix cluster, reducing a number of non-zero factors within the coefficient matrix cluster, each non-zero factor within the coefficient matrix cluster defined as a coefficient-binary variable pair such that the binary variable of the coefficient-binary variable pair multiplied by the coefficient of the coefficient-binary variable pair is non-zero; and,
generating the schedule by which the physical items to be manufactured are assigned into the production slots by solving a mathematical programming problem in relation to the coefficient matrix clusters in which the number of non-zero factors have been reduced,
wherein the mathematical programming problem comprises one of: an integer programming (IP) problem, a linear programming (LP) problem, and a mixed integer programming (MIP) problem.
18. The manufacturing system of claim 17 , wherein, for each coefficient matrix cluster, reducing the number of non-zero factors within the coefficient matrix cluster comprises:
excluding each constraint represented within the coefficient matrix cluster for which a number of non-zero factors is less than or equal to half of a number of binary variables represented within the coefficient matrix cluster.
19. The manufacturing system of claim 18 , wherein, for each coefficient matrix cluster, reducing the number of non-zero factors within the coefficient matrix cluster comprises:
for each binary variable represented within the coefficient matrix cluster,
counting a number of occurrences a coefficient by which the binary variable is most frequently multiplied within the coefficient matrix cluster; and,
where the number of occurrences is less than or equal to half of a number of constraints within the coefficient matrix cluster, excluding the binary variable from the coefficient matrix cluster.
20. The manufacturing system of claim 19 , wherein, for each coefficient matrix cluster, reducing the number of non-zero factors within the coefficient matrix cluster comprises:
defining a substitute variable as a linear combination of a number of the coefficient-binary variable pairs that appear most frequently within the coefficient matrix cluster;
adding the substitute variable as a new constraint within the coefficient matrix cluster; and,
removing from the coefficient matrix cluster each coefficient-binary variable pair defined by the substitute variable.