RUTCOR Colloquia - March 9, 2006
Speaker: Nadia Brauner
Affiliation: Laboratoire Leibniz-IMAG, Grenoble, France
Title: Just-in-time scheduling and number theory.
Time: 1:30 - 2:30 PM
Location: RUTCOR Building - Room 139, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The objective in just-in-time scheduling is to balance the production of
the parts according to their types in order to be as close as possible
to an ideal production. The input is the number of parts of each type.
Hence a complete description of a solution is not polynomial and it is
not obvious whether the problem is in NP (high-multiplicity problems).
We shall give a proof that the problem of minimizing the maximum
deviation between the effective production and the ideal is in co-NP
(collaboration with Yves Crama, Professor in Liège, Belgium).
Then, we shall consider the small deviation conjecture which claims
that the unique standard instances with maximum deviation smaller than
0.5 are the powers of 2. We will prove this conjecture using balanced
word. On our way, we will also prove the symmetric case of Fraenkel
conjecture.
(collaboration with Vincent Jost, PhD student in Grenoble, France)
Back to Seminars Page.
Back to RUTCOR homepage.
| 
