Dual criteria preemptive open-shop problems with minimum makespan

Dual Criteria Preemptive Open-Shop Problems with Minimum Makespan George Vairaktarakis" Department of Industrial and Systems Engineering, University of Florida, Gainesville. Florida 3261 I Sartaj Sahni Department of Computer and Information Sciences, University of Florida, Gainesville. Florida 3261 1

In this article we present an algorithm for the minimum makespan preemptive open shop, which is superior to existing algorithms in both space and time requirements. We define the more complex generalized open shop and jle,xihle open shop and address the minimum makespan problem on these shops. We show how we can use the algorithm for the minimum makespan open shop to achieve load balancing in simple and generalized open shops without increasing the complexity of the algorithm. Load balancing dictates that the number of busy machines in each period is as even as possible. We also consider preventive maintenance issues in the open shop, and makespan retains its minimum value. In particular we consider the scenario where a machine can be maintained during any period that it happens to be idle. Also we consider the case that a maintenance schedule is prespecified. We show that this problem can be solved via a linear programming formulation that can also take into account release times for the jobs and ready times for the machines. Faster algorithms are presented for open shops with three machines or less. Q 1995 John Wiley & Sons, Inc.

1. INTRODUCHON A shop consists of a set M of machines each performing a particular task. We assume that there is a set J with 1 JI 2 I MI jobs, each consisting of at most I MI different tasks (the case I JI < I MI is symmetric). Task m ofjobj must be processed on machine m. The amount of time required by task m of j o b j is given by the nonnegative real number P,,~,. The matrix R = ( P , , ~ is ) called the requirements matrix of the open shop. A schedule of all tasks on the I MI machines is feasible if no task is processed by more than one machine at any time and no machine processes more than one job at any time. Finish time or makespan of a feasible schedule is the maximum among the completion times of the I MI machines in this schedule. Because there is no assumption on the number of times that task m of j o b j can resume service on machine m , an optimal schedule is in general preemptive. We want to find a schedule with minimum makespan among all feasible schedules. This

* Current address: College of Business Administration, Marquette Univ, Milwaukee, WI 53233. Naval Research Logistics, Vol. 42, pp. 103-12 I (1995) Copyright 0 1995 by John Wiley & Sons, Inc.

CCC 0894-069) 0. In each iteration, the current matching Z found in lines [ 51- [ 131 is used for p periods as computed by line [ 171. In the case that p is an integer we can view the operations of line [ 181 as deleting from B p copies of I . The intuition is similar when p is noninteger. In this case line [18] reduces the remaining processing time of all edges in Z by P.

+

2.1.

Generalized Open Shop

We will show how OMFT can be used to solve this problem. Suppose that in the simple open shop the number of periods that a j o b j must spend on machine m isp,,. Also suppose that in the generalized open shop there are s machines identical to m ,denoted by m ,, m2, ..., m,.The degree of each job in the bipartite multigraph corresponding to the simple open shop is equal to its degree in the bipartite multigraph for the generalized open shop. Therefore we only have to pay attention to how we can keep the maximum degree of the machines m ,, m2,. . . , m, at a minimum value. The total load on these machines is C,p,,. For integer preemption we assign the first d = TC,p,,/sl tasks on m l , assign the next d tasks on m2,and so on until all the tasks that require execution by m are exhausted. When noninteger preemption is allowed we assign a workload of d' = ( 2, pJ,/s) periods to each of the machines rn, ,m2,. . . , m,. Repeat the above procedure for all machines m. Then, in the resulting bipartite multigraph, the maximum degree among nodes that represent machines is as small as possible, which ensures that an application of OMFT will provide an optimal solution. The assignment of tasks to machines can be done in 0( Y I MI ) time because at each iteration of the procedure described above either all pJmperiods are assigned to some machine or the capacity d of some machine is reached. Therefore, the minimum makespan problem in a generalized open shop can be solved by OMFT.

+

2.2. Flexible Open Shop The case of the flexible open shop is a bit more complicated. For everyj E J there exists a set Sm,,of flexible machines that can perform, among other tasks, task m. We want to assign job j to the machines in S,,,, for a total of p,, periods. However, this assignment should be done in such a way that the maximum degree among nodes that represent machines of the corresponding bipartite multigraph is not unnecessarily large. Note that an optimal schedule would require at least D ,= max, C,p,,, but no more than D2 = max { D ,, max, CJp,,} periods. The procedure we propose applies a bisection search on the interval [D 1 D , 2 ] .Let D be a value in this interval. A feasible flow algorithm applied to the following network N determines whether there is an assignment of tasks to machines that leads to a schedule in D periods. To every edge (v,, v,) of N we associate a lower and an upper bound 1, and u,, respectively. A flow f = (A,) is called feasible if for every edge (v,, v,) of N we have that 1, sAJIu,, and for every node of Nexcept for s, t the total incoming flow equals

Vairaktarakis and Sahni:Open-Shop Scheduling

109

Upper bound

C,

pjm

Pjm Pjm

D

Figure 1. Network formulation of the flexible open shop.

the total outgoing flow. The network N is constructed as follows. For every p,, > 0 we introduce a vertex u,, with an incoming arc from jobjand outgoing arcs to all the machines in S,,,; see Figure 1 for more details, If such a flow exists andJ, is the flow from u,, to rn then one can construct a bipartite multigraph with maximum degree D by assigning jobj on machine m forA, periods. To find the minimum value of D , say D*, that results in a feasible flow, we have to apply a feasible flow algorithm at most log( Dz - Dl ) times. We observe that the above network is sparse. This is because in practice the number of different machines that can process a task ( j , m )is small. For instance, in a shop that consists of a few types of parallel identical machines, each type usually consists of no more than 5 to 10identical machines. Therefore, in most cases the number of arcs (u,,, m )is O ( r ) .Then the total number of arcs I A1 in the network is O(v ) and the number of vertices in the network is O(r ) . A feasible flow (if one exists) in a network with lower and upper bounds may be obtained using the construction of Even [ 51. He shows how to transform a network N with lower bounds into another network N without lower bounds. From the maximum flow in None can easily determine a feasible flow for N , when one exists. If N has v vertices and e edges 2 vertices and e 224 edges. The fastest known maximum flow algorithm then 15 has for sparse networks without lower bounds is due to Sleator [17] and has complexity 0( I V (1 A I log I V 1 ), where I V I is the number of vertices in the network. After transforming

+

+

110

Naval Research Logistics,Vol. 42 ( 1995)

our proposed network to one without lower bounds, the application of the maximum flow algorithm of Sleator has complexity 0( r2 log v ) . After D* is found, OMFT is applied on the corresponding bipartite multigraph to produce an optimal schedule.

3. LOAD BALANCING IN A PREEMPTIVE OPEN SHOP Having solved the O/pmtn/C,,, problem we can consider a more general problem related to it. Assume that each machine in the shop is operated by a technician. Assume that the number of these technicians, here called operators, is limited. We would like to find a minimum makespan schedule in which every machine is supervised by an operator when the number of operators is specified. As a special case of this problem, we will be able to find the minimum number of operators needed to process all the jobs in the shop in time C,,,; the minimum makespan found in Section 2. A solution to the latter problem minimizes the number of concurrently running machines. We refer to this problem as loud

balancing. Note that if C,,, is the minimum makespan and w is the sum of task times, then an average of w/Cmaxlmachines must be running per period. Therefore, at least r w/Cmaxl operators are necessary in order to run the shop. The following theorem due to Bondy and Murty [ 2, pp. 96- 1001 shows that r w / C,,,l operators are sufficient to run the shop. Recall that the minimum makespan preemptive open shop can be represented by a bipartite multigraph B .

THEOREM 2 (Bondy, Murty): Let B be a bipartite multigraph with maximum degree A and p a positive integer such that p 2 A. Then there exist p disjoint matchings M I ,M 2 , . . . ,Mp such that E ( B ) = UE=, Mk and L w / p l I1 Mkl Ir w / p l , where w = I E ( B )I . For p = C,,, we obtain the following corollary. COROLLARY 1: The minimum number of operators needed in a preemptive open shop to process all tasks in C,,, periods is r w /C,,,l . Next we provide an example that illustrates Theorem 2 followed by procedures that construct the matchings described in this theorem. Let R be the following requirements matrix:

where column i corresponds to period i, i = 1 , 2 , 3 , 4 .

Vairaktarakis and Sahni: Open-Shop Scheduling

mi

m2

m3

m4

111

m5

Figure 2. The multigraph B corresponding to our example.

The bipartite multigraph B for this instance is shown in Figure 2 and the matching decomposition induced by the above solution is

Without loss ofgenerality M I corresponds to period 1, M2 to period 2, et cetera. Then we have four machines running during the first period. However, w = 1 1 and by the previous corollary we can find a solution using only r w/Cmaxl= r 1 1 /41= 3 machines at any period. Let M ; = { (;2, m2 ). (;3 ~ 3 ( j l ),m ~4 ) 1 and M; = (.A, mI>, ,;( m d , ( J 4 , md 1. Now the decomposition of the edge set of B ( R )to M‘, , M 2 , M;, M4corresponds to a solution using only three machines running at any time, namely.

From the previous theorem we obtain the following corollary.

COROLLARY 2: The minimum number p (p 2 A ) of disjoint matchings M , , M 2 , . . . , M,, such that E ( B ) = U”,=, Mk and I MkI 5 c, isp = rw/cl. For every tentative makespan value p 2. A, Corollary 2 indicates the minimum possible number of concurrently running machines. Using this corollary one can construct the entire efficient frontier of makespan values versus the number of busy machines. For example, if only two operators are available, then the optimal makespan would be six periods, becauser11/61= 2(andr11/51= 3 ) . For the case p = C,,, = A we will present a construction where OMFT produces a load balanced minimum makespan schedule. To do this, we will modify the bipartite

Naval Research Logistics, Vol. 42 ( 1995)

112

multigraph corresponding to the minimum makespan problem in such a way that if the OMFT has as input this modified bipartite multigraph, it produces a minimum makespan schedule where no more than r w/ A1 machines are busy over any period (see Corollary 1 ). Assume, as in Theorem 1, that I JI 2 1 MI ( a symmetric construction works if I JI < 1 MI ), Let k = r w /Al. Given an instance of the OMFT problem, augment its corresponding bipartite multigraph B ( J , M ) (described in Section 2), to construct the bipartite multigraph B’(J, M ) as follows. Add 1 MI - k dummy jobs, say dl, d2,. . . , dlMI-k.Let m ,, m2,. . . , mi,1 < I MI, be the machines whose degree is less than A. Link d, with ml with a number of arcs so that the degree of m, becomes A. Then link d, with m2with a number of arcs so that either the degree of m2 becomes A or the degree of d, becomes A, whichever happens first. Continue to link machines whose degree is less than A with dummy jobs, until all dummy jobs have degree A. Because

none of the vertices of B’( J , M ) has degree greater than A. Now we will prove that if OMFT takes as input B’( J , M ) , it gives as output a minimum makespan with no more than k busy machines in any period. Indeed, in the proof of Theorem 1, we showed that if { M : } is the decomposition obtained by applying OMFT to B ’ ( J ,M ) , then M ; saturates all vertices that have maximum degree at the ith iteration of the algorithm. However, because all dummy jobs have degree A in B’(J, M ) , they will be of maximum degree in every iteration of the algorithm. Thus, each Mi saturates all dummy jobs. Now for 1 I i IA, let M ibe produced from Mi by dropping all dummy links. Because the number of dummy links is 1 MI - k , the cardinality of Mi does not exceed k = r w / A l , which means that there is no period with more than r w / A1 busy machines. Because the above construction is shown to work, we only need to compute the complexity of OMFT with input B’( J , M ) . The maximum degree A as well as the number of the machines are not affected by the construction. The size of the job set increases by no more than I MI but the asymptotic complexity of OMFT does not depend on I JI . Thus, we only need to see how the above construction affects the number of nonzero entries r , in the requirements matrix R. To see this, consider B‘(J, M ) and replace multiple edges by a single edge having weight equal to the number of multiple edges it replaces. It is easy to see that in the above construction, no machine is connected to more than two dummy jobs. Thus, the weighted version of B’( J , M ) has at most 2 ( I MI - k ) I 2 1 MI more entries, compared to the entries of the weighted version of B ( J , M ) . Hence, the number of nonzero entries r‘ of B’(J , M ) does not exceed r 2 I MI . But r 2 I MI (assuming that every machine is assigned at least 3r = 0( r ) . one task) and therefore Y’ I From the above we conclude that OMFT can be adapted to solve the minimum makespan load balanced preemptive open-shop problem without any complexity increase. We will refer to this variant of OMFT as VOMFT. Unfortunately, this approach does not seem to extend to the case where p > A. The reason is that some matchings do not saturate all jobs, and then the problem becomes to choose which job is left unsaturated by which matching. For this case we will describe an algorithm that transforms a matching decomposition M I , M 2 , . . ., M A of E( B ) into a

=;,

+

Vairaktarakis and Sahni:Open-Shop Scheduling

113

decomposition in p periods where at most r w / p l machines are busy in any period. The algorithm finds a matching I of cardinality greater than r w/pl . If no such matching exists, the current matching decomposition is optimal. The excess edges of Z are distributed to matchings of size less than r w/pl . This is achieved by repeated application of the next lemma. The algorithm that follows implements the construction described in the proof of the lemma. The correctness of the algorithm follows from the lemma and Theorem 2. LEMMA 1 (Bondy, Murty): Let I , N be matchings for B such that I ZI > I NI . There existdisjointmatchingsZ’,N’ofBsuchthat IZ’I = 111 - I , IN’I = IN1 + l , I ’ U N ‘ = I UN . PROOF: Consider the subgraph H = B[ I U N ] , induced by I U N in B . Because I , N are matchings, each vertex u in H is incident to at most one edge in Z and at most one edge in N hence 1 s degree( u ) I2. Therefore, each component of H is an even cycle or a path, with edges alternately in I , N . Because the edges of any cycle C in H alternate between I and N , the length of Cis even and 1 Z f l E( C)( = 1 N n E ( C ) ) . Then, I ZI > NI means that there exists a path, say P, that starts and ends with edges of 1. Let P = uoelul . . . ez,,+Iu2n+l. Then, set Z’= ( I - { e l ,e3,. . . , ezn+l } >U { e2,e4, . . . , e2,}, and N’ = ( N - { e2,e4,. . . , EZ, } 1 U { el, e3, . . . , e2n+l3 . By construction. I’ U N = I U N . I‘ is missing n 1 edges from I , but has n new edges. Thus 1 I’ I = I I I - 1. Similarly, IN‘I = (NI + 1. Because thesets { e l ,e3,.. . , e2n+l},{ e l ,e 4 , .. . , e2,} aredisjoint a n d I , Nare disjoint by hypothesis, Z’,N are disjoint by construction. It is left to prove now that Z’,N’ are matchings. Because I is a matching, Z - { e l , e3,. . . . e2n+1 } is a matching. N is a matching implies that so is { e2,e4, . . . , e2,). The vertices saturated by { e2,e4, . . . ,e2,,}are saturated by { el, e3,. . . ,ezn+l}, too. Therefore, I’ is a matching. Finally, note that oI , 02n+lare not saturated by Nand then a 0 similar argument shows that N’ is a matching. This proves the lemma.

+

The code that implements the algorithm to produce a minimum makespan schedule with no more than p busy machines in any period is given in the subroutine B-OMFT. Note that p = r w / p l > 9. B-OMFT Algorithm Given : y = rw/pl. A i ( M , , 1 M,I, a,))&, where { ( M I 6, i ) ] f = , are found by OMIT. BEGIN % place all matchings that use more than p machines in the linked list SURPLUS-LIST and all matchings that use less thanp machines in the linked list SLACK-LIST %

[I]Fork= I topdo [ 2 ] I f ( 1 MkI = p ) then Print ( M k ,&), else [ 31 If (I M k I i11)then insert ( M k , 1 Mk 1, &) to the top of SLACK-LIST [ 41 else insert (‘$.IIMk ,, ],ak)to the top of SURPLUS-LIST [ 51 If ( p - A > 0) then insert (S; 0, p - A ) to the top of SLACK-LIST ?G

Remove excess edges from the top element in SURPLUS-LIST to the top element in

Naval Research Logistics,Vol. 42 ( 1995)

114

SLACK-LIST % WHILE (SURPLUS-LIST f 0 )do begin [ 6 ] Let ( M - , s-, 6 - ) , ( M + , s+, 6 + ) be the top element of SLACK-LIST, SURPLUSLIST, respectively [7] Delete ( M - , s-, 6 - ) , ( M + ,s+, 6 ' ) from the top ofSLACKLIST, SURPLUSLIST respectively % Compute the number of periods for which the next matching is to be used 0 '9 [8] If(6' > 6 - ) then begin Insert(M+, s+,6' - 6-)to the topofSURPLUS-LIST 6 := 6 -

end else if ( 6 + < K ) then begin Insert(M-, s-, 6 - - 6 + ) to the topofSLACK-LIST 6:= 6+ end d, : = p - s - ; d2 : = s + - p % Augment M - and choose the next matching to be used among M - , M +70

[9] Apply Lemma 1 for min { d,, d z }times, starting with M + ,M - . Let M+,M- be the resulting matchings, respectively. If d, < d2then begin Print ( M - , 6 ) Insert ( M + ,s+ - d,, 6 ) to the top of SURPLUS-LIST end If ( d, = dz)then begin Print ( M + ,6 ) Print ( M - , 6 ) end If d, > dzthen begin Print(M+,6) Insert ( M - , s- d2,6) to the top of SLACK-LIST end END(ofWH1LE) ~

% Print the matchings left in SLACK-LIST and the number

of periods each is to be used 9%

[ 101repeat

Print ( M - , s-, 6 - ) ; the top element of SLACK-LIST Delete ( M - , s-, 6 - ) from the top of SLACK-LIST until (SLACK-LIST = fl) END

LEMMA 2: The complexity of B-OMFT is 0( r I MI 2 ) . PROOF: As noted in the algorithm, each element of the linked lists SLACLLIST and SURPLUS-LIST is a triplet ( M , s, 6), where M is a matching stored as a linked list, s is the cardinality of M , and 6 is the number of periods that A4 is to be used. The number of matchings generated by OMFT is r (min { r , A} if R is integer). Each matching may have no more than 1 MI edges and hence the total number of edges in all matchings does not exceed YI MI (min { r , A} 1 MI if R is integer). At each iteration of the WHILE loop at least one of these edges gets eliminated and therefore the number of iterations does not exceed r\ MI (min f I , A} I MI if R is integer). Thus we only need to find the time taken by each iteration. The time spent in lines [ 11- [ 41 by the algorithm is 0 ( p ) , because insertion in a linked list is an 0 ( 1 ) operation. Similarly, line [ 51 spends only O ( 1 ) time. Lines [6]-[ 81 take O ( 1 ) time because they

Vairaktarakis and Sahni: Open-Shop Scheduling

115

involve comparisons and insertions or deletions on linked lists (see Horowitz and Sahni [ 131). The block starting at line [ 91 takes time O( I M I ) . This is because finding the machines of M + U M - of degree 1 can be done by checking the 1 MI machines. Also, augmenting M - to saturate these machines takes time 0( I MI ). To see this, traverse the d , ( d2)paths of M +U M - that start from the degree one vertices of Mt . This traversal is done in no more than 2 I MI operations; an upper bound to the number ofedges ofM+U M - . Following the traversal, the augmentation involves at most 2 I MI insertions and deletions. Therefore, the time spent at the block starting at line [9] is indeed O( I M I ) . Multiplying by the number of iterations, we get an asymptotic complexity of O(Y J MI 2 ) . Note that B-OMFT applies for both integer and noninteger entries ofp,,. According to line [ 91, Lemma 1 is applied on the matchings M', M - to produce M+, M-. One of M+, M- has the desired cardinality p and it is used for 6 periods. If the requirements matrix R is an integer matrix, then 6 is integer otherwise 6 may take on a real value. Now we will address the load balancing problem in a generalized open shop. Suppose that p 2 max, C,p,,, is a target completion time. Let m l,m2,. . . ,m,be the set of machines . we that can process the tasks ( j , m )f o r j E J . The number of these tasks is 2, P , , ~ Then assign p unit tasks to m, ,p unit tasks to m 2 ,and so on until all tasks are exhausted. In case that p I max, 2,P , , ~there will be a machine having maximum degree in the resulting bipartite multigraph. Then VOMFT can be used to obtain a load balanced schedule on p periods. In the case that p > max, C, P , , ~no such machine exists and the generalized open shop reduces to a simple open shop because only one machine m is needed to process the tasks ( I , m ) j E J . This case is handled by B-OMFT. 4. PREVENTIVE MAINTENANCE IN A PREEMPTIVE OPEN SHOP

To prevent failure of the machines in an open shop is a very realistic problem faced by managers in industry. Assuming that management knows the number of periods needed to maintain each machine, the problem takes two forms. In the first case management wants to find a schedule that assigns as few maintenance technicians as possible over a desired planning horizon. In the second, management preassigns technicians to machines for certain periods depending on the availability of technicians and machines, and wishes to find a minimum makespan schedule. In this section we will formulate the first problem so that the algorithm presented in Section 2 can be applied to solve it. For the second problem we will give a linear programming formulation that solves the problem to optimality and allows for other constraints as well. 4.1.

Maintenance Schedule Undetermined

We will assume that each machine may require an arbitrary known number of periods to be maintained; that is, assume machine mirequires xi periods of maintenance, which can take place preemptively. Consider the bipartite graph B of Section 2 and the maximum degree A. It is clear that after maintenance is taken into account, the makespan will be no less than

116

Naval Research Logistics, Vol. 42 ( 1995)

a = m a x { A , max

{d(mj)+Xi}},

l s i s (MI

where d( mi) is the degree of the node that corresponds to machine mi in B . Augment the job set of the bipartite graph B one vertex at a time as follows. Scan the set of machines that need maintenance. Let ml be a machine in this list. Introduce a new node o1 corresponding to the first technician. Then, assign to ml , o1 a task with processing time x periods. Then consider the next machine that needs maintenance, say m2.Assign to m2,vI a task with processing time as many periods as possible so that the degree of o1 does not exceed Assign the leftover maintenance requirements, if any, to a new vertex v2 that represents the second technician. Continue in this fashion until all machines that need maintenance are considered. By construction, as few technicians are used as possible and no vertex in B has degree greater than 3.Therefore, by Theorem 1, there exists an optimal schedule in 2 periods and OMFT algorithm of Section 2 can construct it in polynomial time.

a.

4.2. Maintenance Schedule Determined

Now consider the problem where there is a certain period k when a machine m is preassigned a certain technician. Then the scheduler has no choice for machine m over period k , other than leaving the machine idle. To make the problem more realistic we add the following assumptions. Each job j has a release time r,, and each machine rn has a ready time a,,,. Also, assume that each machine is maintained during q intervals [ &, c f ] for i = I , 2, . . . , q , where sf, c i are the starting and completion time of the ith interval, respectively. Later, we will see that the problem just described can be solved in polynomial time in the case that the jobs are allowed to be preempted in noninteger intervals (e.g., a job is processed for 2.5 periods before being preempted). The case where jobs must be preempted in integer intervals is a special case of the timetable design problem, which is known to be strongly NP-complete (see Garey and Johnson [ 71, Even et al. [ 61). This problem is the following INSTANCE: Set H of work periods, set J of jobs, set M of machines, a subset A (j ) c H of available hours for each job j E J, a subset A ( m )c H of available hours for each rn E M , and for each task ( j , m ) E J X M , a nonnegative integer R(j , m ) of required work periods. QUESTION: Is there a timetable for completing all the tasks, that is, a functionf: J X M X H - { 0, l } (wheref( j , m , h ) = 1 means that task ( j , m ) is executed at period h ) such that I . f ( j , m , h ) = 1 only if h E A ( j ) n A( m ) , 2 . Foreach h € H a n d j € J t h e r e i s a t m o s t o n e m € M f o r w h i c h f ( j , m , h ) = I , 3. ForeachhEHandrnEMthereisatmostonejEJforwhichf( j , r n , h ) = 1, 4. For each task ( j ,m ) E J X Mthere are exactly R ( j , m ) values of h for whichf( j , m , h ) = I ?

=

Even et al. [ 61 have shown that the above problem is strongly NP-complete even if I HI 3, A ( j ) = H , V j E J , and R ( j , m ) E { 0, l} . This means that the problem is strongly

117

Vairaktarakis and Sahni: Open-Shop Scheduling

NP-complete even when all jobs are available for processing throughout the schedule and restrictions are placed only on the periods that the machines can operate. Because the minimum makespan problem with prespecified maintenance schedule places restrictions only on the periods that the machines can operate, the preemptive open-shop problem of minimizing makespan subject to prespecified maintenance schedule and integer preemptions is strongly NP-complete as well. Assuming that noninteger preemption is allowed, we will give a linear programming formulation to solve the problem optimally. Sort the ready times am,the release dates r,, the starting times &, the completion times ch of preassigned maintenance, and an upper bound UB for minimum makespan (although a tighter value for UB is not hard to find, a sufficiently large number suffices) in nondecreasing order. Let t o , t l , f 2 , . . . , tp be the distinct elements of the sorted list ( t o = 0 ) . Let also I k = tk - tk-I for k = 1, 2, . . . , p. A solution to the following linear model produces a schedule that minimizes makespan while satisfying the constraints, that is, a solution to O / r J ,a,, pmtn, maint 1C,,, . First, we introduce a dummy job that stands for idle time; this will be job n + 1. For every; = 1,2, . . . ,n 1, m = 1,2, . . . , I M I , k = 1, 2, . . . ,p , we will denote by X,,~~,Lthe portion of pJmthat will be processed in the interval [ t k , t k + ] 1. Then, the total processing time executed on machine m is C:=, p,,, and equals C, CLxlmk:

+

minimize C,,,,

subject to

n+l

2 xjmksIk,

k = 1, . . . , p ,

(2)

m = l , ...,\MI,

(3)

m = 1, . . . , [ M I ,

/=I P

C ~ j , ~ = p ~ , , , , j = 1 , ..., n, k-I

IMI

C x j n l k s I k , k = l , . . . ,p ,

j = 1 , . . . , n,

(4)

m=l

xjmk20,

xn+I,m,k = Ik,

iftk>Q

or & > a , ,

j = 1, . . . , n + 1, ( 6 )

if rn is maintained during [ t k - I ,tk].

(7)

Constraint ( 1 ) requires that no task is assigned after time C,,,. Constraint ( 2 ) ensures that no machine processes for more than I k time units over the interval ( t k - 1 , t k ) . Constraint ( 3 ) requires that machine rn processes all tasks of job j over the entire schedule. Inequality (4) states that no job can be processed more than Ik time units over the interval (tk-1, fk). Constraints ( 5 ) and ( 6 ) take care of release and ready times so that the resulting solution is feasible, and constraint ( 7 ) imposes the maintenance schedule. Once a solution for the above program is obtained, we can apply the algorithm of Section

NavalResearch Logistics, Vol. 42 ( 1995)

118

Figure 3. Network formulation for the special case.

2 for each subproblem in the interval [ t k P l , t k ], a total of p applications. The difference between the timetable design problem and the problem formulated in the linear program is that the later formulation produces timetables with noninteger preemption. It is interesting that this allowance alone reduces the complexity of the problem from strongly N P complete to polynomial. The complexity of the linear-programming-based procedure described above depends on the complexity of the linear program solver that we use. This means that the complexity of the proposed procedure will depend on the problem data; which is undesirable. Suppose that the requirements matrix R is integer. Motivated by the above observation and the fact that noninteger preemption may be undesirable, we discuss special cases that allow for a polynomial time procedure where the values assumed by Xjmk are integer. We will discuss in detail the case where I MI = 3; however, the procedure we suggest is readily applicable for the cases I MI I2. Special case: 1 MI = 3. Suppose that the open shop consists of three machines. Then we can have 0, 1, 2, or 3 machines available over any period. If all three machines are scheduled for maintenance during an interval [ t k - ] , t k ] we can disregard this interval from our schedule and consider the shop idle. Let pi denote the number of periods that machine rn,is the only available machine, i = 1,2,3. If we exclude p i unit tasks of the form ( j , m i ) i = 1 , 2 , 3 , from B , in such a way that the residual graph, say B‘, has as small a maximum degree as possible, then we can construct an optimal schedule as follows: Apply OMlT on B’, Schedule thep, unit tasks of the form ( j , m, ) during the piperiods that rn, is the only available machine.

The resulting schedule has to be optimal because the maximum degree of B’ is minimum by construction. To construct B’ we do a bisection search on A. Given a value 0 IA, IA, we find a feasible flow for the network problem described in Figure 3.

Vairaktarakis and Sahni: Open-Shop Scheduling

119

If a feasible flow exists, then the total flow passing through m,corresponds to tasks that are assigned for execution when rn, is the only available machine. The complexity of the feasible flow algorithm is O(1 V 1 3 , (see Karzanov [ 14]), where I V 1 = n + 3 and hence this bound becomes 0( n3).To find the minimum for which a feasible flow exists, we repeat the feasible flow algorithm no more than log A times. Thus, to find a residual bipartite graph with as small maximum degree as possible takes time O ( n3 log A ) . By construction of the network, the residual graph has maximum degree not exceeding A,, in which case OMIT can be applied to complete the solution in polynomial time. To evaluate the quality of solutions provided by the above linear programming formulation for the case where 1 MI 2 4, our experiment on an open shop consisted of 12 jobs and six machines. This moderate-size instance already involves a few thousand variables. We noted that the linear program produced an integer solution 49 out of the 50 runs. This means that our linear program is an excellent heuristic for the maintenance problem with integer preemption. Note that if we require integer values for all the variables of the linear program, then the corresponding integer program (which would force integer preemption) would have a prohibitively large number of integer variables. The experiment was carried out on a VAXjVMS computer using the LP module of the package GAMS.

4.2.I .

Worst-CaseAnalysis

In this subsection we will propose a reasonable and commonly used maintenance scenario, and we will find an upper bound for the ratio of the makespan of the proposed scenario to the makespan of an optimal solution with respect to any other possible maintenance scenario. Specifically, consider an open shop where r technicians are available, 1 I r I I MI. Suppose that the manufacturer of the machines of the open shop suggests that each machine is maintained for a portion of time every production cycle. In particular, because an open shop can complete all the tasks in A periods, we will assume that each machine must be maintained for r( x/ 100)A1 periods of every r ( x / 100)A1 + A periods. If p := rx/ 1001, then the maintenance time allocated on each machine is p A periods. Consider the following maintenance scenario. Process all tasks in the time interval [O. A] where A is the makespan obtained by OMFT. Then. maintain machines m, , . . . , m, throughout the interval [A, A PA]. Continue by assigning the operators on the machines m,,,, . . . , m2,for the next p A periods and so on. Clearly, the makespan with respect to this scenario is the time that the last machine is maintained, which equals A + p A r 1 MI / ~ 1 . We will refer to the scenario just described as S . Suppose a maintenance scenario S’ is given. Then define the quantities:

+

to,,, = optimal makespan with respect to maintenance scenario S’ t = optimal makespan when maintenance of each machine starts after the

completion time of the last

task on this machine.

We would like to find an upper bound for the ratio tit,,,. Note that either there exists a machine m such that 2, P , ,=~ A, or there exists some j o b j for which C, P , , ~= A. Straightforward calculations of the makespan values t and to, in each of the two cases yields the following theorem.

120

Naval Research Logistics, Vol. 42 ( 1995)

THEOREM 3: If the makespan of OMFT is attained by a machine, then

and the bound is tight. Else,

and the bound is also tight. 5. CONCLUSIONS

In this research we first refined an existing algorithm for the minimum makespan preemptive open-shop problem, by eliminating dummy tasks. As a result the algorithm has less space requirements and runs faster. Then we showed how one can use our algorithm to find schedules that achieve load balancing. Then we considered maintenance issues on the open shop. In the case that a machine can be maintained during any period that happens to be idle, the algorithm OMFT can be employed. In the case that the maintenance schedule is provided by an external source, then the difficulty of the problems depends on whether noninteger preemption is allowed or not. We saw that the problem is strongly NP-complete in the case that integer preemption is required. However, we were able to solve the problem in polynomial time when the shop has 1, 2, or 3 machines. The case where noninteger preemption is allowed is solved by a linear program that also accounts for release times for the jobs and ready times for the machines. We performed some experiments that showed that the solution obtained by the linear program, in most cases, does not produce noninteger preemption. Then, we conducted a worst-case analysis of an optimal schedule versus a scenario very often used in practice.

ACKNOWLEDGMENT The research of Sartaj Sahni was supported in part by the National Science Foundation under grant MIP 9 1-03379.

REFERENCES [ 1 ] Achugbue, J.O. and Chin, F.Y., “Scheduling the Open Shop to Minimize Mean Flow Time,” S A M Journal on Computing, 9,306-31 1 ( 1982). [2] Bondy, J.A., and Murty, U.S.R. Graph Theory with Applications, North Holland, New York, 1976. [ 31 Cho, Y., and Sahni, S., “Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops,” Operations Research, 29,5 11-522 ( 1981). [ 41 Dror, M., “Openshop Scheduling with Machine Dependent Processing Times,” Discrete AppliedMathematics, 39, 197-205 ( 1992). [ 51 Even, S., Algorithmic Cornbinatorics,Macmillan, New York, 1973, Chap. 10. [6] Even, S., Itai, A., and Shamir, A., “On the Complexity of Timetable and Multicommodity Flow Problems,” SZAM Journal on Computing5,69 1-703 ( 1976).

Vairaktarakis and Sahni: Open-Shop Scheduling

121

Garey, M.R., and Johnson, D.S. Computers and Intractability, W.H. Freeman, San Francisco, 1979. Gonzalez, T., “A Note on Open Shop Preemptive Schedules.” IEEE Transactions on Computers. C-28,782-786 ( 1979). Gonzalez, T., “Unit Execution Time Shop Problems,” Mathematics of Operations Research, 7,57-66 (1982). Gonzalez, T., and Sahni, S., “Open Shop Scheduling to Minimize Finish Time. Journal qfthe Associationfor Computing Machinery, 23( 4 ) , 665-679 ( 1976). Gotlieb, C.C., “The construction of class-teacher time-tables,” in Proceedings ufthe 1.F.Y.P. Congress 62, Munich, Vol. 15, pp. 11, 1963. Graham, R.L., Lawler, E.L., Lenstra, J.K., and Rinnooy Kan, A.H.G., “Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey,” Annals of Discrete Mathematics, 5,287-326 (1979). Horowitz, E., and Sahni, S., Fundamentals of Data Structures, Computer Science Press, Los Angeles, 1976. Karzanov, A.V. “Determining the Maximal How in a Network by the Method of Preflows,” Soviet Mathematics Doklady, 15,434-437 ( 1974). Lawler, E., Lenstra, J.K., and Rinnooy Kan, A.H.G., “Minimizing Maximum Lateness in a Two-Machine Open Shop,” Mathematics of Operations Research, 6, 153- 158 ( 1981 ). Liu, C.Y., and Bulfin, R.L., “On the Complexity of Preemptive Open-Shop Problems,” Operations Research Letters, 471-14 ( 1985). Sleator, D.D. unpublished Ph.D. dissertation, Stanford University, 1980.

Manuscript received March 29, 1993 Revised manuscript received June 15, 1994 Accepted September 5, 1994