Properties and applications of signatures in time-dependent scheduling
- LecturerDr. Stanislaw Gawiejnowicz (Adam Mickiewicz University, POLAND)
Host: Chi-Jen Lu - Time2013-03-21 (Thu.) 11:00 ~ 12:00
- LocationAuditorium 106 at new IIS Building
Abstract
We present properties and applications of functions, called signatures, to solving certain scheduling problems with variable time-dependent job processing times.
First, we define two types of basic signatures and present some their properties.
Based on these properties, we construct a greedy algorithm for a time-dependent scheduling problem formulated in a matrix form. Next, we introduce generalized signatures, a new greedy algorithm and show how they can be applied to the studied problem. We also formulate a few conjectures regarding the optimality of the greedy algorithms, giving some analytical and experimental results supporting these conjectures.
We conclude with some remarks on possible future research.