|
|
Math Programming
Why have mathematical programming based approaches not been used in the past for scheduling and planning applications?
Essentially, the huge number of equations and variables implied by industrial scale problems has been too large for the past combinations of solution algorithms, computer memory and processor speeds. The dramatic increase in computer memory and speed has finally reached the point where more sophisticated mathematical programming based approaches are tenable. More importantly, the advances in mathematical programming algorithm technology have been even more dramatic in the 1990’s. Whereas computers increased in capability by about a factor of ten from 1990 to 1996 , engineering efforts applied to scheduling and planning problems have increased the power of mathematical programming algorithms by several factors of ten. A similar phenomenon was exhibited with Artificial Intelligence (AI) methods. In the 1960 's, computers were insufficient to handle the demanding computational requirements of AI. This resulted in a diminished research effort during the 1970's, which resurged in the 1980's. Today, a computer has beaten a Grand Master at chess. The same cycle seen in AI methods is also occurring with mathematical programming.
Is there common evidence that Mathematical Programming Technology will become dominant in the scheduling and planning area?
Many companies that offer scheduling and planning tools also offer tools that are geared for supply chain applications. Notice that these tools are almost always based on linear programming approaches and sometimes use mixed integer linear programs with a small number of integer variables. Given the number of similarities between supply chain and more detailed scheduling and planning applications, one would expect that mathematical programming would also be successful on the more detailed scheduling problems. The predominant reason that mathematical programming is not applied is that translating the successful solution methods from the supply chain to the more detailed level requires a significant skill base and investment of time on the part of a vendor.
What is the mathematical programming approach for solving scheduling and planning problems?
The mathematical programming approach translates all of the decisions that must be made in a scheduling and planning problem into a set of variables whose values determine all the features of a solution. The physical constraints of the problem such as material balances, resource limitations, hard demand requirements and forced equipment outages are written in the form of equations using the variables. The goal guiding the solution of the scheduling and planning problem is supplied as an objective function which also uses the variables. Taken together the variables, constraining equations, and the objective function is called a mathematical program. Once defined from problem data, the mathematical program can be solved to determine feasibility and, in some cases, optimal solutions to the scheduling and planning problem.
What are the different kinds of mathematical programming problems?
Mathematical programming problems are differentiated based on the nature of the variables and equations. If all the variables can take on continuous values and the equations are linear (e.g. no powers of variables), then the mathematical program is known as a Linear Program (LP). If one or more variables can only take on integer values the problem is known as a Mixed Integer Linear Program (MILP). If the constraints involve powers of variables or transcendental functions of variables, then the problem is known as a Mixed Integer NonLinear Program (MINLP). A scheduling and planning problem results in an MILP or MINLP depending on how it is formulated. Linear programming technology is widely available and is considered relatively mature. MILP technology is being rapidly developed although considerable research and development is required to be able to solve most industrial size problems. MINLP technology is the subject of considerable research; however, in most cases, this area is currently intractable for all but the smallest problems. Some very special cases of MINLP's can be solved with good success.
|
COMPANY
