Ana
A I I E Transactions TwoOperation Crane Scheduling Problems
TwoOperation Crane Scheduling Problems
Lieberman, R. W., Turksen, I. B.Bu kitabı ne kadar beğendiniz?
İndirilen dosyanın kalitesi nedir?
Kalitesini değerlendirmek için kitabı indirin
İndirilen dosyaların kalitesi nedir?
Cilt:
14
Dil:
english
Dergi:
A I I E Transactions
DOI:
10.1080/05695558208975054
Date:
September, 1982
Dosya:
PDF, 603 KB
Etiketleriniz:
 Lütfen önce hesabınıza giriş yapın

Yardıma mı ihtiyaç var? Kindle'a nasıl kitap gönderileceğine ilişkin talmatına bakın
Dosya 15 dakika içinde epostanıza teslim edilecektir.
Dosya 15 dakika içinde sizin kindle'a teslim edilecektir.
Not: Kindle'ınıza gönderdiğiniz her kitabı doğrulamanız gerekir. Amazon Kindle Support'tan gelen bir onay epostası için gelen kutunuzu kontrol edin.
Not: Kindle'ınıza gönderdiğiniz her kitabı doğrulamanız gerekir. Amazon Kindle Support'tan gelen bir onay epostası için gelen kutunuzu kontrol edin.
İlgili Kitap Listeleri
0 comments
Kitap hakkında bir inceleme bırakabilir ve deneyiminizi paylaşabilirsiniz. Diğer okuyucular, okudukları kitaplar hakkındaki düşüncelerinizi bilmek isteyeceklerdir. Kitabı beğenip beğenmediğinize bakılmaksızın, onlara dürüst ve detaylı bir şekilde söylerseniz, insanlar kendileri için ilgilerini çekecek yeni kitaplar bulabilecekler.
1


2


This article was downloaded by: [University of Alabama at Tuscaloosa] On: 29 March 2015, At: 23:41 Publisher: Taylor & Francis Informa Ltd Registered in England and Wales Registered Number: 1072954 Registered office: Mortimer House, 3741 Mortimer Street, London W1T 3JH, UK A I I E Transactions Publication details, including instructions for authors and subscription information: http://www.tandfonline.com/loi/uiie19 TwoOperation Crane Scheduling Problems a R. W. Lieberman & I. B. Turksen a b Nuclear Simulator Ontario Hydro Pickering , Ontario, Canada b Department of Industrial Engineering , University of Toronto , Ontario, Canada , M5S 1A4 Published online: 09 Jul 2007. To cite this article: R. W. Lieberman & I. B. Turksen (1982) TwoOperation Crane Scheduling Problems, A I I E Transactions, 14:3, 147155, DOI: 10.1080/05695558208975054 To link to this article: http://dx.doi.org/10.1080/05695558208975054 PLEASE SCROLL DOWN FOR ARTICLE Taylor & Francis makes every effort to ensure the accuracy of all the information (the “Content”) contained in the publications on our platform. However, Taylor & Francis, our agents, and our licensors make no representations or warranties whatsoever as to the accuracy, completeness, or suitability for any purpose of the Content. Any opinions and views expressed in this publication are the opinions and views of the authors, and are not the views of or endorsed by Taylor & Francis. The accuracy of the Content should not be relied upon and should be independently verified with primary sources of information. Taylor and Francis shall not be liable for any losses, actions, claims, proceedings, demands, costs, expenses, damages, and other liabilities whatsoever or howsoever caused arising directly or indirectly in connection with, in relation to or arising out of the use of the Content. This article may be used for research, teaching, and private study purposes. Any substantial or systematic reproduction, redistribution, reselling, loan, sublicens; ing, systematic supply, or distribution in any form to anyone is expressly forbidden. Terms & Conditions of access and use can be found at http:// www.tandfonline.com/page/termsandconditions TwoOperation Crane Scheduling Problems* R. W. LIEBERMAN Nuclear Simulator Ontario Hydro Pickering, Ontario, Canada Downloaded by [University of Alabama at Tuscaloosa] at 23:41 29 March 2015 I. B. TURKSEN SENIOR MEMBER,IIE Department of Industrial Engineering University of Toronto Toronto, Ontario M5S 1A4, Canada Abstract: For twooperation crane scheduling problems we consider two basic procedures; namely, batching and meshing. A minimumordered partition forms the basis of the batching procedure. A meshordered relation forms the basis of the meshing procedure. Under certain necessary conditions, these procedures yield optimal schedules. Examples are provided to illustrate each procedure. Four mixed procedures are defined and combined t o form an efficient algorithm whose solution is no worse than 413 the optimal solution. Industrial processes employing overhead cranes which share a common track often encounter significant delays due to crane interference. The problem of crane scheduling deals with finding crane assignments which minimize these processing delays. The basic model of crane systems, the terminology, and some results on singleoperation crane scheduling problems can be found in the first paper of this series [2] . In this paper, the results given there are extended to jobs consisting of two operations, using the same terminology. The Batching Procedure In real applications, the majority of crane tasks consist of two operations: picking up a load of material from one location (the source) and transporting it to another location (the sink). For crane systems with all jobs consisting of exactly two operations, the set of jobs is 6 = {(Qil,Qi2)1 i = 1,. . . ,n), Received October 1980; revised February 1982. This paper was handled by the Scheduling, Planning, and Control Department. where Qil is the source location and Qi2 is the sink location. The model p4 = On, N, (n, 2), 0, T ) is the crane system having m cranes, N job locations, and n jobs of two bperatians, each operation requiring T time units to complete and all jobs simultaneously ready at time zero. It is a direct extension of the p , system studied in [2] with single operation jobs. Let L = {source locations) = {Qil ) and L2 = {sink locations}= {Qi2 ). For the job set 9 = {(3,2),(8,4), (1,5), (7,6)),L1 = {3,8,1,7) andL2 = {2,4,5,6). A crane which begins processing job Ji = (Qil, Qi2)must first move tolocation Q i , , remain there for a time period of .r,thenproceed to location Qi2 and remain there for a further rtime units. It is assumed that once a given crane begins processing the job Yi,no other crane can be assigned to process Ji. Once a crane begins to process the source location of job Ji, it is said to be committed to process the respective sink location. The algorithm z l , found so effective to solve the single crane system, cannot be directly operation (On, N, n, 0,~)) applied to the p4 system. If it is applied to the sources L , then the sink locations may not necessarily be processed , *This is a companion paper to "Crane Scheduling Problems" by the same authors which appeared in the December 1981 issue.  September 1982, IIE TRANSACTIONS    05695554/82/09000147/$2.00/0 O 1982 IIE   147 effectively because of the crane commitments and the resulting crane interference. Similarly, if z were applied to the sink locations L2, the source locations might not be processed efficiently. Whether or not a batching procedure can be applied to yield an optimal solution under the minimum makespan criterion is certainly dependent on the structure of the job set J. In [I] and [3], a necessary condition is given for an interferencefree solution using the following batching procedure. Downloaded by [University of Alabama at Tuscaloosa] at 23:41 29 March 2015 Procedure Batch (1) Partition the job set dinto r n l m l , where r x l is the ceiling of 3, batches Bi of at most m jobs, i = 1,2, . . . , rnlrnl, where B, C_Jsuch that U B, Vi = J and n Bi Vi = 6. (2) Process jobs of a batch simultaneously and independently from jobs in another batch. Let V be defined as the source numerical order operator so that for the job set L7 = {(Qil, Qi2)), V$ = [(all, Q12), (Q21,Q22), . . . ,(Qnl,Qn2)]suchthat !211<Q21 < . . . < Q n l . Define the ordered set of sources and the ordered set of sinks to be L,(V;F) = (Qll, Qz1,.. . ,Q,,) and L2(Vit) = (QIz,Qzz ,. .. ,.Qh2),respectively. Then the batching procedure yields an interferencefree solution if the batches Bi are constructed such that L2(VBi) are monotonicallyincreasing sequences for all i, i = 1,2, . . . ,r n / m l , where L2 (VB,) is the ordered set of sinks induced bythe ordered set of sources in the set Bi g $. Thus each batch will take time 27 to process, and the makespan M = 2rnlmw. It is established in [I] and [3] that M*(p4), the mpardel server (mps) solution, is 2rnlmk. In order to determine for a given job set whether such a batch construction is possible, it is necessary to consider the concept of a minimum ordered partition (MOP). Let P, = (PI, p2,. . . , pn) be a ntuple of unique integers and let Fk = (ykl, yk2,. . . , ykqk) be ordered subsets of P, such t h a t ( l ) u r k Vk=P,, (2)nFkVk=6,thenullset. The partition F = {rk )is an ordered partition if the following conditions hold: (a) yki < Tkj iff i <j, ffk and (b) yki = Pr and ykj = p, and i <j iff r < S, p,, p, Ep,. The is a minimum ordered partition (MOP) iff partition rmin I Tmin I < I F I V F. The partition number of P, is defined to be Q(P,) = I I'1 . A necessary condition for the partitioning of 3 such that the Procedure Batch yields an interferencefree solution is that Q [L2( V a l <r n l m l . Furthermore, Q can be determined by an O(n2) algorithm (see [ l ] and [3]) which constructs an MOP (see Appendix A). Quite often, a partition of the job set to obtain an interferencefree schedule under batching can be obtained directly from the constructed MOP provided the necessary condition is met. If Q[Lz ( O , )J >r n / m l , any schedule s constructed by the batching procedure will have a positive interference I(s). Before illustrating the above with an example, there are three conditions inherently assumed, the last two of which at first seem limiting but in reality are not. The assumptions are: (1) L, u L 2 = L The first assumption states that every location is either a source or a sink. The second one states that each location is either a source or a sink but not both. The third states that a given location can appear as a source or sink in exactly one job. In real applications, the latter two assumptions may not hold. In terms of the model, without these two assumptions the batching procedure could require two or more different cranes to begin processing the same location at the same time. However, it is physically impossible for more than one crane to process the same location at the same time. Therefore, for those jobs containing identical job locations, it is only necessary to ensure that they never appear in the same batch. This is merely a bookkeeping activity and does not actually affect the results with the assumptions as stated. Another assumption contained in the model is that cranes not processing at job locations can be positioned between any two job locations. Since most real applications have not more than four or five cranes, this assumption does not seem unreasonable. We now illustrate the above ideas by the following example: Given that the number of cranes m = 4, the number of job locations N = 20, and the number of jobs n = 10, the job set is: The mps Solution (1) We first apply the source numerical operator to 2 to obtain the set of ordered sinks L2( V 3 ) : IIE TRANSACTIQNS, Volume 14, No. 3 (2) We construct a minimumordered partition of J by partitioning L2(V) using algorithm MOP: Thus Q [L2(V 9)] = 3 < r 1 0 / 4 1 = 3 and the necessary condition is met. We observe that each subset rihas at most m =4 jobs, thus each subset ri determines a batch Bi. Therefore A mesh is determined by two things: (1) an ordered sequence of jobs and (2) the starting crane. In order to determine (I), it is helpful to define sinktosource relations (SSR's). Definition 1 Let Ji = (a,b) and Jj = ( c , d ) , i f j, where Ll({Ji,Jj)) = {a,c)andL2({Ji,Jj))= {b,d). Letw~{L,G),whereG and L are the binary relations "greater than" and "less than," respectively. Then: Downloaded by [University of Alabama at Tuscaloosa] at 23:41 29 March 2015 (3) Each batch can now be processed in time 27 to yield an interferencefree solution: (1) Ji%Jj o r J j g Ji iffcwb (2) Jjy Ji o r J i Jj i f f a o d (1) and (2) are combined to form: z1 0 (3) Ji In some cases the necessary condition is met but one or more subsets r k have cardinality greater than m. In order to process the r n / m l batches in time MX(p),each batch must not contain more than m jobs. Such a partition of jobs is termed a complete Mbatch set. To determine whether a complete mbatch set does exist, it may be necessary to examine all possible MOP'S. This problem, in general, is JY9complete. A variety of enumeration techniques, such as backtracking, are available to search for such a set. However, they are all exponential algorithms. Furthermore, a complete mbatch set may not exist even though the necessary condition is met. Under this circumstance, and for the case where the necessary condition is not met, other procedures may yield solutions whose makespan is the lower bound M*(p). As is shown in the next section, such a procedure can be derived for the crane system in which the number of cranes is m = 2. The Meshing Procedure When the number of cranes is restricted to two, another procedure known as "Mesh" may yield an interferencefree solution. [Interference was defined in [2] as I(s) = M(s) MX(p). Hence "interferencefree" implies I(s) = 0, i.e., M(s) = M*(p) M*.] A meshing procedure is one in which, given that both cranes are busy, while one crane is processing a source location of one job the other crane is processing a sink location of some other job. Since the model is static, this forces exactly one crane to be idle during the first and last 7 time units. Consequently, interferencefree schedules can only occur for job sets containing an odd number of jobs. For an even number of jobs, the best mesh will yield a makespan of M* + 7.  September 1982,iIE TRANSACTIONS +2 Jj i f f c o l b and a w d , w l , w2 E {L, G) . The binary relation y is known as a SinktoSource Relation, or SSR. For example, suppose Ji = (5,2) and Jj = (1,4). Then the SSR's of Ji and Jj are F Each pair of jobs defines 2 SSR's. A directed graph D49,E) is now defined to depict the SSR structure of the job set. Definition 2 Let DQ3, E) be the digraph of SSR's, where d , the job set, is ~ E~{~L, , G ) ),is the the set of vertices and E = { w ( i , ] > l ~ ~ w + set of directed edges. Definition 3 Given the digraph of SSR's D(& E), an alternating elementary path is an elementary path consisting of arcs alternating between L and G. Note that the sequence of jobs specified by an alternating elementary path yields a mesh on the jobs in the path. Furthermore, an alternating Hamiltonian path (AHP) is the best mesh, since all the jobs are included. So the problem of constructing a job sequence for a mesh reduces to that of finding the longest alternating elementary path in the digraph of SSR's D(M,E). Ideally, the path is Hamiltonian. Once the AHP defining the job sequence is determined, the starting crane is specified as follows: if the first arc in that path is labeled "L," then the fust job in the sequence is to be processed by crane C2. If the first arc in that path is labeled "G," then the first job is to be processed by crane C1. Consider the job set 3 = ((1,10), (3,8), (5,6), (7,4), (9,2)), where n = 5 and m = 2. With the application of algorithm MOP (see Appendix A), Q [L2(B 3)] is determined to be 5, but r / m l = 3 . Because Q>h/ml, an interferencefree schedule cannot be constructed using the batching procedure, since the necessary condition is not met. However, since n is odd, it may be possible to construct an interferencefree schedule by meshing if an AHP exists in the digraph of SSRs D($J). The digraph appears as Fig. 1. Since the first arc is labeled G, crane C1 is assigned to the first job on the path, J3.The schedule then is: X(0) = (6, 0 I 5,0), X(T)=(O,416,7),X(27)=(8,0 13,4), X(37) = (0,2 1 8,9), X(47) = (10,o 1 1,2), X(57) = (lo,()), X(67) = (0,0), where X(T) = (e, f I g, h ) is defined in [2] . In general, the determination of a Hamiltonian path is JWcomplete. However, for this special digraph, this may not be the case. An algorithm has been developed to find the longest alternating elementary path in D(d,E),although it uses backtracking and thus is exponential. It can be used, however, polynomially in O(n2), but does not guarantee the optimal solution (see [I] ). The algorithm is given in [I] ). Downloaded by [University of Alabama at Tuscaloosa] at 23:41 29 March 2015 Mixed Procedures on the TwoCrane Problem The batching and meshing procedures previously described can be used in various combinations to form mixed procedures which can be applied to the p5 = (2,N,(n,2),0,7)crane system to yield, in polynomial time, schedules with relatively low makespans. In fact, an algorithm will be described in this section which has time complexity O(n2) and yields a schedule having a makespan no greater than 413 the mps lower bound M*. The details of the procedure (Batch/Mesh)/Mesh are given in Appendix B. The details of the other procedures can be obtained from [I] . We have also included a discussion of the bounds on makespan for the p5 crane system in the same appendix. Recall that given a job set $ from ps ,a digraph of sourcetosink relations (SSRs), D($,E), can be constructed. Fig. 1 . The digraph for the example. Definition An AHP can be found yielding the job sequence (J3, J4, J2, J5, Jl) (see Fig. 2). J, A digraph of SSR's, D('$,E), is said to be saturated if all of the directed edges in E represent the same SSR. In other words, if the edges are all labeled "G" or all labeled "L," the digraph is said to be saturated. (1) BatchlMesh. The procedure alternates between the two procedures Batch and Mesh under the conditions that Q[L2(V$)] = n and D(d,E) is saturated. First an arbitrary set of two jobs is begun, but, since Q = n7the sinks cannot be processed together by their respective cranes. The third job is meshed with one of the first two (depending on the SSR). This is repeated until all jobs have been processed. It can be shown that the makespan is M(Batch/Mesh) = r4n/517 and the time complexity of the procedure is O(n). (2) BatchBatchlMesh. This procedure processes y batches of two jobs where y < r n / 2 1 and the remaining jobs by the Batch/Mesh procedure. The y batches can be taken from the MOP constructed by algorithm MOP. It can be shown that procedure BatchBatch/Mesh has a makespan of r(4ny)/31 T and hence M(BatchBatchlMesh) < r 4 4 3 17. Fig. 2. The Alternating Hamiltonian Path for the example. 150 (3) MeshBatchlMesh. This procedure is employed whenever IIE TRANSACTIONS, Volume 14, No. 3 Downloaded by [University of Alabama at Tuscaloosa] at 23:41 29 March 2015 Q[LZ(Vg)] = n and D(2,E) is not saturated. A mesh is performed on the jobs of the longest path found (with no backtracking) and the Batch/Mesh procedure is employed on the remaining jobs. It can be shown that for a path of lengh h, the makespan is MweshBatchlMesh) = r(4n  h + 2)/3lr. Since it is used under the assumption that D($, E ) is not saturated, h must be at least 2(X > 2). Such a path can be found in O(n2)time.Hence, M(MeshBatchlMesh) <r4n/31 T and its time complexity is O(n2). (4) (Batch/Mesh)/Mesh. This procedure utilizes the Batch/ Mesh and Mesh procedure to yield a makespan M[(Batch/ Mesh)/Mesh] < r4n13l~. Batches of three jobs (or less) are processed either by BatchIMesh or Mesh depending on certain conditions. The algorithm is given in Appendix B. The time complexity is shown to be O(n). It should be pointed out that the time complexities given with the above procedures hold only under the condition that no backtracking is employed. In the next section an algorithm is presented which utilizes these procedures without backtracking, producing a solution whose makespan is at most 413 the mps lower bound MX(p5) for large n. Since the optimal makespan may well be greater than M*Q5 ), this algorithm will probably yield a makespan much closer to the optimal than 413 the optimal makespan. The time complexity of the algorithm is polynomial; more precisely, O(n2 ). Algorithm POLY INPUT: 6,the job set from the system PS = (2fl,(n,2), 0,r) Bounds on Makespan Under Algorithm POLY Algorithm POLY specifies that one and only one mixed procedure is to be employed for any possible state of the job set. Since any of the mixed procedures yields a make, an upper bound on span no greater t h a n r 4 n / 3 1 ~therefore the makespan produced by algorithm POLY is MUB(POLY)= r 4 n / 3 1 ~ . Asymptotic Behavior  The following bounds are now developed: For n For n For n Time Complexity The determination of Q has complexity O(n2), as has already been stated. So, too, do the procedures BatchBatch/Mesh and MeshBatch/Mesh. The other two have complexity O(n), as was noted above. Therefore algorithm POLY has time complexity O(n2 ). September 1982, IIE TRANSACTIONS 4 (mod 6), M(P0LY) G [(4n + 2)/3n] M*(p5). (1) n O(mod 6), that is n = 6k; R 413. = r24k/372r6k/31= (2) n = 1 (mod 6), that is n = 6k + 1;R = r 4 n / 3 7 2 r n / 2 1 <4/3; R(n) = (4n+2)/(3n+3). (3) n = 2 (mod 6), that is n = 6k + 2; R = (8k+2)/(6k+2) > 413; R(n) = (4n+1)/3n . (4) n BEGIN IF D(d,E ) is saturated THEN IF Q = n THIN BatchIMesh ELSE BatchBatchlMesh; ELSE IF Q = n THENMeshBatchIMesh; ELSE (Batch/Mesh)/Mesh END 2 (mod 6), M(P0LY) < [(4n + 1)/3n] M*(p,). The ratio R is defined to be MuB(POLY)/M*(pS) = r4n/31/ 2r.1121 .This ratio is now examined for the six equivalence classes modulo 6. Let k be a positive integer: OUPUT: A schedule sp METHOD: The four procedures BatchIMesh, Batch/Batch/ Mesh, MeshBatchIMesh, and (Batch/Mesh)/?vlesh are employed under different conditions without backtracking. 0,1,3,5 (mod 6), M(P0LY) G (4/3)M*(ps ).  3 (mod 6), that is n = 6k + 3; R = 4(6k+3)/6(3k+2) <413; R(n) = 4n/(3n+3) . (5) n 4 (mod 6), that is n = 6k + 4; R = (4k+3)/(3k+2) > 413; R(n) = (4n+2)/3n . (6) n S(mod 6), that is n = 6k + 5; R = (8k+7)/(6k+6) < 413; R(n) = (4n+1)/(3n+3) . It can be seen that for n 1,3,5 (mod 6), R approaches 413 from the bottom; and for n 2,4 (mod 6), R approaches 413 from the top. These cases are shown in Fig. 3. As can be seen from Fig. 3 and Table 1, under the polynomial algorithm POLY, O(n2), the solution is guaranteed to be within 413 of the mps lower bound M*(ps) for reasonably sized n, and therefore at worst within 413 of the optimal solution. Example 1 Consider a (2, 20, (10,2), 0, 1) crane system with the job 151 1.5  1.4   I 5 0 10    1.3 R Downloaded by [University of Alabama at Tuscaloosa] at 23:41 29 March 2015  a  I n = 0 (mod 6 ) 15 '  l l l 20 n l   I 1 25     " l r l 30 l  a  i 4 l l 35 4 Asymptotic bounds on R = M(Poly)/M'(us) Fig. 3. Asymptotic bounds on R. Table 1 : The asymptotic behavior or bounds on R ( n ) ,n = 0 , I , 2, 3 , 4 , 5 (mod 6 ) . = n 0 (mod 6) nl RI 6 1 121 1 18 5 1.33) 1.33l 1.331 1.33' 1.331 1.33 n = 1 (mod 6 ) R = (4n + 2)1(3n+ 3 ) n 1 7 13 R 1 1.25 1.29 n 2 4 1 3 0 1 36 = 2 (mod 6 ) n1 2 R 1.5 19125 31 37 1 1.31 1.31 1.32 1.3 R = (4n + 1 )/3n 8 14 20 26 32 38 1.38 1.36 1.35 1 1.35 1.34 1.34 n = 3 (mod 6 ) R = 4nl(3rn + 3 ) n 1 3 9 15 21 27 33 39 R 1 1 1.2 1.25 1.27 1.29 1.29 1.3 n = 4 (mod 6 ) nl 4 R1 1.5 1 1 R = 22' 28 3 4 ) 40 1 1.36 1.36 1.351 1.35 1.38 n r 5 (mod 6 ) R n 5111 = (48 + 1)/(3n+ 3 ) 17 23 29 35 41 1.28 1.29 1.30 1.31 1.31 I R 152 1.161 1.25 We begin constructing the schedule by taking two jobs from batch B , and starting them together at time 0, so X(0) = (8,21 3,s). The jobs which are started at time 0 are labeled J 1 and J 2 , and the remaining job is J 3 . Since 8 = b l < a3 = 10, the schedule given by the right branch of Table 2 (a) is taken as follows: (4n + 2)/3n 101 16 1.4 set .ir = ((3,8), (521, (10,6), (15,141, (12,181, (19,1), (13,20), (4,719 (17,161, (9,11)1. Using algorithm MOP, it is determined that Q, the cardinality of a minimumordered partition, is 4. Since n , the number of jobs, is 10, we have Q # n. By inspection, the digraph D(JJ) is not saturated: (3,8) (5,2) and (5,2) G (10,6). Accordingly, (Batch/Mesh)/Mesh is to be em$eyed. The batches are constructed in an arbitrary manner: The next batch is then taken with the first two jobs (of B z ) beginning at time 4, hence X(4) = (18,14 1 12,15). We observe again that b, = 18 < 19 = a,, hence X(5) = (18,010,14), X(6)=(0,1 (18,19), X(7)=(0,1). The next batch (B3) begins at time 8 and X(8) = (20,16 1 13,17). Now we observe that 4 = a3 < b2 = 16, so that the left branch of Table 2(a) is taken as follows: IIE TRANSACTIONS, Volume 14, No. 3 X(9) = (0,16 1 20,0), X(10) = (7,O 14,16), X(11) = (7,O) . The last batch consisting of one job is now processed: the search. In point of fact, for Example 1, no complete mbatch set of cardinality r n / m l exists and hence the search would have taken exponential time without a guarantee of an optimal solution. For Example 2, a complete mbatch set can be found in exponential time yielding an optimal solution. In a similar manner, one could seek a mesh without a guarantee of an optimal solution. X(12) = (1 1,0 19,0), Downloaded by [University of Alabama at Tuscaloosa] at 23:41 29 March 2015 Table 2 : Procedure (Batch/Mesh)/Mesh. The makespan is 14. The lower bound M* is calculated as 2 r 1 0 / 2 1 = 10. This result can also be seen from Fig. 3. We observe that for n = 10 = 4 mod 6, the ratio R = 1.4, hence the makespan M is (1.4)M* = 14. Example 2 (a I f (a3 < b 2 ) or ( b l < a s ) I f a3 X(O) X(7) X(27) X(37) X(47) < bz J. 4 1 ( b l , bz I f bl <a3 al, az) ( 0 . b 1~b i . 0 ) (b3.0la3, b z ) (b3,O) (0.0) ( b l , O f O ,b 2 ) (0.b31b l , a31 (o,b3) (0.0) (b) Consider the following (2, 18, (9,2), 0, 1) system with = ((4,171, (10,5), (15,3), (8,141, (12,1), (2,16), (7,131, (1 1,6), (9,18)). The lower bound is calculated as M* = 2r9/'2 1 = 10. For n = 9 = 3 mod 6, the algorithm will yield a schedule with makespan of M = 12 (see Fig. 3). Again, Q = 5 # n and D is not saturated. Again, the batches are constructed arbitrarily: I f (b2 < a 3 < b l ) I f al < b3 .1 X(O) ( b 2 , 0 l a 2 , 0 ) X ( 7 ) ( 0 ,b 3 lbz, a3 ) X ( 2 7 ) ( b 1 , 0 1 ~ 1b ,3 ) X(37)(bl,O) X ( 4 7 ) (0,O) I I I f a2 > b3 4 ( 0 ,b l l 0 , a l ) (b3,01a3, b l ) (0, b2 1 b3, az ( 0 ,b z ) (0,O) Concluding Remarks In the first batch, none of the conditions in Table 2(a) can be realized. Therefore, the conditions presented in Table 2(b) must hold. Thus we have b2 < a3 < b l (5 < 15 < 17) and a2 > b3 (10 > 3). Thus batch B1 is processed as shown in the right branch of Table 2(b). The remaining batches can be processed as in Example 1, hence the schedule is: At this point, it is worthwhile to remark that for both Examples 1 and 2, since Q < Tn/ml, an optimal solution (M = M*) may possibly be obtained by searching for a complete mbatch set if one is willing to pay the price for September 1982, IIE TRANSACTIONS Like many other scheduling problems, crane scheduling with the single track constraint is computationally very difficult. Except for the simplest crane systems, the computational complexity of crane scheduling isJY9hard. Under certain conditions, however, interferencefree schedules can be obtained for the On,N,(n,2),0,~)and (2,N9(n,2),0,r) crane systems. Quite often, a complete mbatch set is given directly by the minimumordered partition constructed by algorithm MOP. l'he batching procedure can then be applied to yield an optimal schedule. If the condition is not satisfied, it may be possible to find an interferencefree schedule with another procedure such as Mesh. As presented here, the meshing procedure can only be applied to systems with two cranes. An efficient algorithm [one of 0(n2)] can be employed on twocrane systems which yields schedules whose makespans are at worst 413 the lower bound value. It is conjectured that similar procedures can be developed for crane systems having more than two cranes. Acknowledgments This work was supported by the Natural Science and Engineering Council of Canada under Grant No. A7698. 153 References [5] Downloaded by [University of Alabama at Tuscaloosa] at 23:41 29 March 2015 Lieberman, R. W., "Scheduling Under Interference Constraints," PhD thesis (unpublished), University of Toronto (October 1979). Lieberman, R. W. and Turksen, I. B., "Crane Scheduling Problems," AZZE TRANSACTIONS 13, 4, 30431 1 (December 1981). Lieberman, R. W. and Turksen, I. B., "A Necessary Condition for the Elimination of Crane Interference," Proceedings of the Ninth IFIP Conference on Optimization Techniques, Warsaw, Poland (September 1979). Graefe, P.W.U., Nenonen, L. K., and Strobele, K., "Simulation of Combined Discrete and Continuous Systems on a Hybrid Computer," Simulation, 129237 (May 1974). [7] [8] [9] Appendix B: Appendix A: Algorithm MOP INPUT: [6] Gross, D. and Harris, C. M., Fundamentals of Queueing Theory, John Wiley and Sons, New York (1974). Aho, A. V., Hopcroft, J. E., and Ullman, J. D., The Design and Analysis of ComputerAlgorithms, AddisonWesley, Reading, Massachusetts (1975). Coffman, E. G., Jr., Bruno, J. L., Graham, R. L., Kohler, W. H., Sethi, R., Seiglitz, K., and Ullman, J. D., Computer and JobShop Scheduling Theory, John Wiley and Sons, New York (1976). Baker, K. R., Introduction to Sequencing and Scheduling, John Wiley and Sons, New York (1976). Kedia, S. K., "A JobShop Scheduling Problem with Parallel Machines" (unpublished), Department of Industrial Engineering, University of Michigan (1970). An ntuple Pn = (p ,, p2, . . . , pn) . Procedbre (Batch/Mesh)/Mesh . OUTPUT: A MOP r(Pn) = {rk 1 k= 1,2, . . ,@Pn) ) , whererk=('~kl,~k2,..,"dk~~) The Algorithm BEGIN k + l ; Q l +l;j+l;yIl + p l ; FOR i + 2 UNTIL n DO BEGIN IF pi < Ykek THEN BEGIN k + k + 1; jtk; +I Em; ELSE IF k = 1 THEN GOT0 new; ELSE FOR j + k step 1 UNTIL 2 DO BEGIN IF ^/jnj <pi < ~ j  iQ ~ THEN ~ BEGIN 'li'!2j+ 1; GOT0 set END; ELSE IF j = 2 THEN BEGIN j + 1; GOT0 new EM) END; BEGIN For the job set d , take batches of three jobs at a time until eY is exhausted. The last batch may have less than three jobs. LET Ji = ( a , bi); consider any batch; IF the batch contains less than three jobs, THEN Batch/ Mesh; ELSE the batch has three jobs J1, J2, J3; IF b2 < a3 < bl, THEN apply Mesh starting with either J1or J2and then meshing with J3. ELSE Batch/Mesh starting with X(0) = (bl, b2 I a l , a21 EM>. 4 new : Time Complexity of (Batch/Mesh)/Mesh BatchlMesh takes any two jobs and meshes the third and therefore takes time proportional to n.Mesh is employed by either beginningJl or J2and meshing J 3 , a total of at worst n t 1 operations. Therefore, (Batch/Mesh)/Mesh is of time complexity O(n). Bounds on Makespan LEMMA1. Assume that njobs are to be processed by two cranes in m / 3 1 batches, where r n / 3 1 batches contain exactly three jobs. If 3Xn, then there is one remaining batch containing either one or two jobs. Each of the threebatches are processed in time 47. A twobatch is processed in 37 and a onebatch in 27. The makespan M is then given as r 4 n / 3 7 ~ . IIE TRANSACTIONS, Volume 14, No. 3 PROOF: There are three cases to consider: (a)n = O m o d 3 , h e n c e M = 4 L n / 3 J ~ = r 4 n / 3 1 ~ . (b)n = 1 mod3,thenM =4Ln/3Jr+Zr=r4n/317 by Lemma 2. (c) n = 2 mod 3, then M = 4 L n / 3 J ~+ 37 = r 4 n / 3 1 ~by Lemma 3. LEMMA2: If n  1 mod 3 then K n / 3 1  2 = r 4 n / 3 1 . P ~ o o ~ . L e t n = 3 kl , + k=O, 1,2,. . ..ThenKn/31 2 = 4k + 2 and r 4 n / 3 1 = 4k + 2. Case I: X(0) = (b2 ,O l a2 ,O), or Case 11: X(0) = (O,bl I 042, ) . After 27 time units, the following possible states may exist: from Case I, X(27) = (bl ,0 1al,b3); from Case 11, X(27) = (O,b2 b39a2)We can therefore say that for a Mesh, a l < b3 or b3 < a 2 . A Mesh would be impossible if both a l > b3 and b3 > a2, but this is never the case, for it would imply that a, > a 2 , contradicting Assumption 1. Therefore a mesh is always possible whenever b2 < a3 < bl. Downloaded by [University of Alabama at Tuscaloosa] at 23:41 29 March 2015 LEMMA3. If n = 2 mod 3, then 4Tn/31 1 = r4n/31. THEOREM. For a pg crane system, if Q < n and D($,J!?) is not saturated, then M[(Batch/Mesh)/Mesh] = r 4 n / 3 1 ~ . PROOF. Let Ji = (ai,bi). It is now shown that a batch of three jobs can be processed in time 47, that two jobs can be processed in time 37 and one job in 27. Since the procedure processes jobs in batches of three jobs except the last, which contains n mod 3 if 31n and3 if 3 1 n, it follows that M [(Batch/Mesh)/Mesh]=r4n/31 from Lemma 1.o It is trivial to see that a batch consisting of exactly one job takes 27. Again, a batch of exactly two jobs, when processed using Batch/Mesh, takes 37. Now consider a batch of three jobs: J1, J2, and J3.Any two of them can be started together since both cranes are idle, so without loss of generality it is assumed that a l <a2. (Assumption 1). There are then two cases to consider: (1) J3canbemeshed,i.e.,bl <a3 ora3 <b2.1fJg can be meshed, then the procedure reduces to BatchIMesh and M(Batch/Mesh) = r4n/317. This is shown in Table 2 (a). (2) J3 cannot be meshed, i.e., b2 < a3 < bl . If J3cannot be meshed, then the strategy specifies a Mesh for all three jobs. Given that a Mesh on the three jobs is possible, a makespan of 47 = r4n/317 is achieved [see Table 2 (b)] . It is now shown that a Mesh on the batch of three jobs is alwavs possible under the condition that b2 < a3 < bl by starting J2 on crane C1 or J1on crane C2, i.e., September 1982, IIE TRANSACTIONS Ismail B. Turksen is Associate Professor of the Department of Industrial Engineering at the University of Toronto. He earned the degrees of BS, MS, and PhD in Industrial Engineering and Operations Research, all from the University of Pittsburgh. He is a member of the Board of Advisors of the Encyclopedia of Computer Science and Technology and a senior member of the Institute of Industrial Engineers. He was a member of the Board of Trustees of the Institute of Industrial Engineers, VicePresident of Region XIV (Canada), and is the past President of Canadian Society for Industrial Engineering. He is a member of CORS/APEO. He has published and presented papers in the areas of operations research, information systems, scheduling, human error detection and control, and linguistics variables in fuzzy sets and systems. Robert W. Lieberman is an Assistant Technical Supervisor at Ontario Hydro. He holds a BSc, MASc, and PhD in Industrial Engineering, all from the University of Toronto. Currently he is engaged in research and development of training systems for nuclear power plant simulators. He has presented and published papers in the area of scheduling. He is a member of CORS and APEO. 155