### Abstract

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.