We consider the following problem (P): given a discrete finite set N with n elements, a finite collection S = {S1, . . . , Sm} of (possibly duplicated) subsets of N and a positive integer dj for each Sj ε S, assign every i ε N to a distinct positive integer k(i) so that the number of sets in S with maxiεSj{k(i)} > dj is minimized. A motivation for (P) can be found in an operation scheduling problem, where a set J of m jobs with specific due dates d1, . . . , dm must be completed by a machine: job j is completed as soon as a subset Sj of operations is done. Jobs share common operations: this means that once operation i is completed, it is completed for all the jobs j that require i. A practical application of this problem is pattern sequencing in stock cutting [2]. The case with |Sj| = 2 (j in J), mentioned in [1], is a graph ordering problem and was shown to be NP-hard (reduction from CLIQUE). In this paper we formulate the general case as a STABLE SET on a special graph. We investigate the structure of the graph, and discuss facet-defining and valid inequalities (the former include some Chv́atal-Gomory lifted odd holes). A preliminary computational experience provides difficult instances to be tested in future research.

Sorting Common Operations to Minimize Tardy Jobs

ARBIB, CLAUDIO;SERVILIO, MARA
2011-01-01

Abstract

We consider the following problem (P): given a discrete finite set N with n elements, a finite collection S = {S1, . . . , Sm} of (possibly duplicated) subsets of N and a positive integer dj for each Sj ε S, assign every i ε N to a distinct positive integer k(i) so that the number of sets in S with maxiεSj{k(i)} > dj is minimized. A motivation for (P) can be found in an operation scheduling problem, where a set J of m jobs with specific due dates d1, . . . , dm must be completed by a machine: job j is completed as soon as a subset Sj of operations is done. Jobs share common operations: this means that once operation i is completed, it is completed for all the jobs j that require i. A practical application of this problem is pattern sequencing in stock cutting [2]. The case with |Sj| = 2 (j in J), mentioned in [1], is a graph ordering problem and was shown to be NP-hard (reduction from CLIQUE). In this paper we formulate the general case as a STABLE SET on a special graph. We investigate the structure of the graph, and discuss facet-defining and valid inequalities (the former include some Chv́atal-Gomory lifted odd holes). A preliminary computational experience provides difficult instances to be tested in future research.
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/11697/89196
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact