Seite - 57 - in Algorithms for Scheduling Problems

algorithms Article Near-OptimalHeuristics for Just-In-TimeJobs MaximizationinFlowShopScheduling HelioYochihiroFuchigami1,* ID ,RuhulSarker 2 andSocorroRangel 3 ID 1 FacultyofSciencesandTechnology(FCT),FederalUniversityofGoias (UFG), 74968-755AparecidadeGoiânia,Brazil 2 SchoolofEngineeringandInformationTechnology(SEIT),UniversityofNewSouthWales (UNSW), CanberraACT2610,Australia; r.sarker@adfa.edu.au 3 InstitutodeBiociências,LetraseCiênciasExatas (IBILCE),UniversidadeEstadualPaulista (UNESP), 19014-020SãoPaulo,Brazil; socorro@ibilce.unesp.br * Correspondence: heliofuchigami@ufg.br;Tel.:+55-62-3209-6550 Received: 28February2018;Accepted: 4April2018;Published: 6April2018 Abstract: Thenumber of just-in-time jobsmaximization in apermutationflowshop scheduling problem is considered. Amixed integer linearprogrammingmodel to represent theproblemas wellassolutionapproachesbasedonenumerationandconstructiveheuristicswereproposedand computationally implemented. Instanceswithup to10 jobs andfivemachines are solvedby the mathematicalmodel in an acceptable running time (3.3min on average)while the enumeration methodconsumes,onaverage,1.5 s. The10constructiveheuristicsproposedshowtheyarepractical especially for large-scale instances (upto100 jobsand20machines),withverygood-qualityresults andefficient runningtimes. Thebest twoheuristicsobtainnear-optimalsolutions,withonly0.6% and0.8%averagerelativedeviations. Theyprove tobebetter thanadaptationsof theNEHheuristic (well-knownforprovidingverygoodsolutions formakespanminimization inflowshop) for the consideredproblem. Keywords: just-in-timescheduling;flowshop;heuristics 1. Introduction Permutationflowshopscheduling,aproductionsysteminwhich jobsfollowthesameflowforall machines in thesameorder, isoneof themost importantproductionplanningproblems[1]. This type ofmanufacturingenvironment isveryoftenencounteredin intermittent industrialproductionsystems. In thiscontext, the just-in-timeschedulingaimstoachieveasolution thatminimizes thecost functions associatedwith the earliness and tardiness of jobs. Therefore, it ismore common tofind research addressingthesumof theearlinessandtardinessof jobsor thepenaltiescausedbyadeviationfroma previouslyestablishedduedate for thedeliveryofaproduct. Inpractice, theseperformancemeasures areveryimportantforcompaniesasboththeearlinessandtardinessofcompleting jobsentail relatively highercostsofproduction, suchas increases in inventory levels,fines, cancellationsofordersoreven lossofcustomers. Adifferentapproach is toconsideranobjectiverelatedto thenumberofearly/tardy jobsrather thanearliness/tardinessduration[2]. LannandMosheiov[3] introducedin1996aclassofproblemsin the just-in-timearea thataimstomaximize thenumberof jobscompletedexactlyontheirduedates, whicharecalled just-in-time jobs.However,uptodate, therearestill fewworks in the literature that considerasanoptimizationcriterionthemaximizationof thenumberof just-in-time jobs,despite its applicability. Examplesofapplications inwhichsuchstructuremayarise include: chemicalorhi-tech industries,wherepartsneedtobereadyatspecific times inorder tomeetcertainrequiredconditions (arrivalofotherparts, specific temperature,pressure,etc.);productionofperishable items(e.g., food Algorithms 2018,11, 43;doi:10.3390/a11040043 www.mdpi.com/journal/algorithms57