Page - 10 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 18 IfCondition6 is satisfied, itmeans job i cannotbeprocessedwithinanyoneof themid-peak periods, let aloneoff-peakperiods. Inotherwords, job i canonlybeused tofill the remaining idle timeof a certain periodwith lower electricity price. There is an obvious regularity that themore the remaining idle timeof theoff-peakormid-peakperiod job ioccupy, the lower is itsprocessing electricitycost. Figure7showsall thepossiblepositions forascenario. Theanalysisprocessof the possiblepositions that job icanbe inserted into issimilar toCondition4,and, therefore,willnotbe repeatedhere. Figure7. IllustrationofCondition6. Condition7:maxk′∈B{Ik′}=0. Condition7 implies that all theoff-peakperiods andmid-peakperiods are full, and job i can onlybe inserted intoon-peakperiods. Ifmaxk′′∈Γ { Ik′′ } < ti, job ishouldbe inserted intoallnon-full on-peak periods bymoving a set of already inserted jobs, and then the positionwith the lowest insertioncostcanbechosen. Themovementmethodcanrefer toCheetal. [9]. Thecorecomponentoftheheuristicalgorithmisdescribedasapseudocode,showninAlgorithm1. Note that theargmin(Ik≥ ti)denotes theminimal indexk for Ik≥ ti. Theorem1.Theproposedheuristic algorithmruns inO(n2m|Γ|) in theworst case. Proof. Step1runs inO(nlogn) time for sortingnnumbersandStep2requiresO(m) time. Foreach given job, StepC1 runs inO(|A|) in theworst case andStepC2 requiresO(1). StepsC3 andC5 bothrequireO(|B|)operations in theworst case. StepsC4andC6demandO(nm) to compute the movementcostwhencalculating the insertioncost. StepC7 includesstepsC7.1andC7.2,wherein thecomplexityofstepC7.1 isO(|Γ|),andthecomplexityofstepC7.2 isO(nm|Γ|). Therefore, step C7requiresO(nm|Γ|)operations in theworstcase. Tosummarize, theproposedalgorithmruns in O(n2m|Γ|) in theworstcase. Now,assumethatno jobsneedto traverseallnon-fullon-peakperiods, that is, theStepC7.2has neverbeenused. In this case, the timecomplexityof theproposedalgorithmisO(n2m). However, theclassicgreedyinsertionalgorithmproposedbyCheetal. [9] requiresO(n2m2)operations in the worst casewhendealingwith the sameproblem, because their algorithm requires all the jobs to traverseallnon-fullperiods tofindanoptimumposition. 10