Page - 115 - in Algorithms for Scheduling Problems

Article EvaluatingTypicalAlgorithmsofCombinatorial OptimizationtoSolveContinuous-TimeBased SchedulingProblem AlexanderA.Lazarev*, IvanNekrasov*,† andNikolayPravdivets † InstituteofControlSciences,65ProfsoyuznayaStreet, 117997Moscow,Russia;pravdivets@ya.ru * Correspondence: jobmath@mail.ru (A.A.L.); ivannekr@mail.ru (I.N.);Tel.: +7-495-334-87-51 (A.A.L.) † Theseauthorscontributedequally to thiswork. Received: 22February2018;Accepted: 12April2018;Published: 17April2018 Abstract: Weconsider one approach to formalize theResource-ConstrainedProject Scheduling Problem(RCPSP) in termsofcombinatorialoptimizationtheory. Thetransformationof theoriginal problemintocombinatorialsettingisbasedoninterpretingeachoperationasanatomicentitythathas adefineddurationandhas toberesidedonthecontinuous timeaxismeetingadditional restrictions. Thesimplestcaseofcontinuous-timeschedulingassumesone-to-onecorrespondenceofresourcesand operationsandcorrespondsto the linearprogrammingproblemsetting.However, real scheduling problemsincludemany-to-onerelationswhich leads to theadditionalcombinatorial component in the formulationduetooperationscompetition.Weresearchhowtoapplyseveral typicalalgorithms tosolve theresultedcombinatorialoptimizationproblem: enumeration includingbranch-and-bound method,gradientalgorithm,randomsearchtechnique. Keywords:RCPSP;combinatorialoptimization; scheduling; linearprogramming;MES; JobShop 1. Introduction TheResource-ConstrainedProjectSchedulingProblem(RCPSP)hasmanypracticalapplications. Oneof themostobviousanddirectapplicationsofRCPSPisplanningthe fulfilmentofplannedorders at themanufacturingenterprise [1] that isalsosometimesnamedJobShop. TheJobShopscheduling process traditionally resides inside theManufacturingExecutionSystemsscope [2] andbelongs to principlebasicmanagement tasksofanyindustrialenterprise.Historically the JobShopscheduling problemhas twoformalmathematicalapproaches [3]: continuousanddiscrete timeproblemsettings. In thispaper,weresearchthecontinuous-timeproblemsetting,analyze itsbottlenecks,andevaluate effectivenessofseveral typicalalgorithmstofindanoptimalsolution. Thecontinuous-timeJobShopschedulingapproachhasbeenextensivelyresearchedandapplied indifferent industrial spheres throughout thepast50years.Oneof themostpopularclassicalproblem settingswasformulated in[4]byManneasadisjunctivemodel. Thisproblemsettingformsabasic systemofrestrictionsevaluatedbydifferentcomputationalalgorithmsdependingontheparticular practical featuresof themodelused.Awideoverviewofdifferentcomputationalapproaches to the schedulingproblemisconducted in [5,6]. Thearticle [5] considers69papersdatingback to theXX century, revealingthe followingmaintrends in JobShopscheduling: - Enumeratingtechniques - Differentkindsof relaxation - Artificial intelligence techniques (neuralnetworks,geneticalgorithms,agents, etc.) Artificial intelligence (AI) techniqueshavebecomemainstreamnowadays. Thepaper [6]givesa detailed listofAI techniquesandmethodsusedforscheduling. Algorithms 2018,11, 50;doi:10.3390/a11040050 www.mdpi.com/journal/algorithms115