Scheduling problems are notoriously difficult and ILP models have not yet shown adequate strength for them to be competitive with other approaches. This chapter presents a time-indexed model for the Job-Shop problem that can be solved either by column generation or by a compact equivalent formulation. We present also an interesting approach for a one-machine problem for which a Dantzig-Wolfe decomposition was proposed. This example allows us to show how the Dantzig-Wolfe decomposition goes in the opposite direction with respect to the compactification techniques that we have extensively discussed in this book.

Scheduling

Lancia G.;Serafini P.
2018-01-01

Abstract

Scheduling problems are notoriously difficult and ILP models have not yet shown adequate strength for them to be competitive with other approaches. This chapter presents a time-indexed model for the Job-Shop problem that can be solved either by column generation or by a compact equivalent formulation. We present also an interesting approach for a one-machine problem for which a Dantzig-Wolfe decomposition was proposed. This example allows us to show how the Dantzig-Wolfe decomposition goes in the opposite direction with respect to the compactification techniques that we have extensively discussed in this book.
2018
978-3-319-63975-8
978-3-319-63976-5
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/1214324
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact