Admissible Search Methods for Minimum Penalty Sequencing of Jobs with Setup Times on One and Two Machines

1 Introduction

Recent years have witnessed a renewed spurt of interest in the theory and implementation of best-first search techniques [Pearl, 1984]. This interest is yet to be adequately reflected, however, in the application of AI search methods to optimization problems that arise in industry, many of which cannot be solved conveniently by any of the known algorithms. Viswanathan and Bagchi [1988] describe a successful attempt at applying search methods to rectangular cutting stock problems, but such examples are few. In this context, an area that appears to hold great promise is sequencing and scheduling, where most problems of practical importance require the use of branch-and-bound or dynamic programming methods [French, 1982; Lawler et al.,

1982]. Now that efficient implementations of best-first search algorithms such as A·, IDA· [Korf, 1985], and MREC [Sen and Bagchi, 1989] have been realized, search could prove superior to other methods in cases where reasonably tight lower bounds can be derived.

This paper investigates the role that best..:first search can play in solving certain types of one-machine and two-machine job sequencing problems that arise in job­ shops and flow-shops. The major objective is to enlarge the sphere of application of best-first search, and at the same time to illustrate how good admissible heuristics can be defined for practical problems. A typical problem studied by us has the following form. Jobs 1 1 , 1 5 i 5 n, with processing times a1, 1 .s i 5 n, have been submitted to a one-machine job-shop at time t = 0. The jobs are to be processed on the given machine one at a time. Let the processing of job 1 1 be completed at time f 1 · Penalty functions 0 1 (.}, 1 5 i 5 n, are supplied, such that the penalty associated with completing job 11 at time f1 is G 1 (f1). An example of a penalty function is G 1 (f 1 ) = c 1 f?, where the c;'s are given constants, the penalty associated with a job being proportional to the square of the finish time of the job. The jobs must be sequenced on the machine in such a way that the total penalty

F = L { 01(~) I 1 5 i .s n }

is minimized The penalty functions are non-decreasing, and in general non-linear. Moreover, a job has a setup time that is independent of its position in the processing sequence; we say that the setup times are separable. In a more general formulation, the setup times can be sequence-dependent, i.e. the setup time of a job can depend on the job that immediately precedes it in the processing sequence. Problems of this type have obvious relevance to industry, but are known to be very hard to solve satisfactorily in their full generality, the number of job sequences being exponential in the number of jobs. No efficient general methods of solution have been reported. Schild and Fredman [1963] proposed a scheme for non-linear penalty functions that ignored setup times but nevertheless required a great deal of computation; improvements were subsequently suggested by Townsend [1978] and Bagga and Kalra [1980], but these were specific to quadratic penalty functions. Another special case has been studied by Rinnooy Kan et al. [1975]. As for two-machine flowshop situations, work has been confined to the determination of minimum length schedules in the presence of setup times (see, for example, [Gupta and Darrow, 1985; Sule, 1982; Corwin and Esogbue, 1974]); penalty functions have not yet been considered by anyone in any detail.

This paper, which is in the nature of a preliminary report, describes how best-first search techniques can be used to determine minimal penalty job sequences for one and two machines when the setup times are separable. A"' is the search algorithm used. Each case involves the computation of a reasonably tight lower bound that can serve to guide the search fairly narrowly to a goal. Search graphs have been implemented as graphs and not as trees whenever it has been found possible to do so; this tends to speed up the execution. In the two-machine case the search methods given below are not always order preserving [Pearl, 1984, p. 102], and unless the search graph is a tree the solution may not be optimal. The programs have been run on random data that try to simulate real~life situations. The results we have obtained are most encouraging; our main contribution lies in showing how useful best-first search can be in attacking job sequencing problems traditionally reganled as very difficult, such as the determination of a minimum penalty job sequence for a two-machine flow-shop however simple the penalty function, or for a single machine when the penalty for a job is proportional to a non-integral power of the finish time of the job.

2 One Machine Job Sequencing Problems

2.1 Problem Description

For the one-machine problem with sequence-dependent setup times we define the following notation :

number of jobs

ith job

fi di Gi(.) Ci F processing time ( > 0 ) for job Ji setup time for job Ji when it immediately follows job Ji in the processing sequence completion time of job Ji deadline for job Ji penalty function for job Ji penalty coefficient for job Ji total penalty for a given sequence

If Ji is the first job in the sequence, then So,i represents its setup time. After the last job in the sequence is completed, the machine need not be brought back to any specific state. A penalty of Gi(fi - d;) is incurred for job Ji when f; > d,; if fi 5 d; then no penalty is incurred for Ji. The formulation can be generalized to include the cost of carrying in inventory those jobs that get completed before their respective deadlines. In order to simplify the problem it is frequently assumed that all deadlines are zero; we make this assumption in the paper.

When the setup times are separable as in [Sule, 1982], we have the following alternative notation :

• Pi initialization time for job Ji

qi cleanup time for job Ji

A;

Pi + a;+ qi Initialization time refers to the time needed to initialize the machine settings before job Ji can be processed, while cleanup time refers to the time needed to clean the machine and bring it back to a specified state after the processing of job Ji has been completed. When job Ji follows job Ji in the sequence, the total setup time (<I; + p.) can be viewed as corresponding to sij in the general c~e; again, if Ji is the first job in the sequence, then Pi corresponds to So,i in the general case. Let the jobs be processed in the sequence Jj(l)· J~(2)· · · · ' Jj(n) and let the completion time of JOb Jj(k.) be ~(It)· Then for 1 5 k 5 n, ~(k) = L { ~(i) I 1 5 i 5 k } - <J,j(k)· Note that the finish time of a job does not include the cleanup time for the job; the cleanup time gets added when the finish times of the jobs that follow in the sequence are computed. For one-machine problems, there is no loss of generality if the initialization time of a job is included in the processing time and not considered separately. As an illustration of the kind of problem we are trying to solve, consider the following example:

Example: Penalty for a job J 1 proportional to its finish time fi; separable setup times.

Here, Gi(fi) = c;fi, where the ci's are constants, ci being the penalty coefficient for job J1· Thus

= Lt ci(k) 2., { Ai(i) I 1 5 i 5 k } - Lt Ct ~ To minimize F we just need to arrange the jobs in the order [French, 1982]:

F = L { ci(k~(k) I 1 5 k 5 n }

Aj(t/C·(t) 5 ~(2fc'(2) 5 · · · 5 ~(n..Jcj(n)· since the fast sum in ~e expression for F is a constant. Here we do not need to take help of search methods. D

In more complex situations we are forced to take recourse to AI search methods. Algorithm A"' is imple­ mented in the standanl manner [Nilsson, 1980; Pearl, 1984]. OPEN is maintained as a priority queue. Nodes generally correspond to unordered subsets of jobs; the root node is the empty set. When a node corresponding to a subset of k jobs gets selected from OPEN and expanded, it generates (n-k) sons, each son being a subset of (k+1) jobs. A problem gets solved when a complete set of n jobs gets selected from OPEN. For two-machine problems, a node sometimes corresponds to an ordered sequence of jobs. The following additional notation is used in the specifications of the problems:

2.2 Non-Linear Penalty Functions

Case I Penalty for a job proportional to square of its completion time; all initialization and cleanup times are zero.

Here �;(~) = c;f; 2 · Towmend [1978] proposed a new method for computing l..>wer bounds in a best-first branch-and-bound algorithm to solve this problem; certain improvements were subsequently suggested by Bagga and Kalra [1982]. We compute the heuristic estimate h(N) at the current node N as follows :

Order the processing times Of the m jobs in Q in the non-decreasing order

~(I) ~ aj(2) ~ ··· ~ aj(m) Also order tfle penalty coefficients of the jobs in Q independently in the non-increasing order

Take the heuristic estimate as

~(k) = T + L { li:J<u> I 1 ~ u ~ k } ,

where

and T = I. { ax I Jk is in P } .

Our computation ensures that h(N) is a lower bound on h*(N), the cost of the optimal path from N to a goal, since the penalty functions strictly dominate each other and have no crossover points. The sorting of the processing times and the penalty coefficients is done only once at start. Thereafter, we just have to keep track of which jobs are in Q, and when computing the heuristic estimate we simply skip over those terms in the sorted lists that correspond to jobs in P.

The method can be generalized to handle penalty functions for job J; that are proportional to (f;)'i. or to exp(~). where k is a real constant independent of i. Such functional forms have not been considered by Townsend [1978] or Bagga and Kalra [1980].

In our experiments, programs were written in C and run on the SUN 3/60 workstation. The search graph was a graph and not a tree. The heuristic is monotone [Nilsson, 1980], so that a node is expanded at most once. But it is still advantageous to use a graph representation because this allows the g-values of unexpanded nodes to get updated in OPEN. A tree representation causes an explosion in the number of nodes generated and expanded. To implement graphs efficiently, we need to be able to find out quickly whether a newly generated successor is already present in the graph. This can be achieved by the use of a hashing scheme. A node N corresponds to a subset of jobs; the bit representation of N is viewed as a binary number which is then hashed using the modulo method. All particulars about a node are stored in the hash table; entries in the priority queue are pointers to the hash table. Two different penalty functions of the form G;(f;) = c;(f;)k were considered, with k = 2.0 and k = 1.5. Processi.ilg times (~) of jobs were integers and were chosen randomly in the range 1 to 99 from a unifotm distribution. Penalty coefficients ( c;) were also integers and were generated in the range 1 to 9 in the same way. For each set of jobs, the execution time, the total number of nodes generated, and the total number of nodes expanded were averaged over 25 runs. Results are given in Table I. It was found experimentally that for k = 2, Townsend's algorithm runs slightly faster than ours, but these results are not shown in the table.

For k = 1.5, computations were done using real numbers, and so the execution times are larger. The heuristic is quite tight: For 14 jobs, only 7561 nodes are generated when k = 2.0, while there are 141 job sequences.

Case n Penalty for a job proportional to square of its completion time; separable setup times.

No algorithm has yet been proposed for this problem. We determine the heuristic estimate h(N) as follows. Let q = min { ~ I Jk is in Q }

Order the jobs in Q according to the conditions

(pj(l) + li:J(l)) ~ (Pj(2) + li:Jgl) . ~ · · · ~. (Pj{m) + ~(m1· and order the penalty coeffietents as m Case I. The expression for h(N) is the same as in Case I, but here take ~(k) = T + <but + L { (pj(u) + ll;i(u)) I 1 ~ U ~ k } + (k - 1)q

As in Case I, h(N) ~ h*(N), and h is monotone. Again, the method can be extended to powers other than two and to exponentials. A · was run with the above heuristics. Data was generated as in Case I; the initialization and cleanup times were also generated randomly, but in the range 1 to 9 to keep them smaller than the processing times. Nodes still correspond to unordered subsets of jobs. Results are shown in Table n for the case k = 2. A depth-first branch-and~bound implementation was also tried out, but was found to be much slower in execution.

casem General non-linear penalty functions; separable setup times.

This generalizes Case ll. Here we consider penalty functions G; that have the non-negative integers as domain and the non-negative real numbers as range; each G; is non-decreasing and possibly non-linear, and the G;'s do not necessarily have identical functional forms [Schild and Fredman, 1963]. Let q, T and ~(k) be defined as in Case II, and let G(x) = min { G;(x) I J; is in Q }.

When computing the heuristic estimate arrange the jobs as in Case II and then use G and q instead of the G;'s and the q;'s, but when computing g(N) use the actual G; and q; values. Close bounds are hard to obtain when the G;'s have different functional forms.

~ h(N) 5 h*(N).

Proof: Express h*(N) as a function of T, and of the parameters G;. p;. a; and q; of the jobs J; in Q. Replace each occurrence of G; and q; in the expression for h*(N) by G and q respectively; this gives a value ho(N) 5 h*(N). But when G and q are used tor computing the heuristic estimate, h(N) is the smallest estimate we can get, so that we must have h(N) 5 ho(N). 0

Some experimental results are given in Table ill. As before, nodes correspond to unordered sets of jobs and the heuristic is monotone. The penalty functions were chosen to have the form G;(f;) = c;f; + C;·(~) 2 . The coefficients c; and C;· were both randomly generated in the range 1 to 9.

3 Two-Machine Flow-Shop Problems

In the two-machine flow-shop problem, each job must be processed twice; it must be processed on the first machine before it is processed on the second machine. The completion time of a job is the time at which its processing on the second · machine is finished. The classic algorithm of Johnson [1954] finds a minimum length schedule. Our objective is to minimize the total penalty. This problem has been generally considered to be intractable, and there are very few references on the topic. Search methods can be applied here with advantage. We use the notation introduced earlier with the following additions and modifications:

A well known theorem (see French [1982], Theorem 5.1, p. 67) states that in the absence of setup times, there is an optimal schedule in which jobs are sequenced in the same order on the two machines. This theorem remains valid when the setup times are separable, but not when they are sequence-dependent [Gupta and Darrow, 1985]. Since our study is confined to separable setup times, we can restrict ourselves to job sequences which are identical for the two machines.

Case I Penalty for a job equal to its completion time;

all initialization and cleanup times are zero.

Here g(N) is the sum of the finish times of the jobs in P. To determine h(N), order the processing times on M 1 of the m jobs in Q as follows:

ll;(t) 5 ll;(2) 5 · · · ~ li;{m) Order the processing ttmes on 1\.12 of the jobs in Q independently as follows:

£rQQ.f We have to show that X 5 h*(N) and Y 5 h*(N). The jobs in Q have been so ordered that the finish time on M 1 of the kth job in Q is the earliest possible; moreover, each of the jobs in Q must be processed on M2, and the processing on 1\.12 of the kth job in Q cannot begin until the processing on M 1 of the kth job is over. This proves that X 5 h*(N). Again, the processing of any job in Q cannot commence on 1\.12 before T3, so Y ~ h*(N). o

Sequencing problems of up to 12 jobs can be readily solved using a tree representation for the search graph, where a node corresponds to an ordered sequence of jobs. Such a formulation is essentially equivalent to a best-first branch and bound procedure. If we represent a node as an unordered subset of jobs we find that the search is faster but no longer order preserving, because when the jobs in P are permuted, not only g(N) but also T 2, and therefore T 3, get altered. This has the unusual consequence that with a graph representation, non­ optimal solutions are outputted even when the heuristics are admissible. It was found experimentally, however, that the solutions are close to optimal, so that the method can still be useful in practice. Experimental results are given in Table IV. Data was generated independently and randomly for the jobs on the two machines. It is interesting to observe that if we change the expressions for X and Y to

and set g(N) = 0 and h(N) = max { X, Y } , we get a minimum length schedule. This gives us an alternative to Johnson's algorithm, but the latter runs much faster.

Case IT Penalty for a job proportional to its completion time; separable setup times.

This generalizes Case I. Here Gi(fi) = eli· where the c/ s are the penalty coefficients as before. Let g(N) be the weighted sum of the finish times of the jobs in P. To compute h(N) order the processing times on M 1 of the m jobs in Q as follows:

~(lfCi(l} .$ ~(2fCi(2) .$ · · · .$ ~{mfci(m) Independently order the processing times on ~ of the jobs in Q:

Bj{lfcj{l) .$ Bj(2fcj{2) .$ ... .$ Bj(mfcj(m) Also, let D be the inner product, for the JObs in Q, of the m-element b-vector with the corresponding c-vector, where the hi's in the b-vector are arranged in non­ decreasing order while the ci's in the c-vector are arranged in non-increasing order. Now take

Let h(N) = max { X, Y } . Experimental results are given in Table V. Here, t<:>o, h(N) is a lower bound on h*(N). If we can redefine X and Y as follows

and set g(N) = 0 and h(N) = max { X, Y } , we get an alternative to Sule's [1982] method for finding a minimum length schedule when setup times are separable.

Case m Penalty for a job proportional to square of

its completion time; all initialization and cleanup times are zero.

The penalty functions are as in Case II of Section 2.2. Compute g(N) by summing, over the jobs in P, the squares of the finish times multiplied by the appropriate penalty coefficients. Order as in Case I the processing times on M 1 of the jobs in Q, and independently the processing times on ~ of the jobs in Q. Also order the corresponding penalty coefficients ci in non-increasing order:

We again have h(N) .$ h*(N). This case, as well as the next, can be generalized to powem other than two and to exponentials. Experimental results for the square penalty function are given in Table VI.

Penalty for a job proportional to square of its completion time; separable setup times.

Case IV

Order the processing times on M1 and ~ of the jobs in Q independently as follows:

Let the penalty coefficients be arranged in non-increasing order as in Case ill. Arrange the m-element b-vector in non-decreasing order, square each element, and let D be the inner product of the resulting vector with the corresponding m-element c-vector arranged as above.

Now let bQmin be the smallest bi in Q, and let

and take h(N) = max { X, Y, Z } Experimental results are given in Table VTI.

4 Conclusion

The major aim of this paper has been to open a new area of application for AI search methods, and to illustrate how good admissible heuristics can be derived for some practical problems. It has been shown that certain types of difficult but practical one-machine and two-machine job sequencing problems, for which efficient algorithms are not currently known, can be tackled in a reasonably satisfactory way by admissible search schemes. The work reported here can be extended in many directions. Even before any extension in scope is attempted, more intensive experimental testing needs to be undertaken of the admissible heuristics derived here on real life data gathered from job-shops and flow­ shops. The · following additional issues and questions could be taken up for closer examination and study:

1. Is it possible to modify the methods described here to solve sequencing problems involving sequence­ dependent setup times? In the one-machine case, this problem has some similarities with the travelling salesman problem. In the two-machine case, an optimal schedule can sequence jobs in different orders on the two machines; this greatly complicates the situation, and perhaps a totally new approach is necessary.
2. ii) When there are more than two machines in a flow-shop, an optimal schedule can order jobs in different orders on the machines. One way out of the difficulty is to restrict oneself to permutation schedules only [Lageweg et al., 1978], in which jobs are sequenced in the same order on all machines, but this has the obvious limitation that optimal schedules may not be realized. Can search methods be used to determine good permutation schedules ?
3. iii) In a real life problem, a job normally has a deadline by which the processing must be completed; no penalty accrues for a job that gets completed within its deadline. Is it possible to modify the heuristic estimate functions to take care of deadlines ? A positive answer will greatly increase the worth of~ approach.