Back to the program.
Scheduling Problems: Model, Algorithms and Applications
Marco Pranzo
UniversitÓ degli Studi "Roma Tre"
Rome, Italy


In this presentation we briefly introduce the Alternative Graph. The Alternative Graph is a generalization of the Disjunctive Graph, and can be used to represent constrained scheduling problems. In the Ideal Job Shop Problem there is the assumption that all the machines have an infinite capacity buffer. For some problems, due to technological constraints, this assumption is not realistic. The Blocking Job Shop Problem (zero buffer between machines) and and the No-Wait Scheduling Problem (jobs cannot idle) are introduced. Both this problems arise from real world application and can be easily modeled using the Alternative Graph formulation. We describe metaheuristic algorithms that work on the Alternative Graph and make no assumption on the type of the scheduling problem. Therefore these algorithms can be applied to solve all the problems that can be modeled by means of the Alternative Graph. Finally two real world application are discussed. The scheduling of a continuous casting line of a steelmaking plant, and the scheduling of trains in a regional railway network.