Seite - 160 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 57 Havingcalculatedoptimalsolutionsforseveralpoints, it ispossible tovalidate thedecisiontouse eitherdynamicorheuristicplanningalgorithms. InFigure4, therelativesolutionqualitygainedby theoptimalcontrolalgorithmDYNisassumedtobe100%.Therelativequality indexof theheuristic solutions is calculated as a fraction of the optimal one, i.e., it can be observed that, in the case of anumberofprocessesbetween10and12, thequalityof theheuristicandoptimalsolutionsdoesnot differ bymore than4%. In area 2, theDYNalgorithm ispreferable to theheuristics. If still using theheuristics, theFIFOalgorithmispreferable to theLast-in-first-outone. The largestbenefit from using theDYNalgorithmisachieved inarea3. In thisarea, theLIFOalgorithmispreferable to the FIFOalgorithm. Finally, theproposedmodelandalgorithmallowsfor theachievementofbetter results inmany cases in comparisonwith heuristics algorithms. However, this point is not themost important. Themost importantpoint is that thisapproachallows the interlinkingofplanningandscheduling modelswithinanadaptationframework. Therefore, thesuggestedresultsareimportant intheIndustry 4.0domain.Hence, theproposedmodelingcomplexdoesnotexistasa“thing in itself”butworks in the integrateddecision-supportsystemandguides theplanningandschedulingdecisions indynamics ontheprinciplesofoptimizationandadaptation. 6.Conclusions Optimalcontrolsas functionsof thesystemandcontrol stateallowfor thegenerationofoptimal decisions in consideration of a system’s evolution in time in thepresence of perturbationswhich result indifferent systemstates.Optimalcontrolapproaches takeanotherperspectiveasmathematical programmingmethodswhichrepresentschedulesas trajectories. Computationalalgorithmswithregardtostate, control, andconjunctivevariablespacesexist in the literature.Wehavedemonstrated that theadvantagesofoptimalcontrolmethodsareapplicable to the treatmentof largescaleproblemswithcomplexconstraints, theconsiderationofnon-stationary process executiondynamics, the representation indifferential equations of complex interrelations betweenprocessexecution,capacityevolution,andmachinesetups. Inaddition, theadvantagesof optimal control also includeaccuracyof continuous timeandaccuratepresentationof continuous flows(e.g., inprocess industryorenergysystems)with thehelpofcontinuousstatevariables. An important observation is that schedule presentation in terms of optimal controlmakes it possible to incorporate therichvarietyofcontrol theoreticaxiomswithregardto feedbackadaptive control (mostlyapplied in the frameworkofproduction-inventorycontrolmodels)aswellas theuse ofcontrol toolsofqualitativeperformanceanalysis, suchasattainable (reachable) sets. Limitations of control applications includeconceptual andalgorithmic restrictions suchas continuousprocess applications and specific (i.e., non-generalized) forms of constructing algorithmswith necessary requirementsconcerningoptimality, convergence,andnumerical stability. In this study,we exemplifiedanapplicationof optimal control tomanufacturing scheduling. Fundamentally, this application dynamically decomposes the assignment matrix in time using differentialequations,andthensolves (bytendency)polynomialproblemsofsmalldimensionality at eachpointof time,witha subsequent integrationof thesepartial solutionsusing themaximum principleby integratingmainandadjointequationsystems. Thesmalldimensionalityateachpointof timeresultsfromdynamicdecompositionof jobexecutiondescribedbyprecedencerelationconstraints, i.e., at eachpointof time,weconsideronlyoperations thatcanbeassignedtomachinesat thispointof time,excludingthoseoperations thatalreadyhavebeencompletedaswellas those thatcannotstart becausethepredecessorshavenotyetbeencompleted.Algorithmically,wesolvedthesedimensionally smallproblemsat subsequentpointof times, integratemainandadjoint systemsby themaximum principle,andconsideredhowaparticularassignmentdecisionchanges thescheduleperformance metric (e.g., tardiness). If an improvement isobserved, thealgorithmtakes thisassignmentandmoves further tonextpointof timeandcontinues in thismanneruntilTf. 160