Patent ID: 7702410
Filing Date: 2010-04-20
Classification: G06Q

Abstract:
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, 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.