We study an operation scheduling problem where a finite set of jobs with due dates must be completed by one machine: each job is completed as soon as a specific subset of unit operations is done. Distinct jobs may share operations, and when an operation is done, it is done for all the jobs that share it. The goal is to schedule operations so that the (weighted) number of tardy jobs is minimized. We reformulate the problem as maximum stable set problem on a special graph and study its structure. Valid inequalities and optimality cuts are derived, separated and tested in a computational experience that identifies some features of hard instances and the potential contribution of the addition, at root, of various cut classes.

Sorting Common Operations to Minimize the Number of Tardy Jobs

ARBIB, CLAUDIO;
2014

Abstract

We study an operation scheduling problem where a finite set of jobs with due dates must be completed by one machine: each job is completed as soon as a specific subset of unit operations is done. Distinct jobs may share operations, and when an operation is done, it is done for all the jobs that share it. The goal is to schedule operations so that the (weighted) number of tardy jobs is minimized. We reformulate the problem as maximum stable set problem on a special graph and study its structure. Valid inequalities and optimality cuts are derived, separated and tested in a computational experience that identifies some features of hard instances and the potential contribution of the addition, at root, of various cut classes.
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: http://hdl.handle.net/11697/16071
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact