Page - 21 - in Algorithms for Scheduling Problems

algorithms Article SingleMachineSchedulingProblemwithInterval ProcessingTimesandTotalCompletion TimeObjective YuriN.Sotskov*andNataljaG.Egorova UnitedInstituteof InformaticsProblems,NationalAcademyofSciencesofBelarus,SurganovaStreet6, Minsk220012,Belarus;NataMog@yandex.by *Correspondence: sotskov48@mail.ru;Tel.: +375-17-284-2120 Received: 2March2018;Accepted: 23April2018;Published: 7May2018 Abstract:Weconsiderasinglemachineschedulingproblemwithuncertaindurationsof thegiven jobs. The objective function isminimizing the sumof the job completion times. We apply the stabilityapproachto theconsidereduncertainschedulingproblemusingarelativeperimeterof the optimalityboxasastabilitymeasureof theoptimal jobpermutation.Weinvestigatedpropertiesof theoptimalityboxanddevelopedalgorithmsforconstructing jobpermutations thathave the largest relativeperimetersof theoptimalitybox.Computational results forconstructingsuchpermutations showedthat theyprovidedtheaverageerror less than0.74%for thesolveduncertainproblems. Keywords: scheduling;uncertaindurations; singlemachine; total completiontime 1. Introduction Sincereal-life schedulingproblemsinvolvedifferent formsofuncertainties, severalapproaches havebeendevelopedin the literature fordealingwithuncertainschedulingproblems. Inastochastic approach, job processing times are assumed to be randomvariableswith the knownprobability distributions [1,2]. Ifonehasnosufficient informationtocharacterize theprobabilitydistributionof all randomprocessingtimes,otherapproachesareneeded[3–5]. In theapproachofseekingarobust schedule [3,6], thedecision-makerprefersaschedule thathedgesagainst theworst-casescenario.A fuzzyapproach[7–9]allowsascheduler todeterminebest scheduleswithrespect to fuzzyprocessing times. A stability approach [10–12] is based on the stability analysis of the optimal schedules to possiblevariationsof thenumericalparameters. In thispaper,weapply thestabilityapproach toa singlemachineschedulingproblemwithuncertainprocessing timesof thegiven jobs. InSection2, wepresent thesettingof theproblemandtherelatedresults. InSection3,weinvestigateproperties ofanoptimalityboxof thepermutationusedforprocessingthegiven jobs. Efficientalgorithmsare derived forfindinga jobpermutationwith the largest relativeperimeter of theoptimalitybox. In Section5,wedevelopanalgorithmforfindinganapproximatesolutionfor theuncertainscheduling problem. InSection6,wereportonthecomputational results forfindingtheapproximatesolutions for the tested instances. Section7 includes theconcludingremarks. 2. ProblemSettingandtheRelatedResults Therearegivenn jobsJ = {J1, J2,..., Jn} tobeprocessedonasinglemachine. Theprocessing time piof the job Ji∈J cantakeanyrealvalue fromthegivensegment [pLi ,pUi ],where pUi ≥ pLi >0. Theexactvalue pi∈ [pLi ,pUi ]of the jobprocessing timeremainsunknownuntil completing the job Ji ∈J . LetRn+denote a set of all non-negativen-dimensional real vectors. The set of all possible vectors (p1,p2, . . . ,pn)= p∈Rn+of the jobprocessingtimes ispresentedas theCartesianproductof Algorithms 2018,11, 66;doi:10.3390/a11050066 www.mdpi.com/journal/algorithms21