Seite - 146 - in Algorithms for Scheduling Problems

algorithms Article OptimalControlAlgorithmsandTheirAnalysis for Short-TermSchedulinginManufacturingSystems BorisSokolov1,AlexandreDolgui 2 ID andDmitryIvanov3,* 1 SaintPetersburgInstitute for InformaticsandAutomationof theRAS(SPIIRAS),V.O.14 line,39, 199178St. Petersburg,Russia; sokol@iias.spb.su 2 DepartmentofAutomation,ProductionandComputerSciences, IMTAtlantique,LS2N—CNRSUMR6004, LaChantrerie,4 rueAlfredKastler, 44300Nantes,France;alexandre.dolgui@imt-atlantique.fr 3 DepartmentofBusinessAdministration,BerlinSchoolofEconomicsandLaw,10825Berlin,Germany * Correspondence: divanov@hwr-berlin.de;Tel.:+49-30-30877-1155 Received: 18February2018;Accepted: 16April2018;Published: 3May2018 Abstract:Current literaturepresentsoptimalcontrol computationalalgorithmswithregardtostate, control, andconjunctivevariablespaces. Thispaperfirstanalyses theadvantagesandlimitationsof differentoptimalcontrolcomputationalmethodsandalgorithmswhichcanbeusedforshort-term scheduling. Second, it develops anoptimal control computational algorithm that allows for the solutionof short-termscheduling in anoptimalmanner. Moreover, qualitative andquantitative analysisof themanufacturingsystemschedulingproblemispresented.Resultshighlightcomputer experimentswithaschedulingsoftwareprototypeaswellaspotential futureresearchavenues. Keywords: scheduling;optimalcontrol;manufacturing;algorithm;attainablesets 1. Introduction Short-termschedulinginmanufacturingsystems(MS)considers jobsthatcontainoperationchains withequal (i.e., flowshop)ordifferent (i.e., job shop)machine sequencesanddifferentprocessing times. Operationswhichneed to be scheduled formachineswithdifferent processingpower are subject tovariouscriteria includingmakespan, leadtime,andduedates ([1–4]). Over the last several decades, various studies have investigated scheduling problems from differentperspectives.Arichvarietyofmethodsandapplicationscanbeobserved in thedevelopment of rigorous theoreticalmodelsandefficientsolutiontechniques. [5–12]and[13]havedemonstrated thatspecific large-scaleschedulingproblemswithcomplexhybrid logicalandterminalconstraints, processexecutionnon-stationary(i.e., interruptions inmachineavailability), complex interrelations betweenprocessdynamics, capacityevolutionandsetups (i.e., intensity-dependentprocessingtimes formachinework) require further investigation in termsofabroadrangeofmethodicalapproaches. Oneof these isoptimalcontrol. Optimal control approaches differ frommathematical programmingmethods and represent schedules as trajectories. The various applications of optimal control to scheduling problems are encountered in production systems with single machines [14], job sequencing in two-stage productionsystems[15], andmulti-stagemachinestructureswithalternatives in jobassignmentsand intensity-dependentprocessingrates. Specifically, suchmulti-stagemachinestructures includeflexible MSs([16–18]), supplychainmulti-stagenetworks ([19,20]), andIndustry4.0systemsthatallowdata interchangebetween theproduct andstations, flexible stationsdedicated tovarious technological operations,andreal-timecapacityutilizationcontrol [13]. Adiversityofknowledgeandfindings inoptimalcontrolapplicationsexistswhichpertains to scheduling. However, these approaches typically pertain to trajectorieswhich are assumed to be optimal but are subject to somespecific constraint systemandprocessmodel forms suchasfinite Algorithms 2018,11, 57;doi:10.3390/a11050057 www.mdpi.com/journal/algorithms146