Seite - XI - in Algorithms for Scheduling Problems

developed and applied to resolve the conflicts by re-timing, re-ordering, and locally re-routing the trains.Apartof theSouthernSwedishrailwaynetwork fromthecenterofKarlskrona toMalmo¨city is considered for anexperimental performanceassessmentof the approach. Acomparisonwith the correspondingmixed-integerprogramformulation, solvedby thecommercial state-of-the-art solver Gurobi, isalsomadetoassess theoptimalityof thegeneratedsolutions. Chapter 7dealswithageneralizationof the job shopproblem. It is devoted toa formalizationof theresource-constrainedprojectschedulingproblem(RCPSP) intermsofcombinatorialoptimization theory. ThetransformationoftheoriginalRCPSPintoacombinatorialsettingisbasedoninterpreting eachoperation as an atomic entity that has adefinedduration andhas to reside on the continuous timeaxis,meetingadditional restrictions. Thesimplest caseof continuous-timeschedulingassumes a one-to-one correspondence between the resources and operations and corresponds to a linear programming problem setting. However, real scheduling problems includemany-to-one relations that lead to an additional combinatorial component in the formulation of the RCPSP due to the competition of the operations. The authors investigate how to apply several typical algorithms to solve the resulting combinatorial optimization problem: an enumerative algorithm including a branch-and-boundmethod,agradientalgorithm,orarandomsearchtechnique. Thenext threechaptersdealwithcomplexmanufacturingsystemsandsupplychains, respectively. Chapter 8 considers a number of geographically separated markets, with different demand characteristics fordifferentproducts that shareacommoncomponent. Thiscommoncomponentcan either bemanufactured locally in each of themarkets or transportedbetween themarkets to fulfill thedemand.However,finalassembliesare localizedto therespectivemarkets. Thedecision-making challenge iswhether tomanufacture the commoncomponent centrally or locally. To formulate this problem, a newsvendormodeling-based approach is considered. The developedmodel is solved usingaFrank–Wolfe linearizationtechniquealongwithBenders’decompositionmethod. The authors of Chapter 9write that the current literature presents optimal control computational algorithmswithregard tostate, control, andconjunctivevariable spaces. Theauthorsof this chapter firstanalyze theadvantagesand limitationsofdifferentoptimal control computationalmethodsand algorithmswhich can beused for short-term scheduling. Second, theydevelop an optimal control computational algorithm that allows the optimal solution of short-term scheduling. Moreover, a qualitativeandquantitativeanalysisof theschedulingproblemarising in themanufacturingsystem ispresented. Chapter 10 is devoted to a graphmodel of hierarchical supply chains. The goal is tomeasure the complexity of the links betweendifferent components of the chain (e.g., between the principal equipment manufacturer and its suppliers). The information entropy is used as a measure of knowledge about the complexity of shortages and pitfalls in relationship to the supply chain componentsunderuncertainty. Theconceptof conditional entropy is introducedasageneralization of the conventional entropy. An entropy-based algorithm is developed, providing an efficient assessmentof thesupplychaincomplexityasa functionof thesupplychainsize. Finally,Chapter11dealswithan imageprocessingwork-flowschedulingproblemonamulti-core digital signalprocessor cluster. It presents anexperimental studyof scheduling strategies including task labeling, prioritization, and resource selection. The authors apply the above strategies as executing theLigoandMontageapplication. A joint analysisof three conflictinggoalsbasedon the performancedegradationprovidesaneffectiveguideline forchoosingabetter strategy.Acasestudy is discussed. The experimental results demonstrate that a pessimistic scheduling approachworks xi