Seite - 125 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 50 4.Discussion Analyzing thecomputational experiment result,wecome toaclassical researchoutcome that tosolve theglobaloptimizationproblemeffectivelyweneedtofindamorecomputationallycheap algorithmthatgivesasolutioncloser toglobaloptimum.Letus tryseveral standardapproaches to improvethesolutionwithnon-exponentialalgorithmextensions. 4.1. RandomSearchasanEffort toFindGlobalOptimum Asmentioned above, the gradient algorithm, beingmore effective from the computational complexitypointofview,affords tofindonly local suboptimalsolutions [12].Atypicalextensionto overcomethis restrictionwouldberandomsearchprocedure. Themain ideaof thismodification is to iterategradient searchmultiple timesgoingout fromdifferent startingpoints [13]. Incase thestarting pointsaregeneratedrandomlywecanassumethat themorerepeatinggradientsearcheswedothe higher theprobabilityoffindingaglobaloptimumweachieve. Therewassomeresearchconducted in thisareawhoseoutcomerecommendshowmanystartingpoints togenerate inorder tocover the problem’s acceptance regionwithhighvalueofprobability [14]. According to [14] the acceptable numberofstartingpoints iscalculatedas N ·dim(Φ), whereN = 5. . .20, anddim(Φ) is thedimensionality of optimizationproblembeing solved, i.e., forourcase this is thenumberofall competingoperationsofallordersonall resources. Theresultof applyingrandomsearchapproach is represented inTable2. Themainbarrier for implementingtherandomsearchprocedurefor thecombinatorialscheduling problemisgeneratingenoughfeasibleoptimizationstartingpoints. Aswecansee fromtheresults inTable 2, numberof failures to generate feasible startingpoint ismuchhigher than thequantity of successful trials. Leaningupon the results of enumerationalgorithm inTable 1wecanassume that the tolerance regions for optimization problem (1)–(3) are very narrow. Even from the trial example inTable1wesee that thenumberof feasible iterations (25)collect less than10percentofall possiblepermutations (318)which leavesusvery lowprobabilityofgettinga feasible initialpoint for furthergradientoptimization. Thus,wecanmakeaconclusionthat ‘pure’ implementationof random searchprocedurewillnotgiveahugeeffectbutshouldbeaccompaniedwithsomeanalyticprocessof choosingfeasible initialpointsofoptimization. Suchaproceduremaybebasedonnon-mathematical knowledgesuchas industryormanagementexpertise. Fromourunderstanding, thisquestionshould be investigatedseparately. 5.Conclusions Researchofacontinuous-timeschedulingproblemisconducted.Weformalizedthescheduling problem as a combinatorial set [8] of linear programming sub problems and evaluated typical computationalprocedureswith it. Inaddition to theclassicalandestimatedresultingconflictbetween the“complexity”and“locality”ofoptimizationalgorithmswecametotheconclusionthat theclassical approachof randomization isunhelpful in termsof improvingthe locally foundsuboptimalsolution. The reasonhere is that the schedulingprobleminsetting (1)–(3)hasaverynarrowfeasibilityarea whichmakes it difficult to randomlydetect a sufficientnumberof startingpoints for further local optimization. Theefficiencyof randomsearchmightbe increasedby introducingamartial ruleor procedureoffindingtypical feasiblestartingpoints. Theothereffectiveglobaloptimizationprocedures arementionedinaveryshort formandare left for furtherauthors’ research. Theyare: 125