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