Seite - 118 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 50 where thevariablesxif>0, f=1,. . . , |F|, i=1,. . . , |J|arecontinuousandrepresent thestart times ofeachoperationofeachorder;andvariables ck∈{0,1}, k=1,. . . ,KareBooleanandrepresent the positionofeachcompetingoperationamongothercompetitors foreachresource. 2.3. CombinatorialOptimizationTechniques From themathematical point of view, the resulting basic problem setting belongs to linear programmingclass. Thevariables ck∈{0,1}, k=1,. . . ,K formacombinatorial setof subordinate optimization problems [8]. However, wemust suppress that the combinatorial set ck ∈ {0,1}, k=1,. . . ,K, isnot fullas thesequenceofoperationswithineachorder isdictatedbymanufacturing procedure.Consequently, thenumberofcombinations is restrictedonly to thosevariantswhenthe operationsofdifferent orders tradeplaceswithout changing their queuewithinoneorder. Letus researchpossiblewaystosolvethegivencombinatorialsetofproblems. Inthisarticle, theoptimization willbeconductedwith“makespan”criterionformalizedwith the formula: |F| ∑ f=1 x|J|f →min. 2.3.1. EnumerationandBranch-and-BoundApproach Enumeratingthefullsetofcombinationsforallcompetingoperations isanexerciseofexponential complexity [9].However,aswehavementionedabovethenumberofcombinations inconstraint (3) is restricteddue toother constraints (2) and (1). Theprecedencegraphconstraint (1) excludes the permutationsofcompetingoperationswithinoneordermakingthelinearproblemsettingnon-feasible forcorrespondingcombinations. Thewayweenumerate thecombinationsandchoose thestarting pointofenumerationalso influences theflowofcomputationssignificantly. Thecommonapproachto reducingthenumberof iterations inenumeration is todetect the forbiddenareaswhere theoptimal solutionproblemdoesnotexist (e.g., theconstraints formanon-feasibleproblemormultiplesolutions exist). Themostwidelyspreadvariantof the techniquedescribedisbranch-and-boundmethod[10] anditsdifferentvariations. Let us choose the strategy of enumerating permutations of operations in such away that it explicitlyandeasilyaffordstoapplybranch-and-boundmethod. Thestartingpointof theenumeration willbe themostobviouspositioningoforders inarowasshowninFigure2.Westart fromthepoint where theproblemisguaranteedtobesolvable—whenallordersareplannedinarow—whichmeans that thefirstoperationof thenextorder startsonlyafter the lastoperationof thepreviousorder is finished. If theprecedinggraphiscorrectandtheresourcesareenoughthatmeans thesingleorder canbeplacedontheresources thatare totally free (theproblemissolvable—wedonotconsider the unpractical casewhenthegraphand/orresourcesarenotenoughto fulfillasingleorder). Infeasibility herecanbereachedonly in thecasewhenwestartmixingtheorders. Thisguarantees that the linear programmingproblemissolvable,however, thiscombination is far frombeingoptimal/reasonable. Figure2. Initial state: allordersareplaced inarow. 118