Sorting Common Operations to Minimize Tardy Jobs

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.