An algebraic geometry algorithm for scheduling in presence of setups and correlated demands.

Autor: Tayur, Sridhar, Thomas, Rekha, Natraj, N.
Zdroj: Mathematical Programming; Jul1995, Vol. 69 Issue 1-3, p369-401, 33p
Abstrakt: We study here a problem of scheduling n job types on m parallel machines, when setups are required and the demands for the products are correlated random variables. We model this problem as a chance constrained integer program. Methods of solution currently available-in integer programming and stochastic programming-are not sufficient to solve this model exactly. We develop and introduce here a new approach, based on a geometric interpretation of some recent results in Gröbner basis theory, to provide a solution method applicable to a general class of chance constrained integer programming problems. Out algorithm is conceptually simple and easy to implement. Starting from a (possibly) infeasible solution, we move from one lattice point to another in a monotone manner regularly querying a membership oracle for feasibility until the optimal solution is found. We illustrate this methodology by solving a problem based on a real system. [ABSTRACT FROM AUTHOR]
Databáze: Complementary Index
Externí odkaz: