Seite - 39 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 7.ConcludingRemarks The uncertain problem 1|pLi ≤ pi ≤ pUi |∑Ci continues to attract the attention of the OR researchers since the problem iswidely applicable in real-life scheduling and is commonly used inmanymultiple-resource scheduling systems,where only one of themachines is the bottleneck anduncertain. Therightschedulingdecisionsallowtheplant toreduce thecostsofproductionsdue tobetterutilizationof themachines. Ashorterdelivery time is archivedwith increasingcustomer satisfaction. InSections2–6,weused thenotionof anoptimalityboxof a jobpermutationπk and provedusefulpropertiesof theoptimalityboxOB(πk,T).Weinvestigatedpermutationπkwiththe largest relativeperimeterof theoptimalitybox.Usingtheseproperties,wederivedefficientalgorithms forconstructing theoptimalityboxfora jobpermutationπkwiththe largest relativeperimeterof the boxOB(πk,T). Fromthecomputationalexperiments, it followsthat thepermutationπkwiththesmallestvalues of the error functionF(πk,t) for theoptimalityboxOB(πk,T) is close to theoptimalpermutation, whichcanbedeterminedafter completing the jobswhentheirprocessing timesbecameknown. In ourcomputationalexperiments,wetestedclasses1–7ofhardproblems1|pLi ≤ pi≤ pUi |∑Ci,where thepermutationconstructedbyAlgorithm3outperformsthemid-pointpermutation,which isoften used in thepublishedalgorithmsappliedto theproblem1|pLi ≤ pi≤ pUi |∑Ci. Theminimal,average andmaximal errorsΔof theobjective functionvalueswere 0.045303%, 0.735154%and4.773618%, respectively, for thepermutationswithsmallestvaluesof theerror functionF(πk,t) for theoptimality boxes. Theminimal,averageandmaximalerrorsΔmid−poftheobjectivefunctionvalueswere0.05378%, 0.936243%and6.755918%,respectively, for themid-pointpermutations. Theminimal,averageand maximal errors Δmax of the objective function valueswere 0.04705%, 0.82761% and 6.2441066%, respectively. Thus,Algorithm3solvedall hard instanceswith a smaller errorΔ thanother tested algorithms. Theaveragerelation Δmid−p Δ for theobtainederrors forall instancesofclasses1–7wasequal to1.33235. Theaveragerelation ΔmaxΔ for theobtainederrors forall instancesofclasses1–7wasequal to1.1133116. Author Contributions: Y.N. proved theoretical results; Y.N. and N.E. jointly conceived and designed the algorithms;N.E.performedtheexperiments;Y.N.andN.E.analyzedthedata;Y.N.wrote thepaper. Conflictsof Interest:Theauthorsdeclarenoconflictof interest. References 1. Davis,W.J.; Jones,A.T.Areal-timeproductionscheduler forastochasticmanufacturingenvironment. Int. J. Prod. Res. 1988,1, 101–112. [CrossRef] 2. Pinedo,M.Scheduling: Theory,Algorithms, andSystems;Prentice-Hall: EnglewoodCliffs,NJ,USA,2002. 3. Daniels,R.L.;Kouvelis,P.Robustschedulingtohedgeagainstprocessingtimeuncertainty insinglestage production.Manag. Sci. 1995,41, 363–376. [CrossRef] 4. Sabuncuoglu, I.;Goren,S.Hedgingproductionschedulesagainstuncertainty inmanufacturingenvironment withareviewofrobustnessandstabilityresearch. Int. J.Comput. Integr.Manuf. 2009,22, 138–157. [CrossRef] 5. Sotskov,Y.N.;Werner,F.SequencingandSchedulingwithInaccurateData;NovaSciencePublishers:Hauppauge, NY,USA,2014. 6. Pereira, J.Therobust (minmaxregret) singlemachineschedulingwith intervalprocessingtimesandtotal weightedcompletiontimeobjective.Comput.Oper. Res. 2016,66, 141–152. [CrossRef] 7. Grabot,B.;Geneste,L.Dispatchingrules inscheduling:Afuzzyapproach. Int. J.Prod. Res. 1994,32, 903–915. [CrossRef] 8. Kasperski, A.; Zielinski, P. Possibilistic minmax regret sequencing problems with fuzzy parameteres. IEEETrans. FuzzySyst. 2011,19, 1072–1082. [CrossRef] 9. Özelkan, E.C.; Duckstein, L. Optimal fuzzy counterparts of scheduling rules. Eur. J. Oper. Res. 1999, 113, 593–609. [CrossRef] 39