《系统工程》课程教学资源（英文文献）LOGISTICS SCHEDULING ANALYSIS OF TWO_STAGE PROBLEMS

LOGISTICSSCHEDULING:ANALYSISOFTWO-STAGEPROBLEMSYung-Chia CHANGChung-Yee LEEDavicom America CorporationI135 Kem Avene, Sumyrale, CA 94085, U.S.4.DepartmentofIndustrial Engineeringand Engineering MnagementHong Kong University of Science &TechnologyClear Water Bay, Kowloon, Hong Kongcylee@usthkja.smine_chang@davicom8.comAbstractThis paper studies the coordination effects between stages for scheduling problems wheredecision-making is a two-stage process.Two stages are considered as one system. The system can bea supply chain that links two stages,one stage representing a manufacturer,and the other,a distributor.It also can represent a single manufacturer,whileeach stagerepresents a different departmentresponsible for a part of operations.A problem that jointly considers both stages in order to achieveideal overall system performance is defined as a system problem. In practice, at times, it might not befeasible for the two stages to make coordinated decisions due to () the lack of channels that allowdecision makers at the two stages tocooperate, and/or (i)the optimal solution tothe system problemistoodifficult(orcostly)toachieveTwo practical approaches are applied to solve a variant of two-stage logistic schedulingproblems. The Forward Approach is defined as a solution procedure by which the first stage of thesystem problem is solved first, followed by the second stage. Similarly, the Backward Approach isdefined as a solution procedure by which the second stage of the system problem is solved prior tosolving the first stage. In each approach, two stages are solved sequentially and the solution generatedis treated as a heuristic solution with respect tothe corresponding system problem. When decisionmakers at two stages make decisions locally without considering consequences to the entire systemineffectiveness may result -even when each stage optimally solves its own problem. The trade-offbetween the time complexity and the solution quality is the main concern. This paper provides theworst-caseperformance analysis for each approach.Keywords:Logistics scheduling worst caseanalysis,dynamic programmingthe most important and widely discussed topics1.Introductionin manufacturing research over the last tenyears. A supply chain represents all stages atSupply chain management has been one ofThis research is supported in part by Hong Kong RGC Grant HKUST 60 1002E.JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERINGISSN1004-3756/03/1204/385CN11-2983/NJSSSE2003Vol. 12, No.4, pp385-407, December, 2003

LOGISTICS SCHEDULING: ANALYSIS OF TWO-STAGE PROBLEMS Yung-Chia CHANG Chung-Yee LEE Davicom America Corporation 1135 Kern Avenue, Sunnyvale, CA 94085, U.S.A. Department of Industrial Engineering and Engineering Management Hong Kong University of Science & Technology Clear Water Bay, Kowloon, Hong Kong jasmine_chang@davicom8.com cylee@ust.hk Abstract This paper studies the coordination effects between stages for scheduling problems where decision-making is a two-stage process. Two stages are considered as one system. The system can be a supply chain that links two stages, one stage representing a manufacturer; and the other, a distributor. It also can represent a single manufacturer, while each stage represents a different department responsible for a part of operations. A problem that jointly considers both stages in order to achieve ideal overall system performance is defined as a systemproblem. In practice, at times, it might not be feasible for the two stages to make coordinated decisions due to (i) the lack of channels that allow decision makers at the two stages to cooperate, and/or (ii) the optimal solution to the system problem is too difficult (or costly) to achieve. Two practical approaches are applied to solve a variant of two-stage logistic scheduling problems. The Forward Approach is defined as a solution procedure by which the first stage of the systemproblem is solved first, followed by the second stage. Similarly, the Backward Approach is defined as a solution procedure by which the second stage of the system problem is solved prior to solving the first stage. In each approach, two stages are solved sequentially and the solution generated is treated as a heuristic solution with respect to the corresponding systemproblem. When decision makers at two stages make decisions locally without considering consequences to the entire system, ineffectiveness may result – even when each stage optimally solves its own problem. The trade-off between the time complexity and the solution quality is the main concern. This paper provides the worst-case performance analysis for each approach. Keywords: Logistics scheduling, worst case analysis, dynamic programming the most important and widely discussed topics in manufacturing research over the last ten years. A supply chain represents all stages at 1. Introduction Supply chain management has been one of  Thisresearch is supported in part by Hong Kong RGC Grant HKUST 6010/02E. JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING Vol. 12, No. 4, pp385-407, December, 2003 ISSN 1004-3756/03/1204/385 CN11- 2983/N ©JSSSE 2003

Logistics Scheduling:Analysis of Two-Stage Problemswhich value is added to a manufacturedSarmiento and Nagi (1999). Specifically, Hallproduct, Substantial ineffectiveness may resultand Potts reported the benefits of cooperativewhen decision-making between differentdecision-making for scheduling in a supplystages is poorly coordinated. Therefore, anchain where a supplier makes deliveries toimportant issue in supply chain managementseveral manufacturers, who may in turn supplyresearch is coordination between decisionseveral customers. They demonstrated thatcooperationbetweensupplierandmakersA review by Thomas and Griffin (1996)manufacturer may reduce the total cost in aillustrated a significant importance of supplysystem by at least 20% and as much as 100%,chain management. It has been pointed out thatdepending upon the scheduling cost functionover 11% of the U.S. Gross National Productconsidered.(GNP) is spent on non-military logistics, andTo coordinate scheduling decisions amonggreater than 30% of product prices are affecteddifferent stages is complex A decision that isby logistics expenditures. They suggested anoptimal with respect to the entire system mighturgent need for research to consider the supplynot be an optimal decision for every stagechainexplicitly to address issues at anwheneachstagehasitsownperformanceoperational level,rather than strategic, and uemeasure. The sy stem solution may adverselydetermnistic models ratherthanstochasticaffect one or morestages.The conflictsmightSarmiento and Nagi (1999) surveyed theneed to be further negotiated and may beliterature on integr ated production andresolved by providing incentives to motivatedistribution models. They pointed out thatthecoordination.Wecallthis aspectastrategiccompaniestendtoreduceinventorylevelsinissueinsupplychainschedulingAnotherordertobe competitive withthe popularity ofimportant aspect in supply chain scheduling isjust-in-timeand supplychainmanagementthe study of multi-stage schedul ingproblems.We call this aspect an operational issue.concepts. This trend creates a closer interactionbetween stages in a supply chain and increasesConsideringasupply-chain-schedulingthe practical usefulness of integrated models.problem from an operational viewpoint, weIn response to Thomas and Griffin'sassume that the sysiem-wide performance is insuggestion, attention has recently been given tothe common interestofall siages andfocus onthe study ofsupply chain management at thesolving the scheduling problems that involveoperational level, especially issues related tomore than one stage.Hence we call it logisticsproduction-distribution sy stems. Hall and Pottsscheduling(2003)first used theterm supplychainThis paper studies the coordination effectsscheduling.In supply chain scheduling thebetween stages for scheduling problems wherefocus is on the coordination of schedulingdecision-making is a two-stage process.Twodecisions. It emphasizes scheduling issues thatstages are considered as one system.Thearenotconsidered intheliteraturerelatedtosystem can bea supply chainthat linkstwoproduction-distribution sy stems as reviewed bystages,one stage representing a manufacturer,386JOURNAL oF SYST EMS SCIENCE AND SYSTEMS ENGINEERING/ Vol. 12, No. 4, December,2003

Logistics Scheduling: Analysis of Two-Stage Problems which value is added to a manufactured product. Substantial ineffectiveness may result when decision-making between different stages is poorly coordinated. Therefore, an important issue in supply chain management research is coordination between decision makers. A review by Thomas and Griffin (1996) illustrated a significant importance of supply chain management. It has been pointed out that over 11% of the U.S. Gross National Product (GNP) is spent on non-military logistics, and greater than 30% of product prices are affected by logistics expenditures. They suggested an urgent need for research to consider the supply chain explicitly to address issues at an operational level, rather than strategic, and use deterministic models rather than stochastic. Sarmiento and Nagi (1999) surveyed the literature on integrated production and distribution models. They pointed out that companies tend to reduce inventory levels in order to be competitive with the popularity of just-in-time and supply chain management concepts. This trend creates a closer interaction between stages in a supply chain and increases the practical usefulness of integrated models. In response to Thomas and Griffin’s suggestion, attention has recently been given to the study ofsupply chain management at the operational level, especially issues related to production-distribution systems. Hall and Potts (2003) first used the term supply chain scheduling. In supply chain scheduling, the focus is on the coordination of scheduling decisions. It emphasizes scheduling issues that are not considered in the literature related to production-distribution systems as reviewed by Sarmiento and Nagi (1999). Specifically, Hall and Potts reported the benefits of cooperative decision-making for scheduling in a supply chain where a supplier makes deliveries to several manufacturers, who may in turn supply several customers. They demonstrated that cooperationbetweensupplierand manufacturer may reduce the total cost in a system by at least 20% and as much as 100%, depending upon the scheduling cost function considered. To coordinate scheduling decisions among different stages is complex. A decision that is optimal with respect to the entire system might not be an optimal decision for every stage when each stage has its own performance measure. The system solution may adversely affect one or more stages. The conflicts might need to be further negotiated and may be resolved by providing incentives to motivate the coordination. We call this aspect a strategic issue in supply chain scheduling. Another important aspect in supply chain scheduling is the study of multi-stage scheduling problems. We call this aspect an operational issue. Consideringasupply-chain-scheduling problem from an operational viewpoint, we assume that the system-wide performance is in the common interest of all stages and focus on solving the scheduling problems that involve more than one stage. Hence we call it logistics scheduling. This paper studies the coordination effects between stages for scheduling problems where decision-making is a two-stage process. Two stages are considered as one system. The system can be a supply chain that links two stages, one stage representing a manufacturer; 386 JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 4, December, 2003

CHANGand LEEand the other, a distributor. It also cansituation that jobs require different amounts ofrepresent a single manufacturer,while eachstorage space during deliveryThere is limited research on problems instagerepresentsa differentdepartmentresponsible for a part ofoperations.Aproblemwhich jobs are delivered to customers inthat jointlyconsidersbothstagesinordertobatches. Several survey papers on schedulingachieve the optimal schedule is defined as aandbatchingproblemsareavailable:PottsandsystemproblemVan Wassenhove (1992), Webster and BakerTwotypesofsystemproblemsare(1995)and Potts and Kovalyov (2000).considered in this paper. The first type systemHerrmann and Lee (1993), Yuan (1996),Chenproblem, called Type-I problem, is a two-stage(1996), and Cheng, Gordon, and Kovalyovscheduling problem in which each stage is(1996) considered machine schedulingrepresented by a single machine. This problemproblems with jobs delivered in batches afteris equivalent to the classical two-machinebeing processed. Each delivery batch incurredflowshop problem.The second type, calleda certain transportation cost. However, they didType-II problem, is a problem where the firstnot consider transportation times, ie., it wasstage is represented by a single machine andassumed that deliveries can bemadethe second stage is job delivery. Type-Ilinstantaneously.Yang(2000) studied a modelsimilar to the one studied by Cheng Gordon,problems consider the integration ofproduction scheduling with delivery ofand Kovalyov (1996), but with given batchfinished products to customers. In Type-Ildelivery dates. Hall, Lesao ana and Pott (2001)problems, jobs are first processed in aanalyzed a variety of problems with differentmanufacturing system,then deliveredtothemachineenvironments wherea set of availablerespective customers. Jobs are delivered intimes, at which batches may be delivered, isbatchesbyatransporter,referredtoasfixed before the schedule is determined, Lee*"vehicle".A transportation time is associatedand Chen (2001) studied machine schedulingwith each delivery.Job completion time isproblemswithexplicittransportationdefined as the time when a job arrives at theconsiderations. Two types oftransportationcustomer. All jobs delivered in one shipment tosituations are considered in their models. Theone customer have the same completion times.first type, Type-1, involves intermediateThe system problem arises in try ingtotransportation of jobsfrom one machinetominimize a certain objective function byanother for further processing The second typefinding schedules for processing jobs in theType-2, involves the transportation provided tomanufacturing sy stem and for deliveringdeliver finished jobs to their destinations infinished jobs to the respective customers.Thewhich the manufacturing facility is aneed to make batching decisions in the secondtwo-machine flow shop. Jobs are delivered instage makes Type-I problems morebatches by transporter(s). They assumed thatcomplicated than Type-I problems. Chang andalljobs require the same physical space on theLee (2002)studied Type-1I problems under thetransporter.Both transportation capacity and387JOURNAL oF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING/ Vol. 12, No.4, December, 2003

CHANG and LEE and the other, a distributor. It also can represent a single manufacturer, while each stage represents a different department responsible for a part of operations. A problem that jointly considers both stages in order to achieve the optimal schedule is defined as a system problem. Two types of system problems are considered in this paper. The first type system problem, called Type-I problem, is a two-stage scheduling problem in which each stage is represented by a single machine. This problem is equivalent to the classical two-machine flowshop problem. The second type, called Type-II problem, is a problem where the first stage is represented by a single machine and the second stage is job delivery. Type-II problems consider the integration of production scheduling with delivery of finished products to customers. In Type-II problems, jobs are first processed in a manufacturing system, then delivered to the respective customers. Jobs are delivered in batches by a transporter, referred to as “vehicle”. A transportation time is associated with each delivery. Job completion time is defined as the time when a job arrives at the customer. All jobs delivered in one shipment to one customer have the same completion times. The system problem arises in trying to minimize a certain objective function by finding schedules for processing jobs in the manufacturing system and for delivering finished jobs to the respective customers. The need to make batching decisions in the second stage makes Type-II problems more complicated than Type-I problems. Chang and Lee (2002) studied Type-II problems under the situation that jobs require different amounts of storage space during delivery. There is limited research on problems in which jobs are delivered to customers in batches. Several survey papers on scheduling and batching problems are available: Potts and Van Wassenhove (1992), Webster and Baker (1995) and Potts and Kovalyov (2000). Herrmann and Lee (1993), Yuan (1996), Chen (1996), and Cheng, Gordon, and Kovalyov (1996) considered machine scheduling problems with jobs delivered in batches after being processed. Each delivery batch incurred a certain transportation cost. However, they did not consider transportation times, i.e., it was assumed that deliveries can be made instantaneously. Yang (2000) studied a model similar to the one studied by Cheng, Gordon, and Kovalyov (1996), but with given batch delivery dates. Hall, Lesaoana and Pott (2001) analyzed a variety of problems with different machine environments where a set of available times, at which batches may be delivered, is fixed before the schedule is determined. Lee and Chen (2001) studied machine scheduling problemswithexplicittransportation considerations. Two types of transportation situations are considered in their models. The first type, Type-1, involves intermediate transportation of jobs from one machine to another for further processing. The second type, Type-2, involves the transportation provided to deliver finished jobs to their destinations in which the manufacturing facility is a two-machine flow shop. Jobs are delivered in batches by transporter(s). They assumed that all jobs require the same physical space on the transporter. Both transportation capacity and JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 4, December, 2003 387

Logistics Scheduling:Analysis of Two-Stage Problemstransportation times are considered in theirpolicy in the second stage (stage 2) firstmodels. Our Type-II problems involved afollowed by the first stage (stage 1). The firstspecial Type-2 transportation as thealternative is defined as Forward Approachmanufacturing facil ity is a single machine shopand the second alternative as BackwardHurinkandKnust(2001)independentlyApproach.Furthermore,wedefineSystemstudied robotic operations in the manufacturingApproachastheprocedureto solveasystemenvironment, which is an intermediate type ofproblem by jointly considering the two stages.transportation (Type-1 transportat ion asIn the System Approach, each stage has thedefined by Lee and Chen (2001). Theycomplete information on the activities operatedassumed there is only one transporter availableat the other stage and may adjust its scheduleto carry each single job and that the return timeaccordingly in order to benefit the system. Theof the transporter is zero.optimal solution obtained by usingthe SystemIn practice, at times, there may be littleApproach gives us the optimal solution to thecoordination between the two stages due to (0)systemproblem. In the Forward Approach, wethe lack of channels that allow decision makersassume that stage 1I solves its problem with noat the two stages to cooperate, and/or (i) theknowledge of the activities performed by stageoptimal solutiontothesystemproblemistoo2, and stage 2 solves its problem bydifficult (or costly)to achieve (for example,aconsideringboththeinformationprovidedbyproblem that has been classified as stronglystage I (completion time of each job at stage 1,NP-hard), Example () happens quiteequivalently,the arrival time of each job atcommonlyinpracticebasedonourexperiencestage2)andtherequirementsfromitsownwith industry applications.One stagefocusesactivities.This implies that the informationon its own operations and has limitedflowgoesfrom stageI to stage 2onlyinformation of the activities performed bySimilarly,it is assumed that the informationflow only goes from stage 2 to stage 1 wheneither the downstream or the upstream stage.Example (i) is due to the complexity of theusing the Backward Approach.In contrast tosolution procedure. The trade-off between thethe Forward and Backward Approaches, thetime complexity and the solution quality is theinformation flow goes interactively betweenmain concern.the two stages when usingthe SystemWhen there is dificulty to solve two stagesApproach.jointly, in industry practice, the decisionWhen decision makers at two stages makemaking is usually done sequentiallydecisionslocally withoutconsideringFurthermore, it is possible that the decisionconsequencestotheentiresystem,made first in one stage will provide theineffectiveness may result even when eachinformation or constraints tothe other stage.stage optimally solves its single-stage problem.There are two alternatives: (i) dec ide the policyGiven an objective function for a particularin the first stage (stage 1), followed by thesystem problem, ineffectiveness may besecond stage (stage 2), and (ii) decide theevaluated by comparing the solution value388JOURNAL oF SYST EMS SCIENCE AND SYSTEMS ENGINEERING/ Vol. 12, No. 4, December,2003

Logistics Scheduling: Analysis of Two-Stage Problems transportation times are considered in their models. Our Type-II problems involved a special Type-2 transportation as the manufacturing facility is a single machine shop. Hurink and Knust (2001) independently studied robotic operations in the manufacturing environment, which is an intermediate type of transportation (Type-1 transportation as defined by Lee and Chen (2001)). They assumed there is only one transporter available to carry each single job and that the return time of the transporter is zero. In practice, at times, there may be little coordination between the two stages due to (i) the lack of channels that allow decision makers at the two stages to cooperate, and/or (ii) the optimal solution to the system problem is too difficult (or costly) to achieve (for example, a problem that has been classified as strongly NP-hard). Example (i) happens quite commonly in practice based on our experience with industry applications. One stage focuses on its own operations and has limited information of the activities performed by either the downstream or the upstream stage. Example (ii) is due to the complexity of the solution procedure. The trade-off between the time complexity and the solution quality is the main concern. When there is difficulty to solve two stages jointly, in industry practice, the decision making is usually done sequentially. Furthermore, it is possible that the decision made first in one stage will provide the information or constraints to the other stage. There are two alternatives: (i) decide the policy in the first stage (stage 1), followed by the second stage (stage 2), and (ii) decide the policy in the second stage (stage 2) first, followed by the first stage (stage 1). The first alternative is defined as Forward Approach and the second alternative as Backward Approach. Furthermore, we define System Approach as the procedure to solve a system problem by jointly considering the two stages. In the System Approach, each stage has the complete information on the activities operated at the other stage and may adjust its schedule accordingly in order to benefit the system. The optimal solution obtained by using the System Approach gives us the optimal solution to the systemproblem. In the Forward Approach, we assume that stage 1 solves its problem with no knowledge of the activities performed by stage 2, and stage 2 solves its problem by considering both the information provided by stage 1 (completion time of each job at stage 1, equivalently, the arrival time of each job at stage 2) and the requirements from its own activities. This implies that the information flow goes from stage 1 to stage 2 only. Similarly, it is assumed that the information flow only goes from stage 2 to stage 1 when using the Backward Approach. In contrast to the Forward and Backward Approaches, the information flow goes interactively between the two stages when using the System Approach. When decision makers at two stages make decisionslocallywithoutconsidering consequencestotheentiresystem, ineffectiveness may result  even when each stage optimally solves its single-stage problem. Given an objective function for a particular systemproblem, ineffectiveness may be evaluated by comparing the solution value 388 JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 4, December, 2003

CHANGand LEEobtained from solving the stages separatelymight be some trade-off, in terms of the timewith the optimal solution to the systemcomplexity and the solution quality,betweenproblem derived from jointly consideringtwosolving the system problem optimally andsolving it by either the Forward or thestages.FromtheoptimizationperspectiveBackward Approach.This paper attemptstoineffectiveness is commonlyreferredastheerrorresulting fromfailuretooptimally solveaddress that issue.the sy stem problem. The error depends on theThe remainder of the paper is organized assystem problem type, as well as the objectivefollows. Section 2 defines the studied problemsas well as the required notations.From Sectionfunction considered.Forsome systemproblems, the error might be small, and3 to Section 5, three two-stage problems aresubsequentlycan be tolerated in order todiscussed, one per section. Sections 3 and 4facilitate the solution procedure. However, forconsider Type-I problems, with the objective ofsome problems, there is cause for greatlyminimizing the makespan in Section 3 andincreased savings if participants agreeto aminimizingthesum oftotal completion timesdegree of coordination.in Section 4. Section 5 considers Type-IIEssentially,the Forward and BackwardproblemswiththeobjectiveofminimizingtheApproaches can beviewed as heuristics tomaximum lateness. In each section,thesolveoneparticularsystemproblem.ThisproblemisdiscussedintheorderoftheSystem,paper studies the effectiveness of these twothe Forward and the Backward Approachesapproaches by investigating the attainablefollowed by a brief discussion.Worst-casesolution quality as compared to the optimalanalysis is employedto evaluate each approach.solutionwithrespecttothesystemproblemSection6containsaconclusionaswell asThe effect of coordination is quantified by thesuggestions for future work.deviation from the optimal solution value ofthe system problem when solving two stagesbyeithertheForward ortheBackwardApproach. A worst-case analysis is employedto analyze the level of ineffectiveness when thedecisions at each stage are not fullycoordinated. This research emphasizes derivingthe worst-case performance for the situation inwhich the two stages solve their respectiveproblems opt imally.Notethat the errorgenerated by using either the Forward or theBackward Approach may not represent2.Problem Statement andprecisely thetrue benefit, it does demonstrate aNotationpotential cost savingfor consideringbothstages simultaneously.Note also that thereThe problem is defined in detail along withthe required notation in the following sections.2.1SystemProblems(i)Type-I problem:each stage is represented bya single machineThere are two machines, Mi and M, thatare continuously availablefrom time zeroonwardsforprocessingasetofnindependentjobs N= [J, Jh, ., Ja). Each machine canhandle no more than one job at a time. Eachjob consists ofachain oftwooperations.The389JOURNAL oF SYSTEMS SCIENCEAND SYSTEMS ENGINEERING/Vol. 12,No.4, December,2003

CHANG and LEE obtained from solving the stages separately with the optimal solution to the system problem derived from jointly considering two stages. From the optimization perspective, ineffectiveness is commonly referred as the error resulting from failure to optimally solve the system problem. The error depends on the systemproblem type, as well as the objective function considered. For some system problems, the error might be small, and subsequently, can be tolerated in order to facilitate the solution procedure. However, for some problems, there is cause for greatly increased savings if participants agree to a degree of coordination. Essentially, the Forward and Backward Approaches can be viewed as heuristics to solve one particular system problem. This paper studies the effectiveness of these two approaches by investigating the attainable solution quality as compared to the optimal solution with respect to the systemproblem. The effect of coordination is quantified by the deviation from the optimal solution value of the system problem when solving two stages by either the Forward or the Backward Approach. A worst-case analysis is employed to analyze the level of ineffectiveness when the decisions at each stage are not fully coordinated. This research emphasizes deriving the worst-case performance for the situation in which the two stages solve their respective problems optimally. Note that the error generated by using either the Forward or the Backward Approach may not represent precisely the true benefit, it does demonstrate a potential cost saving for considering both stages simultaneously. Note also that there might be some trade-off, in terms of the time complexity and the solution quality, between solving the systemproblem optimally and solving it by either the Forward or the Backward Approach. This paper attempts to address that issue. The remainder of the paper is organized as follows. Section 2 defines the studied problems as well as the required notations. From Section 3 to Section 5, three two-stage problems are discussed, one per section. Sections 3 and 4 consider Type-I problems, with the objective of minimizing the makespan in Section 3 and minimizing the sum of total completion times in Section 4. Section 5 considers Type-II problems with the objective of minimizing the maximum lateness. In each section, the problem is discussed in the order of the System, the Forward and the Backward Approaches, followed by a brief discussion. Worst-case analysis is employed to evaluate each approach. Section 6 contains a conclusion as well as suggestions for future work. 2. Problem Statement and Notation The problem is defined in detail along with the required notation in the following sections. 2.1 System Problems (i) Type-I problem: each stage is represented by a single machine There are two machines, M1 and M2, that are continuously available from time zero onwards for processing a set of n independent jobs N = {J1, J2, ., Jn}. Each machine can handle no more than one job at a time. Each job consists of a chain of two operations. The JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 4, December, 2003 389

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

CHANGand LEE3F+that Cmax / Cmax 82. Furthermore, it isstage 2 sequenced jobs based by solvingstraightforward to showthat the bound is tight.sub-BS2. After passed the result to stage 1 andstage1has then sequenced the jobs, stage2Back ward Appr oach:may either stick in its original sequence or useUsingtheBackwardtheApproach,first-come first-serve policy.In either case, wesub-problem at stage 2, sub-BS2, is consideredalwaysshowthattheworst-casecan中first. Sub-BS2 may be defined as a singleperformanceratio resultingfrom the Backwardmachine problem with the objective ofApproach is equal to 2.minimizing makespan. The job processingtimes considered in sub-BS2 are pij, .4.ProblemF2//ECiSub-BS2 can be optimized by any sequence.Given an optimal sequence for sub-BS2, set4.1SystemApproach(C μ BS 2)* pi) as the due datethe starting timeGarey, Johnson and Sethi (1976) show that(d gBsI) for Jin sub-BS1. At stage 1, theF2] [Cjis NP-hard in the strong sense. Thisproblem was first solved by Ignall and Schrageobjective is to process jobs in order to meet(1965)using a branch-and-bound algorithm.these due dates set by stage 2. Hence, theConway,Maxwell and Miller (1967) showedthat it is sufficienttooptimizeoverallsub-problem considered at stage I, sub-BS1,permutation schedules withno idletime on Mimay be defined as a single machine problembeforeprocessingbegins.Apermutationschedule is a schedule in which both machineswiththeobjectiveofminimizingthemaximumprocess jobs in the same order,one ofthelateness.Sub-BS1maybeoptimizedbyapermutations ofthe n jobs. Gorzalez and Sahni(1978)provided a heuristic for the m-machinespecialization of Lawler's method,known asproblem and showed that the worst-caseJackson's rule (Jackson, 1955):schedule theperformance ratio is m. For the two-machineproblem, Gonzalez and Sahni's heuristicjobs in the order of nondecreasing due dates.proceeds by re-indexing jobs in theThis rule also isreferred to as the earliest duenondecreasingorder of (plj+p),sttlingtiesarbitrarily,and by subsequently schedulingdate first (EDD) rule. Due to the reversibilityjobs in that order on Mi and M2 such thatofa two-machine flowshopproblem, we canunnecessary machine idle time is avoided.Vansee that the error bound is still equal to2 (ie.deVelde(1990)proposedabranch-and-boundalgorithm based on Lagrangian relaxation and38*Cmax/ Cmax2), and it can be shown that theproved that the lower-bound generalizes andbound is tight.dominates the bounds proposed by Ignall andSchrage.Computational testing of Van deNote tha sub-BS1 is defined as a 1I |LmaxVelde's optimizat ion algorithm on problems ofproblem in the Backward Approach describedabove. In fact, there is more than one way todefine sub-BS1. For example, we may definesub-BS1 as a single machine problem with theobjective ofminimizing the total lateness, orminimizing the number of tardy jobs. In such acase, another al gorithm will optimize sub-BS1.Also note that, in the Backward Approach393JOURNAL oF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING/Vol. 12, No. 4, December, 2003

CHANG and LEE 3F*that Cmax / Cmax  2. Furthermore, it is straightforward to show that the bound is tight. stage 2 sequenced jobs based by solving sub-BS2. After passed the result to stage 1 and stage 1 has then sequenced the jobs, stage 2 may either stick in its original sequence or use first-come first-serve policy. In either case, we can always show that the worst-case performance ratio resulting from the Backward Approach is equal to 2. Back ward Approach: Using the Backward Approach, the sub-problem at stage 2, sub-BS2, is considered first. Sub-BS2 may be defined as a single machine problem with the objective of minimizing makespan. The job processing times considered in sub-BS2 are p2j,   Sub-BS2 can be optimized by any sequence. Given an optimal sequence for sub-BS2, set the starting time ( C (j BS 2)* – p2j) as the due date ( d (j BS1) ) for Jj in sub-BS1. At stage 1, the objective is to process jobs in order to meet these due dates set by stage 2. Hence, the sub-problem considered at stage 1, sub-BS1, may be defined as a single machine problem with the objective of minimizing the maximum lateness. Sub-BS1 may be optimized by a specialization of Lawler’s method, known as Jackson’s rule (Jackson, 1955): schedule the jobs in the order of nondecreasing due dates. This rule also is referred to as the earliest due date first (EDD) rule. Due to the reversibility of a two-machine flowshop problem, we can see that the error bound is still equal to 2 (i.e. 3B*Cmax / Cmax  2), and it can be shown that the 4. Problem F2| |ΣCj 4.1 System Approach Garey, Johnson and Sethi (1976) show that F2| |ΣCj is NP-hard in the strong sense. This problem was first solved by Ignall and Schrage (1965) using a branch-and-bound algorithm. Conway, Maxwell and Miller (1967) showed that it issufficient to optimize over all permutation schedules with no idle time on M1 before processing begins. A permutation schedule is a schedule in which both machines process jobs in the same order, one of the permutations of the n jobs. Gonzalez and Sahni (1978) provided a heuristic for the m-machine problem and showed that the worst-case performance ratio is m. For the two-machine problem, Gonzalez and Sahni’s heuristic proceeds by re-indexing jobs in the nondecreasing order of (p1j + p2j), settling ties arbitrarily, and by subsequently scheduling jobs in that order on M1 and M2 such that unnecessary machine idle time is avoided. Van de Velde (1990) proposed a branch-and-bound algorithm based on Lagrangian relaxation and proved that the lower-bound generalizes and dominates the bounds proposed by Ignall and Schrage. Computational testing of Van de Velde’s optimization algorithm on problems of bound is tight. Note that sub-BS1 is defined as a 1| |Lmax problem in the Backward Approach described above. In fact, there is more than one way to define sub-BS1. For example, we may define sub-BS1 as a single machine problem with the objective of minimizing the total lateness, or minimizing the number of tardy jobs. In such a case, another algorithm will optimize sub-BS1. Also note that, in the Backward Approach, JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 4, December, 2003 393

LogisticsScheduling:AnalysisofTwo-StageProblemsup to 20 jobs is discussed. Hoogeveen andpermitted and jobs may beprocessed in theKawaguchi(1999) analyzed the worst-casepre-empt resume mode, the shortest-remainingbehavior of the heuristic presented by-processing-time (SRPT) rule is optimalGonzalez and Sahni(1978) for the m-machine(Schrage, 1968). According to the SRPT rule,problemandshowedthatinatwo-machinewhenajobisselectedfromjobs inqueue,thecase,theworst-caseperformanceratioisequaljob with the smallest remaining processingtime is chosen. In addition, an arriving jobto 2β/(a+ ?), where(and ? denote thepre-empts the job being processed if theminimal and maximal processingtimes of allprocessingtimeof thenew arrival is smallerthe operationsthan the remaining processing time of the joboccupy ing the machine. The non-preemptversion of the SRPT rule is used as a heuristicto solve sub-FS2.Theorem1Zarn/Z-n and thebound is tight.4.2ForwardApproach:F2/-ZCUsing the Forward Approach, thesub-problem at stage I may be defined as:$sub-FS:a single machine problem withthe objectiveof minimizing the sum of jobProof. For the job that is scheduled in the jthcompletion times."position in an optimalsolution,letpiyiand-Input: a set of jobs with processing times"p2,ljdenotethe processing times on Miandpli, p.M2 of that job, respectively, and Crn be the(FSD(().n=IC)- Solution: minpi,Fiandcompletion time. Likewise, letSub-FS1optimizedbythemaybeArp2,/1and Ci4/F denote the correspondingshortest-processing-time (SPT) rule: sequencetimes for the job that is scheduled in the jiththe jobs in the order of nondecreasingprocessingtimes (pij,).Givena sequenceposition by using the Forward Approach.that is optimal with respect to sub-FS1, the jobGiven the heuristic solution, for each job in the(CuFsi)*) becomes the releasecompletion timejth position,thereexists onejob,k,suchdate (rAFS2)for Jjin sub-FS2. Therefore, theK44FC(4/F= i=1p1,[月+-Now,that2,:11sub-problem considered at stage 2 may beconsider the completion time of the jobdefined as:scheduled in the jth position in an optimal sub-FS2:a single machine problem withsolution tothe sy stem problem. We can seethe objective of minimizing the sum of jobkthatLetcompletion times while jobs have unequal+品=plows tha=C9release dates.=(X=1 X+=p2JJ-Input: a set of jobs withprocessing times+ p2,1)p2j and releasedatesrFs2),(rFs2)is* 4Let xI4jF=isip, it can be seenthataobtained from solving sub-FSI).Z4FH==1CF==(X4F+，4FP210)-Solution:minn=ICuFS2)(()Note that sub-FS2 is NP-hard in the strong4F= n=I X[4jFsense (Lenstra et al., 1977). If pre-emption is+n= j=k+1 p2[1 V394JOURNAL oF SYST EMS SCIENCE AND SYSTEMS ENGINEERING/ Vol. 12, No. 4, December,2003

Logistics Scheduling: Analysis of Two-Stage Problems up to 20 jobs is discussed. Hoogeveen and Kawaguchi (1999) analyzed the worst-case behavior of the heuristic presented by Gonzalez and Sahni(1978) for the m-machine problem and showed that in a two-machine case, the worst-case performance ratio is equal to 2β/(α +  where  and  denote the minimal and maximal processing times of all the operations. 4.2 Forward Approach: F2|→|ΣCj Using the Forward Approach, the sub-problem at stage 1 may be defined as:  sub-FS1: a single machine problem with the objective of minimizing the sum of job completion times. - Input: a set of jobs with processing times p1j,   - Solution: min Sub-FS1 may  ( FS 1)( ) .n 1 C jj permitted and jobs may be processed in the pre-empt resume mode, the shortest-remaining -processing-time (SRPT) rule is optimal (Schrage, 1968). According to the SRPT rule, when a job is selected from jobs in queue, the job with the smallest remaining processing time is chosen. In addition, an arriving job pre-empts the job being processed if the processing time of the new arrival is smaller than the remaining processing time of the job occupying the machine. The non-preempt version of the SRPT rule is used as a heuristic to solve sub-FS2. Theorem 1 Z4Fh *  n and the bound is tight. Proof. For the job that is scheduled in the jth *position in an optimal solution, let p1,[ j ] and *p2,[ j ] denote the processing times on M1 and M2 of that job, respectively, and C[*j ] be the by the completion time. Likewise, let 4p1,[Fj ] and 4Fp2,[ j ] and C[4jF denote the corresponding] be optimized shortest-processing-time (SPT) rule: sequence the jobs in the order of nondecreasing processing times (p1j,   Given a sequence that is optimal with respect to sub-FS1, the job completion time date ( r j( FS 2) ) ( C (j FS1)*) becomes the release for Jj in sub-FS2. Therefore, the times for the job that is scheduled in the jth position by using the Forward Approach. Given the heuristic solution, for each job in the jth position, there exists one job, kj, such that 44FC[4jF  i j1 p1,[F]  ij k p2,[i ]]i j k . Now, sub-problem considered at stage 2 may be defined as:  sub-FS2: a single machine problem with the objective of minimizing the sum of job completion times while jobs have unequal release dates. - Input: a set of jobs with processing times p2j and release dates r j( FS 2) ,   ( r j( FS 2) is obtained from solving sub-FS1). - Solution: min n 1C (j FS 2) ( ) .j  Note that sub-FS2 is NP-hard in the strong sense (Lenstra et al., 1977). If pre-emption is consider the completion time of the job scheduled in the jth position in an optimal solution to the system problem. We can see that k*x[*j ]  i j1 p1,[i ] . **n 1 ( x[ j ]  p2,[ j ] )j k *C[*j ] i j1 p1,[i ]  ij k k *p2,[i ] . It follows that n 1C[*j ] j  n 1 x[*j ]  n 1 p2, j .jj j 1 Let 4Let x[4jF  i j1 p1,[F] , it can be seen thati] Z 4FH = n 1C[4jF  n 1 ( x[4jF  ij kjj]] j 1 4Fp2,[i ] ) 4F n 1 x[4jF  n 1ij k 1 p2,[i ] .jj]j 394 JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 4, December, 2003