Annals of Operations Research 92(1999)87–105

87

Scheduling multi-operation jobs on a single machine A.E. Gerodimos a, C.A. Glass a, C.N. Pottsa and T. Tautenhahn b a

Faculty of Mathematical Studies, University of Southampton, Southampton SO17 1BJ, UK

b

Fakultät für Mathematik, Otto-von-Guericke-Universität Magdeburg, Postfach 4120, D-39016 Magdeburg, Germany

We consider the problem of scheduling n multi-operation jobs on a single machine. Each job comprises up to F operations that belong to different families. Changeovers of production from one family to another have associated set-up times. A job completes when all of its operations have been processed. This type of problem arises in the manufacture of food products. It combines the batching aspect of the well-known family scheduling models with an assembly element (where the job’s operations are assembled to make the final product). Our analysis covers three classic optimality criteria: the maximum lateness, the weighted number of late jobs, and the sum of job completion times. We show that the problem of minimizing the maximum lateness is equivalent to its counterpart without assembly. This enables us to derive extensions of known complexity results and to indicate appropriate algorithms. The number of late jobs problem is shown to be binary NP-hard when there are two families, and unary NP-hard when there are an arbitrary number of families, even when all set-up times are identical. For a fixed number of families, we give a dynamic programming algorithm to minimize the weighted number of late jobs, which requires pseudo-polynomial running time. A similar algorithm solves the sum of completion times problem in polynomial time, under the additional assumption that the processing times of operations between families are agreeable. Keywords: scheduling, single machine, multi-operation jobs, complexity, dynamic programming AMS subject classification: 90B35

1.

Introduction

1.1. Motivation for the study The problem under consideration arises in a food manufacturing environment, and involves two production stages. In the first stage, several base ingredients are produced in batches and fed into intermediate buffer storage (bins). In order to avoid contamination of one base ingredient by another, a certain amount of the ingredient is © J.C. Baltzer AG, Science Publishers

88

A.E. Gerodimos et al. y Scheduling multi-operation jobs

reprocessed at the start of each new batch. The effect is the same as that of a set-up time for each batch at the first stage. In the second stage, the base ingredients are blended according to given recipes to form the final products. A general model that captures the above characteristics would be some variant of the classic two-stage flow-shop. However, in the industrial system under consideration, the second stage is considerably faster and must be scheduled to respond quickly to demand. Such a schedule for the second stage effectively defines due dates for base ingredients at the first stage. Further, the intermediate buffer storage is sufficiently large to cope with any “reasonable” schedule for the first stage. Thus, the responsiveness to demand of the whole process is determined by the flexibility of the first stage. We can therefore restrict our attention to the first stage, the problem of scheduling a single machine that manufactures various base ingredients for subsequent assembly into end products. 1.2. Related models Although the model in question is introduced as part of a study of a specific manufacturing facility, its applications extend to a variety of other environments. As more and more companies adopt the ideas of the just-in-time manufacturing philosophy [11], scheduling models with an assembly element are likely to become increasingly relevant. Consider the production process at an oil refinery [20]. Crude oil goes through a series of machines to be converted into intermediate components. These components are then blended together according to a given specification to form a range of final products such as petrol, heating oil and diesel. At the tactical level, it may be of interest to schedule the initial processing efficiently so as to support the blending stage. An essentially equivalent model encountered in a seemingly different environment is described by Julien and Magazine [13]. In the so-called customer order model, jobs represent orders for a variety of products that are manufactured on a single facility. As with our assembly model, incomplete orders cannot be delivered to customers. A special case of our model in which there are only two families has been studied (see [1,3,4,6,7,21]) under different assumptions regarding the operation processing times and the times when jobs are available for dispatch to customers. 1.3. Formal definitions There are n jobs numbered 1,…, n (the orders for final products), each of which has operations from up to F different families (base ingredient types), which are to be processed on a single machine. We assume that each job has at most one operation in each family (if some job has several operations in the same family, then these can be combined into a single operation without affecting the quality of the solution for the models that we consider). The operation of job j ( j = 1,…, n) in family f ( f = 1,…, F)

A.E. Gerodimos et al. y Scheduling multi-operation jobs

89

is denoted by ( f, j), and its associated processing time is pfj ≥ 0. By including zero processing times, we allow jobs to have missing operations, i.e. not every product needs to contain all of the base ingredients. Any operation with zero processing time is called a trivial operation. As a job j cannot complete before all of its operations have been processed, its completion time Cj is that of its last operation. Formally, Cj = max f { Cfj }, where Cfj is the completion time of operation ( f, j). Whenever an operation ( f, j) is processed directly after some operation (g, k) of a different family g, a delay is incurred to set up the machine. Unless otherwise stated, this set-up time is sequence independent, which means that it depends only on family f ; hence, it is denoted by sf . In cases where set-up times are sequence dependent, we assume that they satisfy the triangle inequality, i.e. the set-up time to switch from family f to family h is no more than the set-up time from family f to family g plus the set-up time from family g to family h. Operations of the same family can be combined into a batch and executed without set-ups in between, but they complete individually, irrespective of the completion time of the batch. This assumption is commonly termed item availability [19]. For some variants of the model, each job j has a due date, which we denote by dj . In this case, the lateness of job j is defined as Lj = Cj – dj . We assume that all set-up times, processing times, and due dates are integers. Our model can be examined under the group technology (see [18]) assumption, which specifies that all operations in any family are to be scheduled contiguously. This assumption may be imposed as a result of the requirement to maximize the throughput of the machine, or it may reflect the need to manufacture product of consistent quality. We sometimes consider the assumption of SPT-agreeability, which states that there exists an SPT (shortest processing time) indexing of the jobs such that p1 ≤ … ≤ pn, and pf1 ≤ … ≤ pfn for f = 1,…, F, where pj = ∑f pfj for j = 1,…, n. We note that SPT-agreeability is not an assumption inspired by the real-life problem considered; it is simply imposed to make the sum of completion times problem more tractable. To denote the problems under consideration, we follow the well-known classification scheme α|β|γ introduced by Graham et al. [10]. In our case, α = 1 denotes a single-machine scheduling problem. We include sf in the second field to denote sequence-independent family set-up times. Moreover, we use the term assembly in the second field to describe the fact that a job completes when it becomes available for assembly, which is when all of its operations have been processed. Similarly, the term SPT-agree implies that the SPT-agreeability assumption is imposed. Use of GT in the second field indicates that we study the problem under the group technology assumption. Further, unless we state that F = k for some integer k, the number of families F is considered to be part of the input. Possible restrictions on set-up times and processing times are also included in the second field. In the third field, γ ∈ {Lmax , ∑(wj )Uj , ∑Cj } according to whether the optimality criterion is the maximum lateness, the (weighted) number of late jobs, or the sum of completion times, respectively.

90

2.

A.E. Gerodimos et al. y Scheduling multi-operation jobs

Minimizing the maximum lateness

In this section, the maximum lateness problem is analyzed. For the simplified problem 1kLmax in which set-up times are zero and each job has a single operation, an optimal solution is obtained by sequencing the jobs in earliest due date (EDD) order. First, we establish the equivalence between 1|sf , assembly|L max and the standard family scheduling problem 1|sf |Lmax problem (see [16]) in which each job has a single operation. This enables us to draw conclusions regarding the complexity status of our problem and to indicate algorithms that exist for solving it. Recall that in both models, and throughout this paper, we assume item availability within a batch. We use the natural terms final and non-final operation in the following sense. An operation is called final if it is the last operation of a particular job in a schedule; otherwise, it is termed non-final. Recall that the lateness of job j is defined as Lj = Cj – dj, and the maximum (job) lateness is Lmax = max j{Cj – dj}. By analogy, we define the lateness of operation ( f, j) as Lfj = Cfj – dj , and the maximum operation lateness as Lop max = maxf, j {Lfj }. Lemma 1. An instance of problem 1|sf , assembly|Lmax is equivalent to an instance of problem 1|sf |Lmax where non-trivial in the former problem correspond to jobs in the latter problem. Further, the equivalence holds in the presence of any of the following constraints: the GT assumption, a fixed number of families, and job release dates. Proof. An instance of problem 1|sf |Lmax can be regarded as an instance of problem 1|sf , assembly|Lmax in which each job has a single operation. Conversely, let P be an instance of 1|sf , assembly|Lmax. We define an instance P′ of 1|sf |Lmax by simply creating, for each non-trivial operation ( f, j) in P, a single job that has due date dj and belongs to family f. If pfj = 0, then there is no job in P′ that corresponds to ( f, j). From the definitions, we observe that minimizing Lop max for problem P is equivalent to minimizing Lmax for problem P′. Thus, it remains to show that minimizing Lop max and L max for problem P are equivalent. Consider any schedule, and let (g, k) be an operation for which Lop max = L g, k . Observe that (g, k) must be the final operation of job k. Thus, Lmax ≥ Lop max . Since, by definition, Lmax ≤ Lop max , we have established the desired result. As the structure of the problem remains essentially unchanged in all other respects, the equivalence holds for each of the variants of the two problems mentioned in the lemma. u From lemma 1, known complexity results for problem 1|sf |Lmax also apply to problem 1|sf , assembly|Lmax . Moreover, algorithms for the former can be used to tackle the latter, under similar assumptions, by simply treating operations as individual jobs. The following results are thus straightforward to obtain but are given for the sake of completeness.

A.E. Gerodimos et al. y Scheduling multi-operation jobs

91

Theorem 2 . Problem 1|sf , assembly|L max is binary NP-hard for an arbitrary number of families F. Proof. The result follows from lemma 1 and the binary NP-hardness of problem 1|sf |Lmax that was established by Bruno and Downey [2]. u In view of theorem 2, we might reasonably expect to find a polynomial algorithm only when the number of families is fixed, or when a simplifying assumption is imposed. Theorem 3. Problem 1|sf , assembly|Lmax can be solved optimally by dynamic programming in O(F 2 n F ) time, which is polynomial for fixed F. Problem 1|sf , assembly, GT|Lmax can be solved optimally by a generalized EDD rule in O(nF + (n + F) log(n + F)) time. Proof. From lemma 1, problem 1|sf , assembly|Lmax can be solved by applying the dynamic programming algorithm of Ghosh and Gupta [9] to the equivalent instance of problem 1|sf |Lmax with at most nF jobs and n jobs per family. From the analysis of Ghosh and Gupta, we observe that the time complexity of their algorithm for such an instance is O(F 2 n F ). Analogously, to solve the restricted problem 1|sf , assembly, GT|Lmax , the generalized EDD algorithm of Potts and Van Wassenhove [18] is applied to the equivalent instance of 1|sf , GT|Lmax . For nF jobs and n jobs per family, this algorithm requires O(nF + (n + F) log(n + F)) time. u Note that lemma 1 and the dynamic programming algorithm of theorem 3 also hold if set-up times are sequence dependent provided that they satisfy the triangle inequality. As the dynamic programming algorithm is exponential in the number of families, it can only work in practice for very small values of F. For a large number of families, theorem 2 shows that it is unlikely that an exact algorithm without this drawback could be devised. Observe that lemma 1 also holds for the problem of minimizing the makespan Cmax . This, however, is a trivial problem which is optimized by any group technology solution (with one batch per family for any sequence of batches), as noted by Monma and Potts [16]. In both the Lmax and Cmax problems, the underlying cause for the equivalence is that only the final operation of each multi-operation job can contribute directly to the objective function value (for the Lmax objective function, each operation of the same job is assigned the same due date). In the subsequent sections, it will become clear that our assembly model is a non-trivial generalization of the family model (without assembly) when the objective function has a direct input from each job. 3.

Minimizing the weighted number of late jobs

In this section, we consider the (weighted) number of late jobs problem. For the simplified problem 1k∑Uj in which set-up times are zero and each job has a single

A.E. Gerodimos et al. y Scheduling multi-operation jobs

92

operation, an O(n log n) algorithm of Moore [17] solves the problem. However, problem 1k∑ wj Uj is binary NP-hard [14], although it is solvable by a pseudo-polynomial algorithm of Lawler and Moore [15]. 3.1. NP-hardness We establish two NP-hardness results for number of late jobs problems in this section. The first result pertains to the case when all the set-up times are equal and the number of families is limited to two. Theorem 4. Problem 1|sf = s, assembly, F = 2|∑Uj is binary NP-hard. Proof. We give a reduction from the following binary NP-complete problem [5]. Equal Cardinality Partition: Given positive integers a1 ,…, a2t , where ∑ i2t=1 ai = 2A, does there exist a subset S of the index set {1,…,2t} such that |S| = t and ∑i ∈S ai = A? Consider an arbitrary instance of Equal Cardinality Partition, where t ≥ 6. We construct a corresponding instance of the decision version of problem 1|sf = s, assembly, F = 2|∑Uj as follows. There are n = 2t + 1 jobs, and the set-up times are s1 = s2 = B, where B = 5tA. The jobs have the following processing times and due dates. Job j p1, j p2, j dj

1

…

n–1

n

A + a1 2A – 2a1 2B + (3t – 1)A + 2

… … …

A + a2t 2A – 2a2t 2B + (3t – 1)A + 2

1 1 2B + (t + 1)A + 2

We show that Equal Cardinality Partition has a solution if and only if there is a solution for the corresponding instance of the two-family scheduling problem in which there are at most t late jobs. Let S be a solution of the given instance of Equal Cardinality Partition. We construct a schedule as follows. A batch of family 1 comprising operation (1, n) and all operations (1, i), for i ∈S, is scheduled first. This is followed by a batch of family 2. In this second batch, operation (2, n) is scheduled first, followed by all operations (2, i), for i ∈S. The remaining jobs are scheduled in two separate batches, in any order. A schedule of the first two batches is illustrated in figure 1. It is easy to see that the schedule thus obtained has exactly t + 1 early jobs and t late jobs. Conversely, assume that there exists a schedule with at most t late jobs. Since the total set-up time of 3B for three batches exceeds the largest due date, there are two batches, one for each family, which contain all operations of the t + 1 (or more) early

A.E. Gerodimos et al. y Scheduling multi-operation jobs

93

Figure 1. Schedule of the early jobs in the proof of theorem 1.

jobs. Consequently, the total processing time of all early jobs is at most (3t – 1)A + 2 < 3(t + 1)A – 2A, which implies that at most t jobs from {1,…, n – 1} are early. Therefore, job n is early, together with exactly t jobs from {1,…, n – 1}. Let S denote the set of early jobs from{1,…, n – 1}, where |S| = t. For the two batches containing operations of early jobs, if the batch of family 2 operations is scheduled before the batch of family 1 operations, then the earliest completion time of job n is 2B + 2tA – 4A + 2, which exceeds dn . Therefore, the schedule starts with a batch of family 1 operations. Since job n completes by time dn , we have 2B + 2 +

∑ ( A + ai ) ≤ 2B + (t + 1)A + 2, i ∈S

which implies that ∑i ∈S ai ≤ A. Also, since the last early job (which is not n) has to complete by its due date, we obtain 2B + 2 +

∑ ( A + ai + 2 A − 2ai ) ≤ 2B + (3t − 1)A + 2, i ∈S

which implies that ∑i ∈S ai ≥ A. Therefore, ∑i ∈S ai = A, and S is a solution of the instance of Equal Cardinality Partition. u Our second result is for the case that all set-up times and all processing times of non-trivial operations are equal to one. Theorem 5. Problem 1|sf = 1, assembly, pfj ∈{0, 1} | ∑Uj is unary NP-hard. Proof. We use a reduction from the following unary NP-complete problem [5]. Three-Dimensional Matching (M): Given a set S # T × U × V of ordered triples with T = {1,…, m}, U = {m + 1,…,2m} and V = {2m + 1,…,3m}, where |S| > m, does there exists a set X , S with |X| = m such that each element t ∈T, u ∈U, and υ ∈V, respectively, occurs in exactly one triple of X? Consider an arbitrary instance of M, and let the elements of S be arbitrarily numbered as 1,…,|S|. We construct an instance of the decision version of problem 1|sf = 1, assembly, pfj ∈{0, 1}| ∑Uj as follows. There are 6m families, with sf = 1 for f = 1,…,6m, a set of 6mz + |S| jobs, where z = |S| – m + 1, that are defined below, and the decision is whether there exists a schedule with at most |S| – m late jobs. For each element j ∈S, we define a “big” job j with 6 operations, each having a processing

94

A.E. Gerodimos et al. y Scheduling multi-operation jobs

time of one unit, and with dj = 6m(z + 2). If j corresponds to (t, u, υ), then the operations are (t, j), (u, j), (υ, j), (6m – υ + 1, j), (6m – u + 1, j) and (6m – t + 1, j). Furthermore, for each family f ( f = 1,…,6m), we define z “small” jobs of type f. Each small job k, for k = |S| + (f – 1)z + 1,…,|S| + fz , has a single operation in family f which has a processing time of one unit, and dk = f (z + 2) – 1. The purpose of the small jobs is to ensure that there will be a set-up for each family in a schedule with at most |S| – m late jobs. Further, the analysis presented below shows that the processing time of one unit for the small jobs ensures that each is early in an optimal schedule. In combination, the first three and the last three operations of each big job are constructed to ensure that a feasible schedule with m early big jobs and no late small jobs contains exactly one operation in each family, as we show later in the proof. We show that M has a solution if and only if there is a solution of the corresponding instance of the scheduling problem with at most |S| – m late jobs. Let X be a solution of the given instance of M. Consider a subset of jobs comprising the big jobs corresponding to the m elements of X and all of the small jobs. This subset of jobs consists of z + 1 operations in each of the 6m families. We construct a schedule in which there is a single batch of operations for each family, with all small jobs placed in the first z positions, and the one operation of a big job assigned to the last position, in the corresponding batch. The batches are processed in natural order, so the small jobs of type f, for f = 1,…,6m, complete processing at time f (z + 2) – 1, and the last of the big jobs completes processing at time 6m(z + 2), as shown in figure 2. After these 6m batches, the operations of the remaining big jobs are scheduled arbitrarily. Thus, all small jobs and m big jobs are early, whereas the remaining |S| – m big jobs are late.

Figure 2. Schedule of the early jobs in the proof of theorem 5.

Conversely, assume that there exists a schedule with at most |S| – m late jobs. Since |S| – m = z – 1, at least one small job of each family and at least one big job have to be early. Consequently, the schedule of early jobs contains at least 6m units of set-up time, and has total set-up plus processing time that does not exceed the maximum due date of 6m(z + 2). Since at least 6mz + m jobs have to be early, and each job is either small with one operation or big with six operations, there can be at most m early big jobs, and there are at least 6mz early small jobs. On the other hand, there are only 6mz small jobs in total. Thus, all small jobs and exactly m big jobs are early. Moreover, since the time available for set-ups before the largest due date is equal to 6m, all operations of early jobs of each family are processed together in one batch. We

A.E. Gerodimos et al. y Scheduling multi-operation jobs

95

may assume that the batches are processed in natural order of the corresponding families: otherwise, adjacent batches are interchanged until this property holds. It remains to consider how the operations of the early big jobs are distributed among the families. Observe that, for each family, the set-up plus total processing time for the small jobs is equal to z + 1. The due date for small jobs in family f is f (z + 2) – 1, for f = 1,…,6m. Thus, the number of operations of early big jobs in families 1,…, f is at most f, for f = 1,…,6m – 1. Moreover, by construction, a big job has an operation in family f if and only if it has an operation in family 6m – f + 1. Therefore, the number of operations of early big jobs in families f + 1,…,6m is the same as the number of operations of early big jobs in families 1,…,6m – f, for f = 1,…,6m – 1, which is no more than 6m – f. Since there are precisely 6m operations of early big jobs in total, there are at least f operations of early big jobs in families 1,…, f, for f = 1,…,6m – 1. Consequently, there is exactly one operation of an early big job in each of the families 1,…,6m – 1. It follows that the other operation of an early big job is in family 6m. Hence, the schedule is of the form depicted in figure 2, and the set of triples (t, u, υ) corresponding to the m early big jobs is therefore a solution of M. u 3.2. A dynamic programming algorithm In this section, we develop an algorithm for minimizing the weighted number of late jobs. Unfortunately, we cannot adopt a similar approach to that in section 2 for minimizing the maximum lateness. Such an approach of assigning due dates to operations, and then applying the dynamic programming algorithm of Monma and Potts [16] to minimize the weighted number of late operations fails because the resulting solution may have at least one job with both early and late operations. Instead, we develop a problem-specific dynamic programming algorithm. Our first result states that each operation of an early job may be placed in the latest possible batch (before its due date). Lemma 6 . Problem 1|sf , assembly|∑wj Uj has an optimal solution with the property that each operation ( f, j) of an early job j is scheduled in the last batch of family f that starts processing before time dj . Proof. Consider an optimal schedule in which some operation ( f, j) of an early job j is scheduled in a batch which is not the last batch of family f that starts processing before time dj . Then operation ( f, j) is in an earlier batch. Now consider the transformed schedule where ( f, j) is positioned first in the last batch of family f such that the above condition is satisfied. In the new schedule, operation ( f, j) still completes by time dj , and no other operation is processed later than in the original schedule. Thus, the new schedule is optimal. A finite number of repetitions of this argument yields an optimal schedule that satisfies the property of the lemma. u

96

A.E. Gerodimos et al. y Scheduling multi-operation jobs

If problem 1|sf , assembly|∑wj Uj has missing operations, then we define a corresponding expanded problem with no missing operations by regarding each trivial operation ( f, j) as an operation which has to be processed on the machine instantaneously. In this expanded problem, any batch containing only trivial non-final operations is assigned a zero set-up time. The following result establishes some properties of an optimal solution for the expanded problem. Lemma 7. The expanded version of problem 1|sf , assembly|∑wj Uj has an optimal solution with the property that, within each family, operations of early jobs are sequenced in EDD order. Proof. Consider an optimal schedule of early jobs for the expanded problem that satisfies the property of lemma 6. In such a schedule, no operation ( f, j) is contained in a batch that precedes the batch containing operation ( f, i), where di < dj . Within a batch, a simple interchange argument shows that all operations may be scheduled in EDD order. Thus, within each family, all operations of early jobs are sequenced in EDD order. u The following result is a consequence of lemmas 6 and 7. Corollary 8. The expanded version of problem 1|sf , assembly|∑wj Uj has an optimal solution in which the final operations of early jobs complete in EDD order. We now show how the expanded problem is used to solve the original problem. Lemma 9. An optimal solution of the expanded version of problem 1|sf , assembly|∑wj Uj is an optimal solution of the original problem. Proof. From lemma 7, we restrict our attention to schedules in which operations of early jobs within each family are sequenced in EDD order. We first establish that there is an optimal solution of the expanded problem with the property that, except for the first batch of each family which may contain only trivial operations, no batch starts with a trivial operation. If a trivial operation ( f, j) starts a batch (and it is not the first batch of family f that contains only trivial operations), then a new schedule is constructed in which operation ( f, j) is placed at the end of the previous batch containing operations of family f, or in a new batch at the start of the schedule if there is no such previous batch. This new schedule is also optimal. A finite number of repetitions of this process yields a schedule with the desired property. From this property, the presence of trivial operations does not affect scheduling decisions, and an optimal solution of the expanded problem defines an optimal solution of the original problem. u

A.E. Gerodimos et al. y Scheduling multi-operation jobs

97

In view of lemma 9, we describe a backward dynamic programming scheme for the expanded problem. In accordance with corollary 8, final operations are sequenced in EDD order, and therefore jobs are considered in reverse EDD order. Suppose that we make the decision that some job j is early, and we schedule the final operation of j. Then, lemma 6 suggests that we can schedule all the remaining operations of job j as near to the end of the schedule as possible, i.e. in the last prior occurrence of a batch of the family to which these operations belong. As a consequence, non-final operations can be stored as F sub-batches of processing time, one for each family, which are scheduled when appropriate. We may therefore focus on scheduling final operations, and simply ensure that sufficient time is available at the start of the schedule to accommodate the sub-batches of non-final operations. This method eliminates the need to keep track of the identity of non-final operations that await scheduling. We are now ready to present our backward recursion dynamic program. The algorithm proceeds as follows. First we re-index the jobs according to the EDD rule, and include all operations regardless of whether their processing time is zero. We consider final operations for inclusion in the schedule in reverse order, starting with job n, then job n – 1, and so on. Late jobs are not included in the schedule since they can be appended after all of the early jobs are scheduled. A state ( j, f, t, P1,…, PF) corresponds to a (partial) schedule for early jobs j,…, n, where: • j is the index of the last job considered for inclusion (decisions for jobs j,…, n have already been made); • f is the family of the first operation ( f, k) of the schedule, where k ≥ j; • t is the start time of operation ( f, k) (the set-up time sf for the first family is not currently included, and some sub-batches are not currently scheduled); • Pg is the total processing time of the sub-batch of operations of each family g waiting to be scheduled at the last occurrence of a batch of g in the interval [0, t], where Pf = 0 from lemma 6 since f is the current family. We only consider feasible states, which are those that allow the set-up time for family f as well as the set-up and processing times of the pending operations for all other families to be inserted before time t. Thus, state ( j, f, t, P1,…, PF) is feasible if and only if F

sf +

∑ Pg + ∑

g= 1

sg ≤ t.

g | Pg > 0

Note that this condition assumes that any batch containing only trivial non-final operations has a zero set-up time, which is consistent with our definition of the expanded problem. In our algorithm, G( j, f, t, P1,…, PF) is the value of the objective function, i.e. the minimum weighted number of late jobs, for a schedule corresponding to state ( j, f, t, P1,…, PF). The initial conditions are of the form

98

A.E. Gerodimos et al. y Scheduling multi-operation jobs

G(n + 1, f, d n , 0,…, 0) = 0, f = 1,…, F, and all other initial values are set to infinity. This means that we start with no jobs scheduled, any early jobs to be added must complete no later than time dn (the largest due date), and there are no pending operations to be scheduled before this time. Note that it is not necessary to consider initial values of t in excess of dn ; any job starting after that time is a priori late. From a given state ( j, f, t, P1,…, PF), we can generate other states by considering job j – 1 for inclusion in the schedule or by scheduling some sub-batch. This can be done in one of the three following ways: 1.

Schedule job j – 1 to be late. There is no change to the schedule and we obtain the state ( j – 1, f, t, P1,…, PF), which has a candidate value G( j, f, t, P1,…, PF) + wj –1 .

2.

Attempt to schedule job j – 1 early and continue with family f. We schedule operation ( f, j – 1) at the beginning of the current batch. According to lemma 6, all operations (g, j – 1) for g ≠ f are put into the corresponding sub-batch of operations to be scheduled at the last prior occurrence of a batch of family g. We thus obtain the state ( j − 1, f , min{d j −1 , t} − p f , j −1, P1′, …, PF′ ), where P′g = Pg + pg, j –1 for g ≠ f, and P′f = 0. If this state is not feasible, we ignore this possibility. Otherwise, the state has a candidate value G( j, f, t, P1,…, PF).

3.

Schedule a sub-batch of some family f ′, where f ′ ≠ f. Because of the changeover, we incur a set-up time sf for family f (recall that we are building the schedule backwards). Thus, we obtain the state ( j, f ′, t − s f − Pf ′ , P1′, …, PF′ ), where P′g = Pg for g ≠ f ′ and P′f ′ = 0. In this case, the new state is necessarily feasible and has a candidate value G( j, f, t, P1,…, PF).

When a candidate value for a state is obtained, it is compared with the value currently stored. If the candidate value is less, then it is stored, thereby replacing the previous value. The optimal solution value is min{G(1, f , t, P1 , …, PF )}, where the minimization is over all feasible states (1, f, t, P1,…, PF ). An optimal schedule can be found by backtracking. Note that when the final operation of an early job completes at its due date, the schedule may contain some idle time. Such idle time can be removed. Finally, to convert the optimal schedule for the expanded problem to a

A.E. Gerodimos et al. y Scheduling multi-operation jobs

99

schedule for the original problem, any trivial operations and set-up times generated by trivial operations are eliminated. We now discuss the time requirement of the dynamic programming algorithm. An obvious upper bound on the values of t, and P1,…, PF that may occur in a feasible state is dmax = max j =1,…, n{dj} (where dmax = dn under our EDD indexing). Since there F+ 1 are O(n) values of j and O(F) values of f, there are O(nFd max ) feasible states. Each state generates at most F + 1 new states, each of which is evaluated in constant time. F +1 Thus, the overall time requirement is O(nF 2d max ) for arbitrary F. For a fixed number of families, the algorithm becomes pseudo-polynomial. 4.

Minimizing the sum of completion times

In this section, the total completion time problem is examined. For the simplified problem 1k∑Cj in which set-up times are zero and each job has a single operation, the jobs are sequenced in shortest processing time (SPT) order in any optimal schedule. We first consider the group technology variant under the assumption that no missing operations are allowed. Lemma 10. Problem 1|sf , assembly, GT, pfj > 0|∑Cj can be solved optimally in O(Fn log n) time. Proof. Since the GT assumption holds, in an optimal schedule there will be exactly F batches, one for each family. As no missing operations are allowed, all jobs complete within the last batch. Thus, the operations within the last batch have to be sequenced in SPT order, and an optimal solution may be obtained by comparing the F schedules obtained by positioning each of the batches last. Since sequencing all operations in a batch requires O(n log n) time, it follows that the overall time requirement is O(Fn log n). u In a recent paper [12], Gupta et al. address the bicriterion problem 1|sf , assembly, pfj > 0|Cmax |∑ Ij , where Ij is the elapsed time between the completion of processing for the first and last operation of job j. In this problem, the primary objective is to minimize the makespan, and the secondary objective is equivalent to minimizing the total idle time between the operations of the jobs. They propose an O(Fn log n) solution procedure which is essentially a straightforward generalization of the above lemma. To see this, recall that any group technology schedule is an optimal solution to the makespan problem, so the original problem reduces to problem 1|sf , assembly, GT, pfj > 0|∑ Ij . The latter problem is solved optimally by positioning each of the batches in the last and first position of the schedule and sequencing the operations within the batches in those positions in SPT and LPT (longest processing time) order, respectively.

100

A.E. Gerodimos et al. y Scheduling multi-operation jobs

We now discuss some properties of an optimal schedule for our assembly problem, where the above assumptions are no longer imposed. Lemma 11. Problem 1|sf , assembly|∑ Cj has an optimal solution with the property that any final operations within a batch are sequenced in SPT order, followed by any non-final operations in arbitrary order. Proof. It is straightforward to observe that the non-final operations should be scheduled after the final ones within a batch; moving a non-final operation in an optimal solution to the end of its batch does not increase the completion time of any job and optimality is preserved. Also, the ordering of non-final operations within a batch does not affect the total completion time. If the final operations of a batch of jobs of some family f are not sequenced in SPT order, then some operation ( f, j) is sequenced immediately before an operation ( f, i), where pfj > pfi . As is the case for the classic single machine problem 1k∑Cj , interchanging operations ( f, j) and ( f, i) reduces the total completion time. Therefore, the final operations within a batch must be sequenced in SPT order. u The following lemma is very helpful for developing a dynamic programming algorithm. This result is a generalization of a similar property for two-operation models and, as pointed out by Baker [1], it can be viewed as a scheduling equivalent of the classic planning horizon property for the Wagner–Whitin model [22]. Lemma 12. Problem 1|sf , assembly|∑Cj has an optimal solution with the property that any non-final operation of a job appears in the last batch of the appropriate family that is scheduled before the batch containing its final operation. Proof. Consider an optimal schedule without the desired property. Suppose that a non-final operation is moved to the latest possible batch of the family to which it belongs (while remaining a non-final operation). Since this transformation does not increase any job completion time, the new schedule is also optimal. A finite number of repetitions of this argument yields an optimal schedule that satisfies the property of the lemma. u Note that lemma 12 holds for any regular objective function. In particular, it applies for the problem of minimizing the weighted number of late jobs, and is implicit in lemma 6. Lemma 12 allows us to employ a backward recursion dynamic programming algorithm. As with the weighted number of late jobs problem, only final operations are included explicitly in the schedules; non-final operations are stored in F subbatches and scheduled when a batch of the appropriate family is processed. However,

A.E. Gerodimos et al. y Scheduling multi-operation jobs

101

there is no predetermined order in which the jobs complete; unfortunately, lemma 11 holds only within a batch. To ensure that jobs complete in SPT order with respect to their total processing time, we need to make the SPT-agreeability assumption, which is defined in section 1.3. Note that, under this assumption, the problem instances in which jobs can have missing operations have a very restricted structure which makes them of limited interest. To avoid unnecessary formalism, we shall therefore focus our attention on problem instances in which no missing operations are allowed. We now show that the SPT-agreeability assumption enables us to decouple the tasks of sequencing and batching. Lemma 13. For problem 1|sf , assembly, SPT-agree|∑Cj , there is an optimal schedule in which jobs complete in SPT order. Proof. Consider an optimal schedule in which job j is completed before job i, where pi < pj . We transform this schedule by interchanging, for each family f, operations ( f, i) and ( f, j) if ( f, j) is sequenced before ( f, i). Such a transformation does not introduce any new set-up times. Moreover, since pfi ≤ pfj , the only operations that are completed later in the new schedule are those corresponding to job j. If Ci and Cj are the completion times of jobs i and j in the original schedule, and Ci′and Cj′ are their completion times in the transformed schedule, then C′j = Ci and Ci′ ≤ Cj . Therefore, the total completion time does not increase as a result of the interchange, and the new schedule is optimal. A finite number of repetitions of this argument yields an optimal schedule that satisfies the property of the lemma. u In our backward recursion dynamic program for problem 1|sf , assembly, SPTagree|∑ Cj, lemmas 12 and 13 play the same fundamental role as lemmas 6 and 7, respectively, in section 3.2. In view of lemma 13, the jobs are first re-indexed according to the SPT rule so that p1 ≤ … ≤ pn , and we consider jobs for inclusion in the schedule in reverse order. A state ( j, f, l1,…, lF) corresponds to a (partial) schedule for jobs j,…, n, where: • j is the index of the last job with a scheduled final operation (the final operations of jobs j,…, n have already been scheduled); • f is the family of the first operation ( f, j) of the schedule; • processing starts at time zero (the set-up time sf for the first family is not currently included, and some sub-batches are not currently scheduled); • lg is the job index of the last included operation of family g, where lf = j for the current family f, so that sub-batches containing operations ( j, g),…,(lg – 1, g) of each family g are waiting to be inserted into the schedule. Note that, for this problem where no jobs are excluded as late, the F sub-batches always contain non-final operations with contiguous job indices. Thus, to compute

102

A.E. Gerodimos et al. y Scheduling multi-operation jobs

the total processing time of pending operations of each family g, it suffices to store the job index lg of the last included operation of that family. In our algorithm, G( j, f, l1,…, lF) is the value of the objective function, i.e. the minimum sum of completion times, for a schedule corresponding to state ( j, f, l1,…, lF). Observe that there is no need to explicitly keep track of the starting time of the schedule, as is the case for the weighted number of late jobs problem. Instead, we always start at time zero and simply shift the entire schedule to the right by a quantity equal to the set-up plus processing time corresponding to the insertion. In this way, we simplify the state space by omitting the variable that defines the starting time. Such a scheme has proved useful for the standard family scheduling models (see [8,9]). Also, we replace state variables that define the total processing time of sub-batches with job index variables. Our initial conditions are of the form G(n + 1, f, n + 1,…, n + 1) = 0, f = 1,…, F, and all other values are set to infinity. From a given state ( j, f, l1,…, lF), we can generate other states by including job j – 1 in the schedule, or by scheduling some sub-batch, as follows: 1.

Schedule job j – 1 and continue with family f. We schedule operation ( f, j – 1) at the beginning of the current batch. According to lemma 12, all operations (g, j – 1) for g ≠ f must be scheduled at the last prior occurrence of a batch of family g. We thus obtain the state ( j – 1, f, l 1′ ,…, lF′ ), where lg′ = lg for g ≠ f, and l f′ = j – 1. By inserting operation ( f, j – 1), the completion times of jobs j,…, n are each delayed by time pf, j –1 , and job j – 1 is completed at time pf, j –1 in the schedule corresponding to the new state. Therefore, the new state has candidate value G( j, f , l1, …, lF ) + (n − j + 2) p f, j −1 .

2.

Schedule a sub-batch of some family f ′, where f ′ ≠ f. We thus incur a set-up time sf for family f, and the sub-batch has a total processing time of ∑ lmf ′=− j1 p f ′m . We thus obtain the state ( j, f ′, l 1′ ,…, l F′ ), where l g′ = lg for g ≠ f ′ and l f′′ = j. Since jobs j, …, n are delayed by time ∑ lmf ′=− j1 p f ′m + sf , the new state has candidate value  G( j, f , l1, …, lF ) + (n − j + 1)   

l f ′ −1

∑

m=j

 p f ′m + s f  .  

As in section 3.2, the value of a state is updated whenever a candidate value is found which is less than the value that is currently stored. The optimal solution value is    min G(1, f , l1, …, lF ) + n  s f +    

F

∑

g =1 g≠ f

l g −1     s + p gm   ,  f   m =1   

∑

A.E. Gerodimos et al. y Scheduling multi-operation jobs

103

where the minimization is over all states (1, f, l1,…, lF). An optimal schedule is found by backtracking. In the analysis of the time complexity of the dynamic programming algorithm, n is an upper bound on the values of l1,…, lF . Using similar arguments to those in section 3.2, we find that there are O(Fn F +1 ) states, and that the overall time requirement of the proposed algorithm is O(F 2 n F +1 ), for arbitrary F. Thus, the algorithm becomes polynomial for a fixed number of families. 5.

Concluding remarks

In this paper, we have studied the scheduling of production of multi-operation jobs on a single machine. The problem of minimizing the maximum lateness is shown to be equivalent to its well-known family counterpart. The problem of minimizing the number of late jobs is shown to be unary NP-hard. Using properties that enable us to decouple the tasks of batching and sequencing, we derive a dynamic programming algorithm that solves the weighted number of late jobs problem in pseudo-polynomial time, when the number of families is fixed. An adaptation of this algorithm solves the sum of completion times problem in polynomial time under the assumption that the SPT orderings of operations in families are agreeable. Table 1 provides a summary of Table 1 Complexity of multi-operation scheduling on a single machine. Objective (restriction)

F

Complexity

Best algorithm

fixed

P

O(n F )

arbitrary

binary NP-hard

O(F 2 n F)

fixed

binary NP-hard

O(ndmax )

arbitrary

unary NP-hard

O(nF dmax )

∑Cj

fixed

P

O(n F +1 )

(SPT-agreeability)

arbitrary

open

O(F 2 n F +1 )

∑Cj

fixed and arbitrary

open

–

Lmax

∑wj Uj

F +1

2 F+1

complexity results and algorithms. Although the dynamic programming algorithms for the number of late jobs problem and the sum of completion times problem are developed for sequence independent set-up times, these algorithms can be generalized to the case of sequence dependent set-up times, and for fixed F there is no increase in the time complexity.

104

A.E. Gerodimos et al. y Scheduling multi-operation jobs

Most of the open questions are related to the sum of completion times problem. This problem is a generalization of the corresponding family scheduling problem in which is open (see [18]), but suspected to be NP-hard. Our problem is even less tractable. The main difficulty is that jobs do not necessarily complete according to the SPT rule, and thus batching and sequencing cannot be decoupled. This seems to be the case even for the simpler group technology variant when we allow jobs to have missing operations. A starting point for future investigation would be the slightly more structured variant in which there are only two families. Extending the model to more general machine environments such as parallel machines or multiple stages is also an interesting research topic. Another possible direction is to study variants of our model under the batch availability assumption (see [19]). Acknowledgements The first author’s research was supported by Dalgety plc. The research by the last three authors was partly funded by INTAS (Project INTAS-93-257 and INTAS93-257-Ext). Moreover, the last author was partly supported by the Deutscher Akademischer Austauschdienst. The authors would also like to acknowledge anonymous referees for their suggestions which improved the readability of the paper. References [1]

K.R. Baker, Scheduling the production of components at a common facility, IIE Transactions 20 (1988)32–35. [2] 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. [3] E.G. Coffman, Jr, A. Nozari and M. Yannakakis, Optimal scheduling of products with two subassemblies on a single machine, Operations Research 37(1989)426–436. [4] E.G. Coffman, Jr, M. Yannakakis, M.J Magazine and C.A. Santos, Batch sizing and job sequencing on a single machine, Annals of Operations Research 26(1990)135–147. [5] M.R. Garey and D.S. Johnson, Computers and Intractability; A Guide to the Theory of NPCompleteness, Freeman, 1979. [6] A.E. Gerodimos, C.A. Glass and C.N. Potts, Scheduling the production of two-component jobs on a single machine, European Journal of Operational Research, to appear. [7] A.E. Gerodimos, C.A. Glass and C.N. Potts, Batching and sequencing of customised jobs on a single machine: The item availability case, Preprint OR88, University of Southampton, UK, 1997. [8] J.B. Ghosh, Batch scheduling to minimize total completion time, Operations Research Letters 16(1994)271–275. [9] J.B. Ghosh and J.N.D. Gupta, Batch scheduling to minimize maximum lateness, Operations Research Letters 21(1997)77–80. [10] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics 5(1979)287– 326. [11] H. Groenevelt, The just-in-time system, in: Logistics of Production and Inventory, eds. S.C. Graves, A.H.G. Rinnooy Kan and P.H. Zipkin, Handbooks in Operations Research and Management Science, Vol. 4, North-Holland, 1993, pp. 629–670.

A.E. Gerodimos et al. y Scheduling multi-operation jobs

105

[12] J.N.D. Gupta, J.C. Ho and J.A.A. van der Veen, Single machine hierarchical scheduling with customer orders and multiple job classes, Annals of Operations Research 70(1997)127–143. [13] F.M. Julien and M.J. Magazine, Scheduling customer orders: An alternative production scheduling approach, Journal of Manufacturing and Operations Management 3(1990)177–199. [14] R.M. Karp, Reducibility among combinatorial problems, in: Complexity of Computer Computations, eds. R.E. Miller and J.W. Thatcher, Plenum Press, 1972, pp. 85–103. [15] E.L. Lawler and J.M. Moore, A functional equation and its application to resource allocation and sequencing problems, Management Science 16(1969)77–84. [16] C.L. Monma and C.N. Potts, On the complexity of scheduling with batch setup times, Operations Research 37(1988)798–804. [17] J.M. Moore, An n job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science 15(1968)102–109. [18] C.N. Potts and L.N. Van Wassenhove, Integrating scheduling with batching and lot sizing: A review of algorithms and complexity, Journal of the Operational Research Society 43(1992)395–406. [19] C.A. Santos and M.J. Magazine, Batching in single operation manufacturing systems, Operations Research Letters 4(1985)99–103. [20] R. Simons, Planning and scheduling in oil refineries, OR Newsletter 313(1997)26–28. [21] R.G. Vickson, M.J. Magazine and C.A. Santos, Batching and sequencing of components at a single facility, IIE Transactions 25(1993)65–70. [22] H.M. Wagner and T.M. Whitin, Dynamic version of the economic lot size model, Management Science 5(1958)89–96.