LogisticsScheduling:AnalysisofTwo-StageProblemssecond operation cannot be started priortotheThere is a set of n jobs, N= (Ji, J,., Jn),completion of the first operation. The firsttofirst beprocessed in a manufacturing system(second) operation of Jjmust be executed byby a single machine and then be delivered tomachine Mi (M2) during a given uninterruptedthe respective customers (assume located intimeplij (p2), forj=1,2...n.close proximity).EachJjineeds p processingtimeinthemanufacturingsystemand isLet fbe a system problem schedule. For Jassociated with a due date d. One vehicle isin schedule (s, Ca(αs) is defined as theavailable to deliver jobs (v= 1), which has acompletiontmefortheqthoperationofJqcapacity of =.Thevehicle capacityismeasured1, 2, and C(αs) is defined as the completionby the maximum number of jobs that vehicletime of Jjin schedule (s. Note that C(cs) =can provide for one delivery. All jobs deliveredCzi(αs) for all j. The cost functions consideredtogether in one shipment to a single destinationin this studyforType-Iproblems areare defined as a delivery batch. We assume thatcustomersarelocatedincloseproximitytoeach other (defined as one customer-area),hence all deliveries require the sametransportation time. Let to denote the one-waytransportationtimebetween the machine andX(α)=n=IC(()the customer-area, and T= 2tol. The problem isto find a schedule for processing jobs in thethe total job completion time in schedule fs,manufacturing system and for deliveringandfinished jobstothecorrespondingcustomers,Cmax(as)= max[C(os), j=1, 2,...,n),in order to minimizea certain objectivefunction.the makespan of schedule fs.Let P be the sum of the processing times inUnless ambiguity would result, Cq(os),the manufacturing system of all jobs, i.e., P=C(αs), X(αs) and Cmax(αs) are simplified ton= pj. Let (be a system problem schedulejCq,C,XandCmaxrpctivelyThe following notations for schedule Is aredefined:K(os) = the total number of delivery batches inThe three-field notation scheme, ( Iβ IY,schedule (sB(αs)= the kih delivery batch in schedule (s, kintroduced by Graham, et al. (1979), is= 1, 2, ..,K(os). Batches delivered earlier havefollowedto represent theproblems beingsmaller indicesstudied. Moreover, in order to distinguishC(α.)=thecompletion timeofJ,,whichisdefined as the time when itarrives at itstwo-stage problems from classic schedulingcustomer.All jobs within a delivery batch haveproblems, additional symbols in the?field arethe same completion timesdefined to represent these problems. Thesymbols 33and 338evotshat systemproblems are solved by the Forward and theBackward Approach, respectively.For example,F2||Cmax denotes a two-stage problem solvedby the Forward Approach in which the firststage is solved first followed by the secondstage with the objective of minimizing themakespan.(i)Type-lproblem: the second stage is jobdelivery390JOURNAL oF SYST EMS SCIENCE AND SYSTEMS ENGINEERING/ Vol. 12, No. 4, December,2003
Logistics Scheduling: Analysis of Two-Stage Problems second operation cannot be started prior to the completion of the first operation. The first (second) operation of Jjmust be executed by machine M1 (M2) during a given uninterrupted time p1j (p2j), for j = 1, 2,., n. Let s be a system problem schedule. For Jj in schedule s, Cqj(σs) is defined as the completion time for the qth operation of Jj , q= 1, 2, and Cj(σs) is defined as the completion time of Jj in schedule s. Note that Cj(σs) = C2j(σs) for all j. The cost functions considered in this study for Type-I problems are: j(σs) = n 1 C j( s ) ,j the total job completion time in schedule s, and Cmax(σs) = max{Cj(σs), j =1, 2,.,n}, the makespan of schedule s. Unless ambiguity would result, Cqj(σs), Cj(σs), j(σs) and Cmax(σs) are simplified to Cqj, Cj, j and Cmax, respectively. The three-field notation scheme, |β |γ, introduced by Graham, et al. (1979), is followed to represent the problems being studied. Moreover, in order to distinguish two-stage problems from classic scheduling problems, additional symbols in the field are defined to represent these problems. The symbols and that system problems are solved by the Forward and the Backward Approach, respectively. For example, F2|→|Cmax denotes a two-stage problem solved by the Forward Approach in which the first stage is solved first followed by the second stage with the objective of minimizing the makespan. (ii) Type-II problem: the second stage is job delivery There is a set of n jobs, N = {J1, J2,., Jn}, to first be processed in a manufacturing system by a single machine and then be delivered to the respective customers (assume located in close proximity). Each Jj needs pj processing time in the manufacturing system and is associated with a due date dj. One vehicle is available to deliver jobs (v = 1), which has a capacity of z. The vehicle capacity is measured by the maximum number of jobs that vehicle can provide for one delivery. All jobs delivered together in one shipment to a single destination are defined as a delivery batch. We assume that customers are located in close proximity to each other (defined as one customer-area); hence all deliveries require the same transportation time. Let t01 denote the one-way transportation time between the machine and the customer-area, and T = 2t01. The problem is to find a schedule for processing jobs in the manufacturing system and for delivering finished jobs to the corresponding customers, in order to minimize a certain objective function. Let P be the sum of the processing times in the manufacturing system of all jobs, i.e., P = n 1 p j . Let s be a system problem schedule.j The following notations for schedule s are defined: K(σs) = the total number of delivery batches in schedule s. Bk(σs) = the kth delivery batch in schedule s, k = 1, 2, .,K(σs). Batches delivered earlier have smaller indices. Cj(σs) = the completion time of Jj, which is defined as the time when it arrives at its customer. All jobs within a delivery batch have the same completion times. 390 JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 4, December, 2003
CHANGand LEEL(αs)=C(os)dj, the lateness of J, p.the sequence (sub-FS1, sub-FS2); using theThe cost functions considered in this studyBackward Approach, the two sub-problems arefor Type-l problems is Lmax(cs), in whichsolved in the sequence (sub-BS2, sub-BS1). InLmax(a.)= max[ L(os),j= 1, 2,., n ,thesub-FS1,theproblemsolutionprovidesthemaximum lateness of the jobs in schedulefsinformation/constraintstosub-FS2andinsub-BSI, the solution is made by consideringUnless ambiguity would result, we simplifytheadditionalinformation/constraintsK(αs), Bk(cs), Pr(αs),C(αs), L(αs), Cmax(αs) andgenerated from solving sub-B S2. Note thatLmax(os), to K, Bk, Pk, C, Lj, Cmax and Lmax,sub-FS1 and sub-BS1 are different problems,respectivelyalthough both are considered as stage 1In addition to the three-field notationproblems. For the same reason, sub-FS2 andscheme and the symbol previously defined insub-BS2 are also two different problems, eventhe field for Type-I problems, the notationthough they are both stage 2 problemsintroducedbyLeeandChen(2001)isfollowedLet sub-A denote a sub-problem, AE(FS1,to represent the Type-Il problems being studied.FS2, BS1, BS2). d μA) is defined as the dueIn the ( field, "1→D" is used to representdate of J in sub-A and r Aa) is defined as theproblems in which jobs are first processed on areleasedate ofJjin sub-A,p.Letfbeasingle machine and then delivered to theschedule of sub-A. C (A) (o) and L() (α) arecustomer-area In the ? field, we use“v-,c="defined as the completion time and the latenessto represent number of vehicles and the vehicleofJ,,in schedule(,respectively.Unlesscapacity,respectively.For example, 1→Div=1,ambiguity would result, C(a)(o) and Lu4) (o)c=z,/maxdenotesatwo-stageproblem withare simplified to C A)and L(a). Moreover,the objective of min imizingthe maximumlet L(4)*and C(a)*denotethelateness andlateness subject to (i) one available vehiclethecompletion time ofJjintheoptimalwith capacity of , (i) jobs with general sizes,solution of sub-A,respectively.Similarly(iml) solution by the Backward Approach.L(a)hand C u.a)hrepresent the lateness andcompletiontimeofJjobtainedfromsolvingsub-A by a particular heuristic h. To simplifythe notation, unless ambiguity would result,"h" is used as a generic term to represent aparticular heuristic.2.2Sub-problemsThe problem considered in each stage isdefined as one sub-problem. For each approach,we explicitly define two sub-problems, one torepresent each of the two stages. Let sub-FS1and sub-FS2 denote sub-problems consideredat stage I and stage 2, respectively,when usingthe Forward Approach. Similarly, let sub-BS1andsub-BS2denotesub-problems considered2.3Worst-Case Performance Analysisatstageandstage2rpctivelywhenuinIn each approach, two sub-problems arethe Backward Approach. Using the Forwardsolved sequentially to obtain two jobApproach,thetwo sub-problems are solved insequences, each of which is preferred by onestage. Based on these two sequences, theobjective value for the system problem may be391JOURNAL oF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING/Vol. 12, No. 4, December, 2003
CHANG and LEE Lj(σs) = Cj(σs) dj, the lateness of Jj, The cost functions considered in this study for Type-II problems is Lmax(σs), in which Lmax(σs) = max{ Lj(σs), j = 1, 2,., n }, the maximum lateness of the jobs in schedule s. Unless ambiguity would result, we simplify K(σs), Bk(σs), Pk(σs),Cj(σs), Lj(σs), Cmax(σs) and Lmax(σs), to K, Bk, Pk, Cj, Lj, Cmax and Lmax, respectively. In addition to the three-field notation scheme and the symbol previously defined in the field for Type-I problems, the notation introduced by Lee and Chen (2001) is followed to represent theType-II problems being studied. In the field, “1→D” is used to represent problems in which jobs are first processed on a single machine and then delivered to the customer-area. In the field, we use “v=, c= ” to represent number of vehicles and the vehicle capacity, respectively. For example, 1→D|v=1, c=z, max denotes a two-stage problem with the objective of minimizing the maximum lateness subject to (i) one available vehicle with capacity of z, (ii) jobs with general sizes, (iii) solution by the Backward Approach. 2.2 Sub-problems The problem considered in each stage is defined as one sub-problem. For each approach, we explicitly define two sub-problems, one to represent each of the two stages. Let sub-FS1 and sub-FS2 denote sub-problems considered at stage 1 and stage 2, respectively, when using the Forward Approach. Similarly, let sub-BS1 and sub-BS2 denote sub-problems considered at stage 1 and stage 2, respectively, when using the Backward Approach. Using the Forward Approach, the two sub-problems are solved in the sequence {sub-FS1, sub-FS2}; using the Backward Approach, the two sub-problems are solved in the sequence {sub-BS2, sub-BS1}. In sub-FS1, the problem solution provides the information/constraints to sub-FS2; and in sub-BS1, the solution is made by considering theadditionalinformation/constraints generated from solving sub-BS2. Note that sub-FS1 and sub-BS1 are different problems, although both are considered as stage 1 problems. For the same reason, sub-FS2 and sub-BS2 are also two different problems, even though they are both stage 2 problems Let sub-A denote a sub-problem, A∈{FS1, FS2, BS1, BS2}. d (j A) is defined as the due date of Jj in sub-A and r j( A) is defined as the release date of Jj in sub-A, Let be a schedule of sub-A. C (j A) (σ) and L(jA) (σ) are defined as the completion time and the lateness of Jj, in schedule respectively. Unless ambiguity would result, C (j A) (σ) and L(jA) (σ) are simplified to C (j A) and L(jA) . Moreover, let L(jA)* and C (j A)* denote the lateness and the completion time of Jj in the optimal solution of sub-A, respectively. Similarly, L(jA) h and C (j A) h represent the lateness and completion time of Jj obtained from solving sub-A by a particular heuristic h. To simplify the notation, unless ambiguity would result, “h” is used as a generic term to represent a particular heuristic. 2.3 Worst-Case Performance Analysis In each approach, two sub-problems are solved sequentially to obtain two job sequences, each of which is preferred by one stage. Based on these two sequences, the objective value for the system problem may be JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 4, December, 2003 391
LogisticsScheduling:AnalysisofTwo-StageProblemsaddedinfrontof&toindicate&ofthatcalculated, The two sequences and theobjective value represent the system problemsection, i.e. 4 means Section 4.For examplesolution if solved by the approach applied.Zurdenotes the system problem objectivevalueconsideredin Section4whileusingtheDefine&(F,B),whereF denotes theForward Approach.Forward Approach, and B denotes theBackward Approach.For each of the systemproblems under consideration, let / be aparticular instance and define:3.ProblemF2//CmaxZ&(I) : the objective value for the systemproblem on instance I if solved by theIn this section, F21/Cmax is discussed as ancorresponding&exampletodemonstratetheuseoftheForwardZ-():the optimal objective value to theand Backward Approaches.system problem on instance I.When theobjective of the system problemis to minimizemakespan (maximum lateness),System Approach:use Cmax (Lmax)to replace Z. Note that 3(D)3 isIf the two machines are fully coordinatedomitted unless ambiguity would result. Inthecorresponding worst-case analysis for each(i.e., a system problem is considered), it issystem problem, compare Z&(I) and Z-(I).optimal toapplyJohnson'salgorithm (1954).Specifically,for completion-time relatedAn optimal sequence obtained using Johnson'sobjectives (Cyor Cmax), the interest lies inalgorithm can be described as follows: the jobsderiving the worst-case performance ratio for awith puj 8 paj are arranged first in thesystem problem, which is defined as:non-decreasingorderofpij,theremainingjobs,R&α inf (r≥1Z(I)Z-(I)8r, for all I).with plj> p2j, are subsequently arranged in theWhen dealingwith due-date relatednon-increasing order of pzj.Suppose these twoobjectives,theworst-caseratiocannotbeusedstages are not fully coordinated.torepresentperformance,whenall jobsareontime, the ratio goes to infinity.Alternatively,following the literature in classic machinescheduling the relative difference betweenZ&(I) and Z-(I) is usedto represent theworst-case performance in such cases.TheForward Approach:worst-case performance difference is definedUsing the Forward Approach, theas:sub-problem considered at stage 1, sub-FS1,D&αinf(Z(1)Z()r,forall )may be defined as a single machine problemFurthermore, in order to distinguish thewith the objective of minimizing makespan.objectivevalueofonesystemproblemfromThe job processing times considered inthat ofother system problems,"a number"issub-FS1 areplj,p.Sub-FSI may be optimizedby ary sequence.Given an optimal sequencefor sub-FS1,the job completion time(CFsi)*)becomes the releasedate(rFs2))for Jj insub-FS2. Hence sub-FS2 may be defined asanother singlemachine makespan problemwith unequal job release dates, which may besolved optimally by an Earliest Release Date3Fpolicy,Since Cmax n=1 p1j+n=I p2iandyCmaxmax[n=ijn=p2]),itollowsj392JOURNAL oF SYST EMS SCIENCE AND SYSTEMS ENGINEERING/ Vol. 12, No. 4, December,2003
Logistics Scheduling: Analysis of Two-Stage Problems calculated. The two sequences and the objective value represent the system problem solution if solved by the approach applied. Define {F, B}, where F denotes the Forward Approach, and B denotes the Backward Approach. For each of the system problems under consideration, let I be a particular instance and define: Z(I) : the objective value for the system problem on instance I if solved by the corresponding Z*(I) : the optimal objective value to the system problem on instance I. When the objective of the systemproblem is to minimize makespan (maximum lateness), use Cmax (Lmax) to replace Z. Note that is omitted unless ambiguity would result. In the corresponding worst-case analysis for each systemproblem, compare Z(I) and Z*(I). Specifically, for completion-time related objectives (ΣCj or Cmax), the interest lies in deriving the worst-case performance ratio for a systemproblem, which is defined as: R inf { r≥ 1 | Z(I)/ Z*(I) r, for all I}. When dealing with due-date related objectives, the worst-case ratio cannot be used to represent performance; when all jobs are on time, the ratio goes to infinity. Alternatively, following the literature in classic machine scheduling, the relative difference between Z(I) and Z*(I) is used to represent the worst-case performance in such cases. The worst-case performance difference is defined as: D inf{r≥ 0 | Z(I) Z*(I) r, for all I}. Furthermore, in order to distinguish the objective value of one system problem from that of other system problems, “a number” is added in front of to indicate of that section, i.e. 4 means Section 4. For example, Z4F denotes the system problem objective value considered in Section 4 while using the Forward Approach. 3. Problem F2| |Cmax In this section, F2| |Cmax is discussed as an example to demonstrate the use of the Forward and Backward Approaches. System Approach: If the two machines are fully coordinated (i.e., a systemproblem is considered), it is optimal to apply Johnson’s algorithm (1954). An optimal sequence obtained using Johnson’s algorithm can be described as follows: the jobs with p1j p2j are arranged first in the non-decreasing order of p1j; the remaining jobs, with p1j > p2j, are subsequently arranged in the non-increasing order of p2j. Suppose these two stages are not fully coordinated. Forward Approach: Using the Forward Approach, the sub-problem considered at stage 1, sub-FS1, may be defined as a single machine problem with the objective of minimizing makespan. The job processing times considered in sub-FS1 are p1j, Sub-FS1 may be optimized by any sequence. Given an optimal sequence for sub-FS1, the job completion time ( C (j FS1)* ) becomes the release date ( r j( FS 2) ) for Jj in sub-FS2. Hence sub-FS2 may be defined as another single machine makespan problem with unequal job release dates, which may be solved optimally by an Earliest Release Date 3Fpolicy. Since Cmax n 1 p1 j n 1 p2 j andjj *Cmax max{ n 1 p1 j , n 1 p2 j }, it followsjj 392 JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 4, December, 2003