Properties and applications of signatures in time-dependent scheduling
- 講者Stanislaw Gawiejnowicz 博士 (Adam Mickiewicz University, POLAND)
邀請人：呂及人 - 時間2013-03-21 (Thu.) 11:00 ~ 12:00
- 地點資訊所新館106演講廳
摘要
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.