On scheduling parallel machines with a partially shared resource

UNIVERSITY OF

ILLINOIS LIHRARY

AT URBANA-C; CAMPAIGN

BOOKSTACKS

Digitized by the Internet Archive

in 2012 with funding from

University of Illinois Urbana-Champaign

http://www.archive.org/details/onschedulingpara160rama

Faculty Working Paper 93-0160

m 6385

1993:160 COPY 2

On Scheduling Parallel Machines
with a Partially Shared Resource

™ ?Y Of T

MOV 2 1 ;

Ul

LiHjA,v,.,HAiVlpM,uN

Narayan Raman

Department of Business Administration

University of Illinois

Bureau of Economic and Business Research

College of Commerce and Business Administration

University of Illinois at Urbana-Champaign

BEBR

FACULTY WORKING PAPER NO. 93-0160

College of Commerce and Business Administration

University of Illinois at Urbana-Champaign

September 1993

On Scheduling Parallel Machines
with a Partially Shared Resource

Narayan Raman
Department of Business Administration

On Scheduling Parallel Machines
with a Partially Shared Resource

Narayan Raman

Department of Business Administration

University of Illinois at Urbana-Champaign

Champaign, Illinois 61820

September 1993

ABSTRACT

This paper deals with the computational complexity of several scheduling problems arising in a class
of parallel machine systems with a partially shared resource. The manufacturing shop comprises one
operator and M identical machines operating in parallel. Each job in set J needs to be scheduled
on one of the machines. Before a job can be processed on any machine, it needs to be setup on
that machine. During its setup, a job requires both the machine and the operator; however, only
the machine is required for processing the job. We show that, for this system, optimizing many of
the well-known scheduling measures results in NP-complete problems even when M = 2.

1 Introduction

In this paper, we consider scheduling problems arising in a system comprising one operator and
M identical machines operating in parallel. Each of the N jobs in set J needs to be scheduled on
one of the machines. Before a job can be processed on any machine, it has to be setup on that
machine. During its setup, a job requires both the machine and the operator; however, only the
machine is required for processing the job. All jobs are available at time zero. No preemption is
allowed during setup or processing, or between setup and processing.

This class of resource-constrained scheduling problems is gaining increasing importance because of
its relevance in flexible manufacturing systems (FMSs), as well as in cellular manufacture. In an
FMS, a robot serves the role of the operator that is shared among several pieces of equipment for
the purpose of part setups and tool changes. Similarly, "one worker multiple machine systems"
(Krajewski and Ritzman 1993) form an integral part of many group technology cells. The well-
known case on Fabritek Corporation (Sasser et al. 1982) highlights the importance of minimizing
operator-machine interference in these systems.

This paper deals with the computational complexity of the problems arising in this class of schedul-
ing systems that have a partially shared resource. Note that the maximum completion time mini-
mization problem for identical parallel machines is known to be NP-complete even in the absence of
resource constraints. We show that this problem is rendered strongly NP-complete in the presence
of a partially shared resource. Furthermore, the total completion time minimization problem that
is solvable in polynomial time without resource constraints becomes NP-complete for this class
of systems. We show that optimizing many of the other well-known scheduling measures results
in NP-complete problems as well, and that all complexity results hold even for two-machine sys-
tems. [The reader is referred to Blazewicz et al. 1986 for a comprehensive discussion of the results
currently available on the complexity of parallel machine scheduling problems.]

2 Problem Formulation

Let 5j, pj, dj, and Wj, respectively, denote the setup time, processing time, due date and weight of
job j, j £ J . Let Cj denote the completion time of job j in a schedule for any j £ J ■ Then, the
general system of constraints satisfied by any feasible schedule is given by

M

Y^ Xjm = 1, Vj

m=l

Uijm •Eim%jm ~ "j VI, J, 771

C, - C, - sj - Pi + p,- 1 1 - 5^ y«jm +1(1- <^) > 0, Vi,,

V m=l /

M

Ct - Cj - 5, ~ Pi +Pj ( 1 ~ J] Jfcjm J + L6ij > 0, Vi, j

m + 1

Cj > 0, Vj; Xjm,yijm,Sij e {0,1}, V»',j,

m

(1)
(2)
(3)

(4)

(5)

(6)

where

■^im —

Vi

jm

bin —

1, if product i is produced on machine m

0, otherwise.

1, if jobs i and j are both produced on machine m

0, otherwise

1, if i precedes j on the operator
0, otherwise

and L is a large number. (1) insures that each job is assigned to exactly one machine. (2) defines
Vijmi while (3) requires that any job can finish only when its setup and processing is completed.
(4) and (5) together insure that each machine, as well as the operator, works on at most one job
at a time. Finally, (6) specifies the nature of the variables.

For this system of schedules, we consider the following problems: i) CMAX: minimizing maximum
completion time Cmax = ma,Xj{Cj}; ii) TCT: minimizing total completion time Ctot = J2jCj,
and WCT: minimizing total weighted completion time Cw = J2j w]Cy, iii) LMAX: minimiz-
ing maximum lateness Lmax = maxj {Cj - d3}; iv) TTD: minimizing total tardiness Ttot =
Y^j max(0, Cj - dj), and WTD: minimizing total weighted tardiness Tw = Yj wj max(0,Cj - dj);
and v) TER: minimizing total earliness Etot — XZj max(0, rfj — Cj) subject to C, < d{, Vi, and
WER: minimizing total weighted earliness Ew = }Tj u>j max(0, dj — C3) subject to C{ < d{, Vi.

3 NP-Completeness Proofs

Because all complexity results hold even for two-machine systems, we restrict ourselves throughout
this section to such systems only.

Theorem 1. CMAX is NP-complete in the strong sense.

Proof: CMAX clearly lies in NP. We show that the 3-PARTITION problem which is known to
be NP-complete in the strong sense (Garey and Johnson 1979) is reducible to CMAX. Consider an
arbitrary instance of 3-PARTITION given by a set Q of 3q elements of size at for each i £ Q, and
a positive integer B such that i) B/4 < a, < B/2, Vi 6 Q, and ii) J2ieQai — QB- The recognition
problem is stated as: Is there a partition of Q into q disjoint subsets (Q\, Q.2-,- ■ -,Qq) such that
HieQj a« = Bi for 1 < 3 < <7?

We construct the equivalent instance of CMAX with three types of jobs. Let J{ denote the set
of jobs of type i, i = 1,2,3, and let Jx = {l,...,3g}, \J2\ = |J3| = q. Define P = B(q + 1) + 1.
Assign job parameters as follows:

Si = 0, pt = at, i = 1,. ..,3<?,

Si = P - B, pi = 0, i e J2, and

Si = B, Pi = P - B, i e J3.

Given an instance of 3-PARTITION, this instance of CMAX can be constructed in polynomial
time. We show that for this instance, the maximum completion time (makespan) Cmax < qP, if
and only if 3-PARTITION has a solution.

First suppose that 3-PARTITION has a solution. The required solution for CMAX is constructed
as follows. Sequence type 3 and type 2 jobs on the operator such that type 3 jobs are in positions
1,3, . . . , 2q — 1, and type 2 jobs are in positions 2, 4, ... , 2q. Assign all type 3 jobs to machine M2,
and type 2 jobs to machine Ml as shown in Figure 1.

INSERT FIGURE 1 HERE

Note that all type 2 and type 3 jobs are completed by time qP. Furthermore, Ml has q slots of idle
time, each of duration B. Clearly, if 3-PARTITION has a solution, then J\ can be partitioned into

q subsets, each with a total processing time of B. These subsets are inserted into the idle times
slots on machine Ml to yield the desired solution.

Next, we show that if Cmax < qP, then 3- PARTITION has a solution. First, note that qP is a lower
bound on Cmax because the total work to be done on both machines is YlieJi ai + 2g(P - B) + qB =
2qP. Hence, Cmax = qP, and there is no idle time on either machine through the makespan. Also,
note that the total setup time is q(P - B) + qB = qP\ therefore, the operator has no idle time
either.

Lemma 1. If Cmax < qP, then the operator must process type 3 jobs in positions 1,3, . . .,2q — 1,
and type 2 jobs in positions 2,4,..., 2q.

Proof: Since the operator is busy throughout the duration of the makespan qP, the job set up
last by the operator must be of type 2 because it has zero processing time. If the job in position
2q — 1 is not of type 3, then two type 2 jobs are processed together. This implies that the setup
of the last type 3 job must be completed by time qP — 2{P — B), and its processing should be
completed by time

r = qP -2{P - B) + (P- B) = qP-(P - B).

By r, the two machines should also finish (q — 1) type 2 jobs. Hence, the total work done by both
machines till time r is

W = qP + (q- l)(P- B) = 2Bq2 + 2q- 1.

But the total capacity available on these two machines until r is

CAP = 2t = 2P{q - 1) + 2B = 2Bq2 + 2{q - 1) < W

which is infeasible. Hence, the job in position 2^—1 must be of type 3, and it must be taken up
for setup at time qP — P. This implies that the remaining (q - 1) jobs of type 2 and type 3 each
must have completed setup by time qP - P - P{q - 1). Setting q *— q— 1, and repeating the above
arguments recursively completes the proof of the lemma. □

It follows from the above proof that the type 2 job in position 2i - 1 and the type 3 job in position
2i, i = L,...,4, must be run on different machines. As shown in Figure 1, this leaves q idle time
slots of length B each, and for all type 1 jobs to be completed by qP, it must be possible to complete

processing them during these slots. But this implies that J\ can be partitioned into q subsets of
size B each, which in turn implies that 3-PARTITION has a solution. □

Corollary 1. LMAX is NP-complete in the strong sense.

Proof: In the instance of CMAX generated above, assign d{ = 0, i 6 J\ U J2 U Jz- Then, for
this instance, Lmax < qP, if and only if Cmax < qP- n

Theorem 2. TCT is NP-complete.

Proof: TCT clearly lies in NP. We show that the SUBSET SUM problem that is known to be
NP-complete (Garey and Johnson 1979) is reducible to TCT. Consider an arbitrary instance of
SUBSET SUM defined by a positive integer B' and a set Q' of q elements of (integer) size a', i £ Q'.
The recognition problem is stated as: Is there a subset Q'0 C Q' such that J2ieQ' a'i ~ B't

Let a,b > 1 be arbitrary integers such that a is not an integer multiple of b. Given the original
instance of SUBSET SUM, we generate an equivalent instance by defining a set Q of q elements
of size a; = ba\, i = 1, . . . , q, as well as an integer B = bB' . This transformation can be done in
polynomial time; clearly, there exists a subset Q'0 C Q' for the original instance with the property
that 52iqQi a'i = B' if and only if there is a subset Qo C Q such that YlieQo a» = ^ ^or tne m°dified
problem. Note that this transformation insures that

Remark 1. There exists no subset Q\ C Q with the property that J2ieQi a« = kb — a for any
integer k.

In the rest of the proof, we restrict ourselves to the modified version of SUBSET SUM. Let amax =
maxt€<2 {ai}i an(i H2ieQai = A. We construct the corresponding instance of TCT by considering
jobs /, J and K, as well as job sets £ = {l,...,<jr}, T — {q + 1,. ..,q + /}, Q and H such that
|£?| = g, and \H\ = h with the following parameters.

Job

Processing Time

Setup Time

I

Pi = 0

si — a

J

pj = a

sj = l

K

PK = 0

sK = ax

je£

Pj = 7T! + dj

Sj=0

jef

Pj = ffl

Sj = 0

jeQ

Pj = *2

Sj = 0

jen

Pj = 0

sj = a2

where

/ = q(q+ l)amax

jt, = (f+l)(B + a) + f

t = {q + f)*i + A + a

Do = \{q + f)(q + f + 1)tti + (q + 1)^

9 = qwx + B + a

°~i = q*\ + B - 1

Dx = ax + 9

g = D0 + Dx

*2 = g{r+ 1)

D2 = gr+ \g{g+ 1)tt2

h = D0 + Dx + D2

a2 = h(9+l)

D = a2+ ]h{h + l)a2.

Given an instance of SUBSET SUM, this instance of TCT can be constructed in polynomial time.
We show that for this instance, the total completion time Ctot < D, if and only if SUBSET SUM
has a solution. Note that Remark 1 implies that

Remark 2. There exists no subset S C £ U T , with the property that J2ieS ai = kb — a for any
integer k.

If SUBSET SUM has a solution, then there must exist a subset So C £ corresponding to Qq such
that YIjzEq Pj — ^^l + B, where e0 = |£o|- Let To = {q + j\j £ £ \ £o} Q ? • The desired schedule
for TCT is constructed as shown in Figure 2.

INSERT FIGURE 2 HERE

Note that jobs in set Q start being processed on machine Ml at time

Yl Pi + si = (<! + /Ki + A + a = r,

and jobs in set H start being set up on machine M2 at time

SK + sj + PJ = 9*-i + B - 1 + (1 + a) = 0.

Also note that

C[ = qit\ + B + a = $

<i+f q

J2 CJ - S (j'Ti + B + a) + J2jamax

je{^\^o}u{£\€0} 3=q+l J=l

9 1

Hence, the sum of completion times of all jobs on machine Ml is

c(i) = £ cJ + cI+ £ c. + ^c,

je^oufo j€{*Vb}u{£\£o} ;'€G

< 2(9 + ^9 + f + ^ + 9(? + 1)a™* + ?7ri + B + G + ^B + a) + gT + 29{9 + 1)?r2

= 2^ + f^q + / + i)^ + (9 + l)*i + 2r + ^ + 1)?r2

= D0 + D2. (7)

And the sum of completion times of all jobs on machine M2 is

C(2) = Ck + Cj+J2Cj

h

= trj + 0 + M + _-/»(/» + l)<r2

= l?1 + M + |fc(fc+l)<ra. (8)

Hence,

Ctot = C(l) + C(2) < D0 + D1 + D2 + M + ±h(h + l)<T2

= h(9 + 1) + h(h + l)a2
= D

as required. Next we show that if Ctot < D, then SUBSET SUM must have a solution.

Lemma 2. C% > Cj, for any i 6 H, j (£ H. Furthermore, the processing of jobs in Ji must start
at 9.

Proof: If there is a job j £ H that is completed after some job in H, then Ctot > C} 4- YLizn Ci >
&2 + \h(h+ 1)<72 = D which contradicts the original assumption. If the processing of "H starts later
than 0, then

Ctot > Y, C^ w + !) + \h(h + l) = D

which is again a contradiction. But the total setup time required on all jobs not in Ti equals

si + sj + sK = a + 1 + (q^ +B-l) = d.

Because these jobs precede all jobs in W, the latter cannot start before 9 either. Hence, the
processing of jobs in H must start at 9. □

Two results follow from the above proof.

Corollary 2. There is no idle time on the operator through the makespan of the problem.

Corollary 3. Jobs in H are processed without any intervening idle time.

Consequently, we have

£ Cj < D - £ Cj = D - ih6 + \h{h + l)<x2 j = h (9)

From Lemma 2, we assume without loss of generality that all jobs in H are processed on the same
machine; let this machine be M2.

Lemma 3. Cx > C3, for any i 6 Q, j ^ Q U H. Furthermore, the processing of jobs in Q must
start at r.

Proof: The proof is similar to that of Lemma 2 above. If there is a job j £ Q UH that finishes
after some job in Q, then Y,i&i Q > Cj + E*€0 C* ^ ""a + \s(9 + ^2 = 9^ + g + \g{g + 1)tt2 =
Dq + D\ + D2 = h which contradicts (9). If the processing of Q starts later than r, then

E<?i > £<?; > ^(r + 0 + \d(g+ IK2 = fc

which again contradicts (9). But the total processing and setup times required on all jobs not in
Gun is

E Pj + SK + si + 8j+pj = (q+f)ici + A + (qT1+B-l) + a + l + a = T + 9. (10)

From Lemma 2, it follows that jobs in Q cannot start processing before r either. Hence, the
processing of jobs in Q must start at r. □

We make three observations here. First from Lemmas 2 and 3, and (10), it follows that

Remark 3. Jobs I, J , and K as well as jobs in S and T must be completed without any
intervening idle time.

Second, because r > 9, Q and H must be processed on different machines, i.e., Q must be processed
on machine Ml. Finally, from the proof of Lemma 3, it follows that

Corollary 4. Jobs in Q are processed without any intervening idle time.

Consequently, from (9), we have

E C^h~ E Cj = h-tgT + ±g(g+l)T2\=g. (11)

Nest we establish the relative order of jobs /, J and K.
Lemma 4. J cannot be the first job taken up for setup.

Proof: From Corollary 2, if J is taken up first by the operator on (say) Ml, then the next setup
must take place after one time unit on M2 because of the subsequent processing required on J .
This induces an idle time of one time unit on M2 because no job from £ U T U {/} U {A'} can be
processed during this interval, and a contradiction of Remark 3 results. □

Lemma 5. /, J and K must complete processing by 6.

Proof: From Lemma 2, the setup of jobs /, J and K must be completed by 9. The only schedule
in which their processing will not complete by 9 is one in which J is taken up last among these
three jobs for setup as depicted in Figure 3.

INSERT FIGURE 3 HERE

However, in this case, the gap r — (9 + a) must be filled by jobs from £ U T to prevent any idle
time. Therefore, there must exist a subset S C £ U T such that

Y,Pj = r-(8 + a)
3€S

= {q + f)xi+ A + a-(qiri + B + a) - a

= (M + A - B) - o.

But this contradicts Remark 2 since {fir\ + A — B) is an integer multiple of 6. Hence, this schedule
is not feasible and the proof is complete. D

From Lemmas 4 and 5, it follows that the setup of / and the processing of J must occur in parallel,
and the setup sequence followed by the operator must be A' - J - I in the interval [0,0]. This
implies that the setup of / must start at 9 — a, and C/ = Cj = 6. From (11), it follows that

Cl+ E Ci ^ 9-Ck-Cj

= DQ + Dx-ax-6

= Do (12)

Lemma 6. Exactly q jobs from £ U T must be completed by time 9 — a.

Proof: Let n be the number of jobs from £ UJ that are completed by 9 - a. If 0 < n < q — 1,
then

n q+f

= \iq + f)(q + / + IKi +0 + (q + f~ n)(9 - titt! )
= Do - (q + lfri + (q + f - n){0 - n*!) + 9
> D0

10

which contradicts (12). lfq+l<n<q + f, then

n q+f

ci+ zZ cj - I^M + Wi + aH L (M + o)

jGfUJF j = l J=n+1

= 2^ + /)(9 + / + IKi + nTT! + a + (g + / - n)o

= D0 + ir 1 {re - q - 1} + a + (q + f - n)a
> D0

which again contradicts ( 12) and the proof is complete. □

From the processing times of jobs in sets Z and T , it follows that there must be a subset So Q £Uf
such that |<5o| = q, and

q-K\ + 2_. a3 : ~ 0 ~ a

j€50

or

E ai = B-

j€50

But this implies that SUBSET SUM has a solution and the proof is complete. □

Theorem 3. TTD is NP-complete.

Proof: We reduce the single machine total tardiness problem (SMT) that is known to be NP-
complete (Du and Leung 1990) to TTD. Let the instance of SMT be given by a set of n jobs
with processing times and due dates of 7r, and £,, i = l,...,n, respectively. Let cx denote the
completion time of job i, i = l,...,n in any schedule. The recognition problem is stated as: Is
there a permutation of these n jobs such that J2]=i max(0,c,- — Si) < Z1

Let 7 = n(Z + 1) + JZJLi max(#,-,7r,-). The equivalent instance of TTD comprises n + Z + 1 jobs
with the following parameters:

s, = 0, pt = 7r,-, d{ = 6i, i=l,..., n, and

sn+i = 7> Pn+i = 0, dn+i : = £7, * = 1,...,Z+1.

We show that for this instance, Ttot < Z if and only if SMT has a solution. If SMT has a solution,
then the corresponding schedule for TTD is obtained by sequencing jobs n + 1 through re + Z + 1
on M2 in the order of their indexes. Jobs 1 through n are scheduled on Ml such that Cm = Cm,
i = 1, . . . , re to yield the required solution.

11

If TTD has a solution, then in a manner similar to the proof of Lemma 2, it can be established that
i) C{ > C-j, for any i £ {n+l,...,n + Z + l}, and j £ {1, . . . ,n}, and ii) jobs in{n + l,...,n + Z + l}
must be setup in the order of their indexes, starting at time zero and without any intervening idle
time. Without any loss of generality, we may assume that jobs in {n + 1, . . . , to ■+■ Z + 1} are setup
on machine M2. It is easy to see that all these jobs are completed exactly on time, and therefore,
incur no tardiness. But this implies that £j=1 max(0, C{ - d,-) < Z and SMT has a solution. □

Theorem 4. TER is NP-complete.

Proof: We show that that the single machine total earliness problem (SER) that is known to be
NP-complete (Chand and Schneeberger 1986) can be reduced to TER. Let the instance of SER be
given by a set of n jobs with processing times and due dates of 7r, and £,-, i = 1, . . . , to, respectively.
Let c, denote the completion time of job i, i = 1, . . . , to in any schedule. The recognition problem is
stated as: Is there a permutation of these n jobs such that c; < <$,, Vi, and £Ij=i max(0, St — ct) < Z1

The equivalent instance of TER comprises n + 1 jobs with the following parameters:
st = 0, pi = 7Tj, d{ = S{, i = 1, . . . , to, and

sn+1 = dn+i = YX=i di + !> Pn+i = 0-

Given these parameters, note that Ct < dt, i = 1, . . . , n + 1, is insured only if job (n+ 1) is scheduled
on (say) machine M2 starting at time zero, and the other n jobs are scheduled on machine Ml. It
is easy to see that Etot < Z for this instance of TER if and only if SMT has a solution. □

Because TCT, TTD, and TER are special cases of WCT, WTD, and WER, respectively, it
follows that

Corollary 5. WCT, WTD, and WER are NP-complete.

12

References

1. Blazewicz, J., W. Cellary, R. Slowanski and J. Weglarz (1986), Scheduling Under Resource
Constraints - Deterministic Models, J. C. Baltzer AG, Basel, Switzerland.

2. Chand, S. and H. Schneeberger (1986), "A Note on the Single Machine Scheduling Prob-
lem with Minimum Weighted Completion Time and Maximum Allowable Tardiness," Naval
Research Logistics Quarterly, Vol. 33, 551-557.

3. Du, Z. and J. Y.-T. Leung (1990), "Minimizing Total Tardiness on One-Machine is NP-Hard,"
Mathematics of Operations Research, Vol. 15, 483-495.

4. Garey, M. R. and D. S. Johnson (1979), Computers and Intractability: A Guide to the Theory
of NP- Completeness, W. H. Freeman and Company, New York, NY.

5. Krajewski, L. J. and L. P. Ritzman (1993), Operations Management - Strategy and Analysis,
Addison- Wesley Publishing Company, New York, NY.

6. Sasser, W. E., K. B. Clark, D. A. Garvin, M. B. W. Graham, R. Jaikumar and D. H. Maister
(1982), Cases in Operations Management: Analysis and Action, Irwin, Homewood, IL.

13

Ml
M2

Oper-
ator

B

P

P+B

2P (a-

np

aP

Tl

T2

Tl

T2

Tl

T2

1

3

1

3

i

(q-1)P
+ B

T3

T2

t 3

T2

i~3

T2

Ti represents a job of type i, i = 1,2,3. The shaded area denotes the setup of a type 3 job.

Figure 1 - Proof of Theorem 1

14

Ml

M2

e-

- a

i

76

So

I

r\Fo

e\£o

Q

K

1

J

H

Oper-
ator

n

The shaded area denotes the setup of job J.

Figure 2 - Proof of Theorem 2

Ml

M2

9 + a

r

I

J

Q

H

Figure 3 - Proof of Lemma 5

15

HECKMAN

BINDERY INC.

JUN95

Bound -To -Picas.

f N. MANCHESTER
INDIANA 46962