Page - 72 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 43 mathematicalmodelandtheenumerationmethodwereusefulasqualitycertificate.Moreover, the mathematicalmodelcanbeuseful ifotherconstraintsor requirementsareaddedto theproblem. 6. FinalRemarks This researchachieves itsproposedgoalsofdevelopingandimplementingeffectiveandefficient methodsforsolvingaflowshopschedulingproblembymaximizingthenumberof just-in-timejobs,as demonstrated in thecomputationalexperiments.AMIPmodel isproposedtorepresent theproblem and, togetherwithanenumerationalgorithm, isusefulasqualitycertificate for thesolutionvalues givenbytheconstructiveheuristicsproposed. TheCPLEXsystemsolves instancesof theMIPmodelwithupto10 jobsandfivemachines inat most47min. Itprovidesa lowerboundfor theoptimalsolutionfor instanceswithupto100 jobsand 20machines. Theenumerationmethoddoesnotguaranteeoptimalitybecause thesolution is formed by jobsequencingandtiming(thestarting timesof jobs).However, it showsrelativeapplicabilityand considerablequality (0.2%deviations insmall instances)withanaveragerunningtimeof1.5s. The practicability and applicability of all proposed heuristic methods are demonstrated, in particular for large-scale instances, with very good quality results and non-prohibitive runtimes. Thebestheuristic,H6,demonstratesanear-optimalsolution,withjusta0.5%averagerelativedeviation fromtheexact solutionandoptimalsolutions formore than98%of instances,while theperformance of thesecondbest,H5, isveryclose. In total, 15,600 instancesare solved,with theaverage relative deviationofH6only0.2%andthatofH5approximately0.3%.TheH6andH5heuristicsconsider the EDDruleas the initial solutionandthen iterativelyplace thefirst tardy jobat theendof thesequence. Althoughtheir resultsareveryclose,H6improvesonH5byusingneighborhoodsearches. In this study, the focus isonsolvingaflowshopschedulingproblembyreducing the interval betweenthecompletiontimeof the lastoperationofa jobanditsduedate. Thisenablesanadjustment inthetimingof jobswhichresults inthepossibilityofinsertingidletimebetweenoperations. Therefore, there isnoconcernabout thefirstoperationsofeach job, i.e., theirexecutionscouldbeapproximated. Reschedulingtheseoperationscouldreduce the idle timebetweenthemandpossiblyalsominimize the total timerequired tocomplete the schedule (makespan). Therefore, it is suggested that future workconsidermultiple-criteria functions, includingflowmeasures (asamakespanand/orflowtime), inscenarioswithearlinessandtardiness. Acknowledgments: Thisworkwas supportedbyCNPq (502547/2014-6, 443464/2014-6, and233654/2014-3), CAPES(BEX2791/15-3),FAPESP(2013/07375-0and2016/01860-1)andFAPEG(201510267000983). AuthorContributions:Helio conceived,designedandperformed theexperiments;Helio,RuhulandSocorro analyzedthedataandwrote thepaper. Conflictsof Interest:Theauthorsdeclarenoconflictof interest. References 1. Pinedo,M.L.Scheduling: Theory,AlgorithmsandSystems, 5thed.;Prentice-Hall:UpperSaddleRiver,NJ,USA, 2016; ISBN978-3319265780. 2. Shabtay,D.;Bensoussan,Y.;Kaspi,M.Abicriteriaapproachtomaximizetheweightednumberof just-in-time jobsandtominimize the total resourceconsumptioncost ina two-machineflow-shopschedulingsystem. Int. J.Prod. Econ. 2012,136, 67–74. [CrossRef] 3. Lann, A.; Mosheiov, G. Single machine scheduling to minimize the number of early and tardy jobs. Comput.Oper.Res. 1996,23, 769–781. [CrossRef] 4. Kanet, J.J.; Sridharan, V. Schedulingwith inserted idle time: Problem taxonomy and literature review. Oper.Res. 2000,48, 99–110. [CrossRef] 5. Baker,K.R.;Scudder,G.D.Sequencingwithearlinessandtardinesspenalties:Areview.Oper. Res. 1990,38, 22–36. [CrossRef] 6. Józefowska, J. Just-in-TimeScheduling:ModelsandAlgorithmsforComputerandManufacturingSystems; Springer Science:NewYork,NY,USA,2007; ISBN978-387-71717-3. 72