START Project Y43-MAT Combinatorial Approximation Algorithms TU Graz, Austria

Günter Rote Gerhard J. Woeginger

Minimizing the Number of Tardy Jobs on a Single Machine with Batch Setup Times

Report Woe-23 February 1998

Minimizing the number of tardy jobs on a single machine with batch setup times ^{∗}

Günter Rote ^{†}  Gerhard J. Woeginger ^{‡}

Abstract

This paper investigates a single-machine sequencing problem where the jobs are divided into families, and where a setup time is incurred whenever there is a switch from a job in one family to a job in another family. This setup only depends on the family of the job next to come and hence is sequence independent. The jobs are due-dated, and the objective is to find a sequence of jobs that minimizes the number of tardy jobs.

The special case of this problem where in every family the jobs have at most two different due dates is known to be N P-complete [Bruno & Downey, 1978]. The main result of this paper is a polynomial time algorithm for the remaining open case where in every family all the jobs have the same due date. This case may be formulated as a dual resource allocation problem with a tree-structured constraint system, which can be solved to optimality in polynomial time.

Keywords. sequencing; scheduling; batch setup times; number of tardy jobs.

1 Introduction

This paper deals with the following scheduling problem. There are n jobs J_{1}, …, J_{n} that are to be processed without interruption on a single machine. All jobs are available for processing at time zero. The set of jobs is divided into F families; a setup time s_{f} is associated to each family f = 1, …, F. Whenever a job in family f is processed, this incurs the setup time s_{f} unless another job from the same family is processed immediately before this job. The machine can execute at most one job at a time, and it cannot perform any processing while undergoing a setup. Job J_{j} (j = 1, …, n) has a positive integer processing time p_{j}, and an integer due date d_{j}. In a schedule σ, we denote by C_{j}(σ) the completion time of job J_{j} (j = 1, …, n). If C_{j}(σ) > d_{j}, then job J_{j} is tardy and we set U_{j} = 1. If C_{j}(σ) ≤ d_{j}, then job J_{j} is processed on-time and we set U_{j} = 0. The objective is to find a processing order of the jobs that minimizes ∑_{j=1}^{n} U_{j}, i.e. the number of tardy jobs. In the standard scheduling notation (cf. Lawler, Lenstra, Rinnooy Kan & Shmoys [5] and Potts & van Wassenhove [8]), this problem is denoted by 1 | s_{f} | ∑ U_{j}. For related problems and for practical applications involving batch setup times, the interested reader is referred to Monma & Potts [6], Potts & van Wassenhove [8], and Webster & Baker [9].

∗This research has been supported by the START program Y43-MAT of the Austrian Ministry of Science, and by the Spezialforschungsbereich Optimierung und Kontrolle, Projektbereich Disckrete Optimierung.

†rote@opt.math.tu-graz.ac.at. Institut für Mathematik B, TU Graz, Steyrergasse 30, A-8010 Graz, Austria.

‡gwoegi@opt.math.tu-graz.ac.at. Institut für Mathematik B, TU Graz, Steyrergasse 30, A-8010 Graz, Austria.

A special case of 1 | s_{f} | ∑ U_{j} is the feasibility testing problem, i.e. the problem of deciding whether there is a feasible schedule in which all jobs of a given instance are on-time. Bruno & Downey [1] prove that the feasibility testing problem is N P-hard, even if there are only two distinct deadlines per family. An instance of 1 | s_{f} | ∑ U_{j} where in every family all jobs have the same due date, is said to have uniform family due dates. In this paper we will show that the problem with uniform family due dates is solvable in polynomial time. This special case is sufficiently general to contain the problem 1 | | ∑ U_{j} without batch setup times (in 1 | | ∑ U_{j}, every jobs forms its own family and all family setup times are zero). Hence, our result generalizes the well-known polynomial time algorithm of Moore [7].

Our solution approach to 1 | s_{f} | ∑ U_{j} is as follows: We formulate 1 | s_{f} | ∑ U_{j} with uniform family due dates as a dual resource allocation problem with tree-structured constraints (cf. Section 3). Since this dual resource allocation problem can be solved in polynomial time by dynamic programming (cf. Section 2), the scheduling problem itself can be solved in polynomial time.

2 A dual resource allocation problem

The resource allocation problem (cf. Ibaraki & Katoh [3]) is a well-known optimization problem with a (possibly) complex objective function under a single, extremely simple constraint. In the dual resource allocation problem (cf. Katoh, Ibaraki & Mine [4] or Section 10.1 in [3]), the roles are exchanged and the objective function is simple whereas the constraint system may be messy. In this section, we investigate the following dual resource allocation problem (DAP).

(DAP)

max ∑_{f=1}^{F} x_{f}

s.t. \{ \begin{matrix}∑_{f∈S} g_{f}(x_{f}) ≤ c_{S} & for all S ∈ S \\ 0 ≤ x_{f} ≤ n_{f} & f = 1, …, F \\ x_{f} integer & f = 1, …, F \end{matrix}

For 1 ≤ f ≤ F, the function g_{f}: [0, n_{f}] → IR is an arbitrary function which is specified as an ordered list of pairs (x, g_{f}(x)), x = 0, …, n_{f}. The values n_{f}, 1 ≤ f ≤ F, are positive integers. The set system S is a system of non-empty sets over {1, …, F }. For every S ∈ S, the value c_{S} is an arbitrary real number.

Moreover, denote n = ∑_{f=1}^{F} n_{f}. Observe that n ≥ F holds and that by the specification of the functions g_{f}, the numbers n_{f} and n are essentially encoded in unary.

Proposition 2.1 The dual allocation problem (DAP) is an N P-hard problem.

Proof. The statement may be proved e.g. via a reduction from INDEPENDENT SET IN GRAPHS (cf. Garey & Johnson [2]): Given a graph G = (V, E), find the maximum number of pairwise non-adjacent vertices. For every vertex v_{f} ∈ V, introduce a corresponding variable x_{f} in (DAP) with the interpretation “x_{f} = 1” if v_{f} belongs to the independent set and “x_{f} = 0” otherwise. Moreover, set n_{f} = 1, g_{f}(0) = 0 and g_{f}(1) = 1. For every edge e = (v_{f}, v_{h}) introduce the set {f, h} in S and set c_{{f,h}} = 1. Then the optimal objective value of (DAP) yields the size of the maximum independent set in G.

A set system S is called tree-structured if ∅ ∉ S and for all S′, S′′ ∈ S,

S′ ⊆ S′′  or  S′′ ⊆ S′  or  S′ ∩ S′′ = ∅.

With a tree-structured set system S, we associate a directed in-forest F(S) as follows: For every set S ∈ S the forest contains a corresponding vertex; in the following we will not distinguish between a set S and its corresponding vertex. There is a directed edge from a set S′ to another set S′′ in F(S) if and only if S′ ⊂ S′′ and there is no S′′′ in S with S′ ≠ S′′′ ≠ S′ and S′ ⊂ S′′′ ⊂ S′′. Clearly, every vertex in F(S) has out-degree at most one. Adding all singleton sets to S does not destroy the tree-structured property. But then, the forest F(S) has F leaves, and the remaining vertices have indegree at least 2. It follows that a tree-structured family S contains at most 2F − 1 sets.

Lemma 2.2 For any instance I = (n_{f}, g_{f}, S, c_{S}) of (DAP) with tree-structured S, one can construct in O(n + F^{2}) time another instance I′ = (n_{f}, g_{f}, S′, c′_{S}) of (DAP) such that the following conditions are fulfilled.

(C1) I and I′ are equivalent, i.e. they have the same set of optimal solutions and the same optimal objective value.

(C2) The set system S′ in I′ is tree-structured; |S′| = 2F − 1 holds; the in-forest F(S′) associated with S′ is a binary in-tree.

Proof. We construct I′ in two steps by adding more sets to S. We set the righthand sides c′_{S} of all the corresponding new inequalities to the global upper bound c^{∗} = ∑_{f=1}^{F} max{0, max_{0≤x≤n_{f}} g_{f}(x)}, which makes them redundant. Initialize S′ := S and for all S ∈ S set c′_{S} = c_{S}. If {f} ∉ S′ for some f ∈ {1, …, F } then add the new set {f} to S′. If {1, …, F } ∉ S′ then add the new set {1, …, F } to S′.

In the second step, repeat the following procedure as long as some vertex S in F(S′) has three or more in-going edges: Let S_{i_{1}} and S_{i_{2}} be two arbitrary children of S in F(S′); add the set S′ = S_{i_{1}} ∪ S_{i_{2}} to S′. By iterating this procedure, eventually every interior vertex in F(S′) will have in-degree two and condition (C2) will be fulfilled. This completes the construction of instance I′. It can be verified that I′ is equivalent to I and hence, conditions (C1) and (C2) are both fulfilled.

It remains to discuss the time complexity. The first step is easily done in O(n+F) time. In the beginning of the second step, compute the current forest F(S′) as follows. First construct a simple, undirected, loopless auxiliary graph with vertex set S′: For every f = 1, …, F and for every S′, S′′ ∈ S′ with f ∈ S′ and f ∈ S′′, put an edge between S′ and S′′ into the auxiliary graph. The auxiliary graph can be constructed in O(F^{2}) overall time. Then for S ∈ S′, S ≠ {1, …, F }, the unique out-going edge in F(S′) goes to the set S′ where (i) S′ is adjacent to S in the auxiliary graph, (ii) |S′| > |S|, and (iii) |S′| is smallest possible under these conditions. In this way, the forest F(S′) for S′ at the beginning of the second step can be computed in O(F^{2}) time from the auxiliary graph. Getting rid of the vertices with in-degree greater than two can be done by locally manipulating F(S′); it is routine to implement it in O(F^{2}) overall time.

Theorem 2.3 The special case of the dual allocation problem (DAP) where S is tree-structured is solvable in O(n^{2}) time.

Proof. First we apply Lemma 2.2 to get in O(n + F^{2}) time an equivalent instance where F(S) is a binary tree. Let S_{1}, …, S_{2F −1} be an enumeration of the sets in S, such that S_{i} ⊂ S_{j} implies i ≤ j. For S ∈ S, let n(S) = ∑_{f∈S} n_{f}.

The remaining argument will be done by dynamic programming. Define a two-dimensional array A[i, ℓ] where 1 ≤ i ≤ 2F − 1 and 0 ≤ ℓ ≤ n with the following meaning: The value A[i, ℓ] is the smallest g^{∗} for which there exist values x_{f}^{∗}, f ∈ S_{i}, such that

(A1) ∑_{f∈S} g_{f}(x_{f}^{∗}) ≤ c_{S} holds for all S ∈ S, S ⊆ S_{i}.

(A2) ∑_{f∈S_{i}} x_{f}^{∗} = ℓ.

(A3) ∑_{f∈S_{i}} g_{f}(x_{f}^{∗}) = g^{∗}.

If no values x_{f}^{∗} fulfilling (A1) and (A2) exist, then A[i, ℓ] = +∞. This happens for example when ℓ > n(S_{i}). Hence from now on, we will only deal with entries A[i, ℓ] for which ℓ ≤ n(S_{i}). We compute the entries A[i, ℓ] in increasing order of i. If |S_{i}| = 1, let S_{i} = {f} and set for 0 ≤ ℓ ≤ n_{f}

A[i, ℓ] = \{ \begin{matrix}g_{f}(ℓ) & if g_{f}(ℓ) ≤ c_{S_{i}} \\ +∞ & otherwise. \end{matrix}  (1)

If |S_{i}| > 1, let S_{i} = S_{a} ∪ S_{b} with a < b < i, where S_{a} and S_{b} are the two children of S_{i} in F(S). Then for ℓ ≤ n(S_{i}),

A[i, ℓ] = \{ \begin{matrix}min \{ A[a, k] + A[b, ℓ − k] : 0 ≤ k ≤ n(S_{a}), 0 ≤ ℓ − k ≤ n(S_{b}) \} \\ +∞  if this minimum is greater than c_{S_{i}}. \end{matrix}  (2)

It can be verified that with the above definitions, (A1)–(A3) are always fulfilled for g^{∗} = A[i, ℓ]. In the end, the optimal objective value of (DAP) equals the maximum ℓ for which A[2F − 1, ℓ] takes a finite value.

Let us analyze the time needed to compute all values A[i, ℓ]. Denote by T (i) the total time needed to handle all finite entries A[j, ℓ] with 0 ≤ ℓ ≤ n and S_{j} ⊆ S_{i}. Then for |S_{i}| = 1 with S_{i} = {f}, (1) implies that

T (i) = const_{1} · n_{f} = const_{1} · n(S_{i}).  (3)

If |S_{i}| > 1, let S_{a} and S_{b} be the two children of S_{i} in F(S). Note that a < b < i, that S_{i} = S_{a} ∪ S_{b}, and that n(S_{i}) = n(S_{a}) + n(S_{b}) holds. We claim that

T (i) = T (a) + T (b) + const_{2} · n(S_{a}) · n(S_{b}).  (4)

This can be seen as follows. The time T (i) consists of the total time for handling all entries A[j, ℓ] with 0 ≤ ℓ ≤ n and S_{j} ⊆ S_{a} or S_{j} ⊆ S_{b}, plus the total time for handling all entries A[i, ℓ] with 0 ≤ ℓ ≤ n. For every α, 0 ≤ α ≤ n(S_{a}), and for every β, 0 ≤ β ≤ n(S_{b}), in (2) there is exactly one step performed with k = α and ℓ − k = β. Hence, the total time for handling the entries A[i, ℓ] with 0 ≤ ℓ ≤ n(S_{i}) is proportional to n(S_{a}) · n(S_{b}). Hence, (4) indeed holds. By induction, one proves from (3) and (4) that

T (i) ≤ const · n(S_{i})^{2}.

Consequently, the total time T (2F −1) needed for computing all entries is O(n^{2}). Since F ≤ n, the time spent on applying Lemma 2.2 is also O(n^{2}). Summarizing, this yields the running time claimed in the statement of the theorem.

Finally, we remark that by storing appropriate auxiliary information in the dynamic program and by doing some backtracking, one can also explicitly compute the values x_{f} in an optimal solution; this increases the running time by only a constant factor. Since these are standard techniques, we do not elaborate on them.

3 Solution of the scheduling problem

In this section we discuss the scheduling problem 1 | s_{f} | ∑ U_{j} that has been defined in the introduction. The following observation follows via straightforward job interchange arguments.

Observation 3.1 For any instance of 1 | s_{f} | ∑ U_{j} with uniform family due dates, there is an optimal schedule of the following form.

(i) For every family, the on-time jobs of that family are processed consecutively; hence, the setup for each family is performed at most once.

(ii) In each family, the on-time jobs are the shortest jobs of the family.

For f = 1, …, F, denote by d_{f} the due date of the jobs in family f. Without loss of generality assume that d_{1} ≤ d_{2} ≤ ⋯ ≤ d_{F}. Let n_{f}, f = 1, …, F, denote the number of jobs in family f, and let p_{f,1} ≤ p_{f,2} ≤ ⋯ ≤ p_{f,n_{f}} denote their processing times. Moreover, define

g_{f}(x) = \{ \begin{matrix}0 & if x = 0 \\ s_{f} + ∑_{i=1}^{x} p_{f,i} & if 1 ≤ x ≤ n_{f}. \end{matrix}

For f = 1, …, F, introduce S_{f} = {1, …, f} and set c_{S_{f}} = d_{f}. Define S = {S_{1}, …, S_{F} }. Finally, denote by x_{f} the number of on-time jobs from family f, f = 1, …, F.

With this choice of parameters, the dual allocation problem (DAP) is equivalent to 1 | s_{f} | ∑ U_{j} with uniform family due dates. Moreover, S is tree-structured and hence Theorem 2.3 implies the main result of this paper:

Theorem 3.2 The special case of 1 | s_{f} | ∑ U_{j} with uniform family due dates is solvable in O(n^{2}) time.

Acknowledgement. The authors thank Bettina Klinz for several valuable discussions and for providing pointers to the literature on allocation problems.

References

[1] J. Bruno and P. Downey, Complexity of task sequencing with deadlines, set-up times, and changeover costs, SIAM Journal on Computing 7, 1978, 393–404.

[2] M.R. Garey and D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.

[3] T. Ibaraki and N. Katoh, Resource Allocation Problems: Algorithmic Approaches, MIT Press, Boston, 1988.

[4] N. Katoh, T. Ibaraki, and H. Mine, Algorithms for a variant of the resource allocation problem, Journal of the Operations Research Society of Japan 22, 1979, 287–299.

[5] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys, Sequencing and scheduling: Algorithms and complexity, in: S.C. Graves, A.H.G. Rinnooy Kan, and P.H. Zipkin (eds.) Logistics of Production and Inventory, Handbooks in Operations Research and Management Science 4, North-Holland, Amsterdam, 1993, 445–522.

[6] C.L. Monma and C.N. Potts, On the complexity of scheduling with batch set-up times, Operations Research 37, 1989, 798–804.

[7] J. Moore, An n job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science 15, 1968, 102–109.

[8] C.N. Potts and L.N. van Wassenhove, Integrating scheduling with batching and lotsizing: a review of algorithms and complexity, Journal of the Operational Research Society 43, 1992, 395–406.

[9] S. Webster and K.R. Baker, Scheduling groups of jobs on a single machine, Operations Research 43, 1995, 692–703.

Recent reports from the START project Y43-MAT

PostScript-files of the listed reports may be obtained by anonymous ftp from ftp.tu-graz.ac.at,

   directory /pub/papers/math or by sending e-mail to gwoegi@opt.math.tu-graz.ac.at.

Woe-03 L. Babel and G.J. Woeginger, Pseudo-Hamiltonian graphs (May 97) Woe-04 A. Fiat and G.J. Woeginger, On-line scheduling on a single machine: Minimizing

the total completion time (Jun 97) Woe-05 V.G. Deĭneko and G.J. Woeginger, A study of exponential neighbourhoods for the

traveling salesman problem and for the quadratic assignment problem (Jul 97) Woe-06 G.J. Woeginger, There is no asymptotic PTAS for two-dimensional vector pack-

ing (Aug 97) Woe-07 G.J. Woeginger, A comment on a minmax location problem (Aug 97) Woe-08 S.S. Seiden, Randomized preemptive online interval scheduling (Sep 97) Woe-09 V.G. Deĭneko and G.J. Woeginger, The maximum travelling salesman problem on

Demidenko matrices (Sep 97) Woe-10 G.J. Woeginger, A note on the depth function of combinatorial optimization prob-

lems (Sep 97) Woe-11 S.S. Seiden, Randomized online multi-threaded paging (Oct 97) Woe-12 P. Schuurman and G.J. Woeginger, A polynomial time approximation scheme for

preemptive scheduling with setup times (Oct 97) Woe-13 P. Schuurman and G.J. Woeginger, Approximation algorithms for the multiproces-

sor open shop problem (Oct 97) Woe-14 G. Rote and G.J. Woeginger, Time complexity and linear-time approximation of

the ancient two machine flow shop (Nov 97) Woe-15 H. Hoogeveen, P. Schuurman and G.J. Woeginger, Non-approximability results

for scheduling problems with minsum criteria (Nov 97) Woe-16 S.Seiden, More multiprocessing scheduling with rejection (Dec 97) Woe-17 G.J. Woeginger, A polynomial time approximation scheme for single machine sequenc-

ing with delivery times and sequence independent batch setup times (Dec 97) Woe-18 N. Alon, Y. Azar, G.J. Woeginger and T. Yadid, Approximation schemes for

scheduling on parallel machines (Dec 97) Woe-19 F. Rendl, Semidefinite programming and combinatorial optimization (Dec 97) Woe-20 A. Barvinok, D.S. Johnson, G.J. Woeginger and R. Woodroofe, Finding max-

imum length tours under polyhedral norms (Jan 98) Woe-21 G.J. Woeginger, An approximation scheme for minimizing agreeably weighted variance

on a single machine (Jan 98) Woe-22 G.J. Woeginger and G. Zhang, Optimal on-line algorithms for variable-sized bin

covering (Feb 98) Woe-23 G. Rote and G.J. Woeginger, Minimizing the number of tardy jobs on a single

machine with batch setup times (Feb 98)