Seite - 58 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 43 anddrugs)underdeterministicdemand;maintenanceservicesagencieswhichhandle thepreferable duedate forcustomers;andrentalagencies (hotelsamdcarrental),wherereservationsschedulemust meetexactly the timerequestedbyall clients. In classical notation of three fields, themaximization of the number of just-in-time jobs in a permutationflowshopproblemcanbedenotedbyFm|prmu,dj|nJIT,whereFm indicatesagenericflow shopenvironmentwithmmachines,prmu thepermutationconstraint,dj theexistenceofaduedate foreach jobandnJIT theobjective functionthatmaximizes thenumberof jobscompleted just-in-time. Insomeenvironments, suchasasingle-machineproblemandpermutationflowshop, theschedule isprovidedbyonly jobsequencing. Inothers, it isalsonecessary toallocate jobs tomachines, such as in the oneswithparallelmachines and inhybridflowshop. Although this research addresses theproblemof thepermutationflowshop, inadditiontosequencing, there isalso thepossibilityof inserting idle time intosome jobs toadjust their completions to theduedates (if there is slack). That is, thesolution (schedule) comprisessequencingandtimingphases;besidesanorderof jobs, it isalso necessary todefinethestartingandendingstagesofeachoperation. In the literature, it isknownasa schedulewith inserted idle time[4]. The purpose of this work is to provide insights for a theme in the area of scheduling that, despite its importance forseveral industrial contexts, is relativelyunexplored. Thisstudyproposes amathematicalmodel torepresent thepermutationflowshopschedulingwith the totalnumberof just-in-time jobsbeingmaximizedandasetofheuristic solutionapproaches tosolve it inarelatively shortexecutiontime.Acomprehensivecomputational studyispresented.Asshowninthe literature review, to thebestofourknowledge,allbutoneof thepapersdealingwith themaximizationof the totalnumberof just-in-time jobsonlypresent theoretical results. Thus, thisresearchhelpstofill thegap ofcomputational results in the literatureofschedulingproblems.Weareconcernedwithapplications forwhichthere isno interest in jobs thatarefinishedbeforeorafter theirduedates. The remainder of this paper is organizedas follows. A reviewof the just-in-time scheduling problemsliterature ispresented inSection2.Aformaldescriptionof theproblemconsideredandthe mixed integer linearprogrammingmodeldevelopedisgiven inSection3. Theproposedconstructive heuristicsmethodsarediscussed inSection4.Analysesof theresults fromall thesolutionapproaches computationally implemented in this studyarepresented inSection5. Final remarks aregiven in Section6. 2. LiteratureReview Althoughthe just-in-timephilosophy involvesbroaderconcepts,until recentdecades, scheduling problemsinthisareawereconsideredvariationsofearlinessandtardinessminimization,ascanbe seen in the reviewby [5]. Manyproblems are presented in [6,7]. Themost common just-in-time objective functions foundinthe literaturearerelatedthe totalweightedearlinessandtardiness,with equal, asymmetricor individualweights. Recently, ShabtayandSteiner [8]publisheda reviewof the literatureaddressing theproblem ofmaximizing thenumber of just-in-time jobswhichdemonstrates that this themehas beenvery littleexplored. Theworkpresented in[7],whichdealswithvarious typesof just-in-timescheduling problems,mentionsonlyonepaper thatconsiders thenumberof just-in-time jobs, that is, thesurvey presented in [8]of single-,parallel-andtwo-machineflowshopenvironments. Therearesomepublications in therelevant literature thatdiscuss theproblemconsideringthe criteriaofmaximizing thenumberof just-in-time jobs indifferentproductionsystems, specifically with flow shops. Choi andYoon [9] showed that a two-machineweighted problem is classified asNP-complete and a three-machine identicalweights one asNP-hard. These authors proposed anddemonstratedseveraldominanceconditions foran identicalweightsproblem. Basedonthese conditions, theypresentedanalgorithmfora two-machineproblem. Inaddition, theyprovedthatan optimalsolutiontoa two-machineproblemisgivenbytheearliestduedate (EDD)priorityrule. 58