Patent Document ID: 20090106340
Application ID: 11875937
Patent Status: 0

Claim One:
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 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.