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