Page - 126 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 50 • Genetic algorithms. From the first glance evolutionary algorithms [15] should have a good applicationcase for theschedulingproblem(1)–(3). Thecombinatorialvectorofpermutations ck ∈ {0,1}, k=1,. . . ,K, seemstobenaturallyandeasilyrepresentedasabinarycrossover [15] while the narrow tolerance region of the optimization problem will contribute to the fast convergenceof thebreedingprocedure. Authorsof thispaper leave this question for further researchanddiscussion. • Dynamicprogramming.Ahuge implementationarea inglobaloptimization(andparticularly in RCPSP) is left fordynamicprogrammingalgorithms[16].Havingsevere limitations inamount andtimewedonotcover thisapproachbutwill comebackto it in futurepapers. Thecomputationspeedof thehighdimensionproblemusinganaveragePCisnotsatisfactory. This fact forces authors to investigate parallel computing technologies. Future research assumes adoption of created algorithms to a parallel paradigm, for instance, implementing map-reduce technology[17]. Acknowledgments: ThisworkwassupportedbytheRussianScienceFoundation(grant17-19-01665). AuthorContributions:A.A.L. conceivedconceptual andscientificproblemsetting; I.N. adopted theproblem setting formanufacturing case anddesigned the optimization algorithms;N.P. implemented the algorithms, performedtheexperimentsandanalyzedthedata. Conflictsof Interest:Theauthorsdeclarenoconflictof interest. The foundingsponsorshadnorole in thedesign of the study; in the collection, analyses, or interpretationofdata; in thewritingof themanuscript, and in the decisiontopublish theresults. References 1. Artigues,C.;Demassey,S.;Néron,E.; Sourd,F.Resource-ConstrainedProjectSchedulingModels,Algorithms, ExtensionsandApplications;Wiley-Interscience:Hoboken,NJ,USA,2008. 2. Meyer,H.;Fuchs,F.;Thiel,K.ManufacturingExecutionSystems.OptimalDesign,Planning, andDeployment; McGraw-Hill:NewYork,NY,USA,2009. 3. Jozefowska, J.;Weglarz, J.Perspectives inModernProjectScheduling; Springer:NewYork,NY,USA,2006. 4. Manne,A.S.OntheJob-ShopSchedulingProblem.Oper. Res. 1960,8, 219–223,doi:10.1287/opre.8.2.219. 5. Jones,A.; Rabelo, L.C. Surveyof JobShopSchedulingTechniques. InWileyEncyclopedia ofElectrical and Electronics Engineering; National Institute of Standards andTechnology: Gaithersburg,ML,USA, 1999. Availableonline: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.37.1262&rep=rep1&type=pdf (accessedon10April2017). 6. Taravatsadat, N.; Napsiah, I. Application of Artificial Intelligent in Production Scheduling: A critical evaluation and comparison of key approaches. In Proceedings of the 2011 International Conference on Industrial Engineering andOperationsManagement, KualaLumpur,Malaysia, 22–24 January 2011; pp.28–33. 7. Hao, P.C.; Lin, K.T.; Hsieh, T.J.; Hong, H.C.; Lin, B.M.T. Approaches to simplification of job shop models. In Proceedings of the 20thWorking Seminar of Production Economics, Innsbruck, Austria, 19–23February2018. 8. Trevisan,L.CombinatorialOptimization: Exact andApproximateAlgorithms; StanfordUniversity: Stanford,CA, USA,2011. 9. Wilf,H.S.AlgorithmsandComplexity;UniversityofPennsylvania: Philadelphia,PA,USA,1994. 10. Jacobson, J.BranchandBoundAlgorithms—Principles andExamples;UniversityofCopenhagen:Copenhagen, Denmark,1999. 11. Erickson, J.Models ofComputation;Universityof Illinois:Champaign, IL,USA,2014. 12. Ruder,S.AnOverviewofGradientDescentOptimizationAlgorithms;NUIGalway:Dublin, Ireland,2016. 13. Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C. Introduction to Algorithms, 3rd ed.; Massachusetts InstituteofTechnology: London,UK,2009. 14. Kalitkyn,N.N.NumericalMethods;ChislennyeMetody;Nauka:Moscow,Russia,1978. (InRussian) 15. Haupt,R.L.;Haupt,S.E.PracticalGeneticAlgorithms, 2nded.;Wiley-Interscience:Hoboken,NJ,USA,2004. 126