Signatures and their applications in time-dependent scheduling

Lunedì, 8 Luglio, 2013 - 16:00

Il giorno 8/7/2013, alle 16, nel Laboratorio di Metodi Decisionali, il prof. Stanislaw Gawiejnowicz (Adam Mickiewicz University, Poznan) terrà un seminario dal titolo:

Signatures and their applications in time-dependent scheduling

Abstract. In the talk, we consider properties of some functions called signatures, and we show how to apply them to the construction of greedy algorithms for certain scheduling problems with time-dependent job processing times. First, we define two types of basic signatures and present some of their properties. Based on these properties, we construct a greedy algorithm for a time-dependent scheduling problem formulated in matrix form. Next, we introduce generalized signatures, a new greedy algorithm and show how to apply them to solving a few subcases of the studied problem. Finally, supported by analytical and experimental results, we formulate a few conjectures regarding the optimality of both the greedy algorithms. We complete the talk by some remarks on possible future research.