Seite - 134 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 54 π= n ∑ i=1 πj= n ∑ j=1 n ∑ i=1 Ajx2ij+2 n ∑ j=1 n ∑ i=1 n ∑ k=i+1 Ajxijxkj+ n ∑ j=1 n ∑ i=1 xij(Cmi+Ctij+BBj) (5) Thus,wehavetheobjective functiontomaximize the totalprofit:maxπ This is subject tocapacityconstraints ineachplantaswellaseachmarket for thefinalassembly, Plantcapacityconstraint: n ∑ j=1 xij≤Kmi ∀i=1. . .n FinalAssemblycapacityconstraint: n ∑ j=1 xij≤Kaj ∀j=1. . .n Theformulation inEquation(5) ishavingaquadraticobjective functionandlinearconstraints. WeapplyFrankWolfe’s sequential linearizationmethod,andBender’sDecompositionmethodisused fordecomposing the linearproblemwithin theFrankWolfe’smethod. Stepwiseprocedure for the integratedmethodology isgivenas follows: Consider theproblemto, Minimizeπ(x) subject tox∈S; whereS⊂Rn Let, f isacontinuouslydifferentiable function. Step0. Choosean initial solution,x0∈S.Letk=0.Hereanarbitrarybasic feasiblesolution ischosen, that is, anextremepoint. Step1.Determineasearchdirection,pk. In theFrankWolfealgorithmpk isdeterminedthroughthe solutionof theapproximationof theproblem(1) that isobtainedbyreplacingthe function f with its first-orderTaylorexpansionaroundxk. Therefore, solve theproblemtominimize: zk(x)=π(xk)+∇π(xk)T(x−xk) Subject tox∈S ThisisaLinearProgramming(LP)problem. Inlargescaleproblemsthiswouldbecomputationally complex, andwould require to bedecomposed into smaller problemswhich canbe solved easily. Henceweapply theBender’sdecompositionmethodat thispoint tosolve theLP. Step2. ThusbyBender’sdecompositionmethodx* is obtainedasanoptimal solution togradient equation. Thesearchdirection is pk= x∗−−xk, that is, thedirectionvector fromthefeasiblepointxk towards theextremepoint. Step3.Astep length isdeterminedandrepresentedasαk, suchthat f(xk+αkpk) < f(xk). Step4.Newiterationpoint is foundoutusingxk+1= xk+αkpk. Step5.Check if stoppingcriteria is reached,elsegotoStep1. 3.1. IllustrationofMethodologyontheProblem Theformulation inEquation(5)canberewritten inmatrix formatas: Max xTQx + bTx + c s.t Ax ≤ K whereQ, b, c,AandK are appropriatelydefineddependingon the sizeof theproblem. With this notationonthe formulation, theapplicationof integratedFrankWolfe’sandBender’sdecomposition methodasapplied to themulti-marketnetworkdesignproblemunderuniformdemanduncertainty is depicted in theflowchart, inFigure3. 134