Seite - 147 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 57 dimensionality, convexity, etc. In general, optimal control algorithms only provide the necessary conditions for optimal solution existence. Themaximumprinciple provides both optimality and necessary conditions only for some specific cases, i.e., linear control systems. As such, further investigationsarerequired ineachconcreteapplicationcase. Thispaperseeks tobring thediscussionforwardbycarefullyelaboratingontheoptimality issues describedaboveandprovidingsomeideasandimplementationguidanceonhowtoconfront these challenges. Thepurposeof thepresent study is tocontribute toexistingworksbyprovidingsome closedformsofalgorithmicoptimalityprovenin therichoptimalcontrolaxiomatic. The rest of this paper is organized as follows. In Section 2,wepropose general elements of themultiple-modeldescriptionof industrialproductionschedulinganditsdynamic interpretation. InSection3, optimal control computational algorithmsand their analyses areproposed. Section4 presentsacombinedmethodandalgorithmforshort-termscheduling inMS. InSection5,qualitative andquantitativeanalysisof theMSschedulingproblemissuggested. Thepaperconcludes inSection6 bysummarizingtheresultsof this study. 2.OptimalControlApplications toSchedulinginManufacturingSystems Optimalcontrolproblemsbelongto theclassofextremumoptimizationtheory, i.e., theanalysis of theminimizationormaximizationofsomefunctions ([21–28]. This theoryevolvedonthebasisof calculusvariationprinciplesdevelopedbyFermat,Lagrange,Bernulli,Newton,Hamilton,andJacobi. Inthe20thcentury, twocomputationalfundamentalsofoptimalcontroltheory,maximumprinciple[21] anddynamicprogrammingmethod[29],weredeveloped. Thesemethodsextendtheclassical calculus variationtheorythat isbasedoncontrolvariationsofacontinuous trajectoryandtheobservationof theperformance impactof thesevariationsat the trajectory’s terminus. Sincecontrol systemsinthe middleof the20thcenturywereincreasinglycharacterizedbycontinuousfunctions(suchas0–1switch automats), thedevelopmentofboththemaximumprincipleanddynamicprogrammingwasnecessary inorder tosolve theproblemwithcomplexconstraintsoncontrolvariables. Manufacturingmanagersarealways interested innon-deterministicapproaches toscheduling, particularlywherescheduling is interconnectedwith thecontrol function [30]. Studiesby[31]and[11] demonstrated awide range of advantages regarding the application of control theoreticmodels in combinationwith other techniques for production and logistics. Among others, they include anon-stationaryprocessviewandaccuracyofcontinuous time. Inaddition,awiderangeofanalysis tools fromcontrol theoryregardingstability, controllability,adaptability, etc.maybeusedifaschedule is described in terms of control. However, the calculation of the optimal program control (OPC) with thedirectmethods of the continuousmaximumprinciple has not beenproved efficient [32]. Accordingly, theapplicationofOPCtoscheduling is important for tworeasons. First, aconceptual problemconsistsof thecontinuousvaluesof thecontrolvariables. Second,acomputationalproblem with adirectmethodof themaximumprinciple exists. These shortcomings set limitations on the applicationofOPCtopurelycombinatorialproblems. Todate,variousdynamicmodels,methodsandalgorithmshavebeenproposedtosolveplanning andschedulingproblems indifferentapplicationareas ([13,19,33–38]). In thesepapers, transformation procedures from classical scheduling models to their dynamic analogue have been developed. Forexample, the followingmodelsofOPCwereproposed: Mg—dynamicmodelofMSelementsandsubsystemsmotioncontrol; Mk—dynamicmodelofMSchannelcontrol; Mo—dynamicmodelofMSoperationscontrol; Mf—dynamicmodelofMSflowcontrol; Mp—dynamicmodelofMSresourcecontrol; Me—dynamicmodelofMSoperationparameterscontrol; Mc—dynamicmodelofMSstructuredynamiccontrol; 147