Page - 146 - in Algorithms for Scheduling Problems
Image of the Page - 146 -
Text of the Page - 146 -
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
back to the
book Algorithms for Scheduling Problems"
Algorithms for Scheduling Problems
- Title
- Algorithms for Scheduling Problems
- Authors
- Frank Werner
- Larysa Burtseva
- Yuri Sotskov
- Editor
- MDPI
- Location
- Basel
- Date
- 2018
- Language
- English
- License
- CC BY 4.0
- ISBN
- 978-3-03897-120-7
- Size
- 17.0 x 24.4 cm
- Pages
- 212
- Keywords
- Scheduling Problems in Logistics, Transport, Timetabling, Sports, Healthcare, Engineering, Energy Management
- Categories
- Informatik
- Technik