Seite - 4 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 18 2.MILPFormulationfor theProblem Thispaperstudiesanenergy-efficientsinglemachineschedulingproblemunderTOUelectricity tariffs. Theproblemcanalsobe calleda singlemachine schedulingproblemwith electricity costs (SMSEC).Considerasetof jobsN={1,2, . . . ,n} thatneedtobeprocessedonasinglemachinewith theobjectiveofminimizingtheelectricitycost. It isassumedthatall the jobsmustbeprocessedata uniformspeed. Each job i∈Nhas itsuniqueprocessingtime tiandpowerconsumptionperhourpi. Amachinecanprocess,atmost,one jobata time,andwhenit isprocessinga job,nopreemption is allowed. Each jobandthemachineareavailable forprocessingat time instant0.Machinebreakdown andpreventivemaintenancearenotconsidered in thispaper. Themachine ismainlypoweredbyelectricity. Theelectricityprice followsaTOUpricingscheme representedbyasetof timeperiodsM={1,2, . . . ,m},witheachperiodk∈M,havinganelectricity price ck andastarting timebk. The intervalofperiodk is representedby[bk,bk+1],k∈M, andb1 =0 is alwaysestablished. It isassumedthat theCmax is thegivenmakespanandbm+1≥Cmax. Thismeans thata feasiblesolutionalwaysexists. Themainworkof thisproblemis toassignasetof jobs toperiodswithdifferentelectricityprices in the timehorizon [0, bm+1] tominimize total electricity cost, and themain task is todetermine to whichperiod(s)a job isassignedandhowlonga job isprocessed ineachperiod.Hence, twodecision variablesaregivenasfollows.Notethat thestartingtimeofeach jobcanbedeterminedbythedecision variables (i.e.,xi,k andyi,k). xi,k: assignedprocessingtimeof job i inperiodk, i∈N,k∈M; yi,k= { 1,if job iorpartof job i isprocessed inperiodk 0,othertwise , i∈N,k∈M. In addition, a job is calledprocessedwithin aperiod if both its starting timeandcompletion timearewithin thesameperiod.Otherwise, it is calledprocessedacrossperiods [9]. Letdk andXk, k∈M, represent thedurationofperiodkandthe totalalreadyassignedprocessingtimes inperiodk, respectively. Thedifferencebetweendk andXk isdefinedas theremaining idle timeofperiodkwhich is representedby Ik,k∈M. If Ik=0, theperiodk is called full. TheMILPmodel for thesinglemachineschedulingproblemcanbepresentedas follows: MinTEC= n ∑ i=1 m ∑ k=1 pixi,kci (1) s.t. m ∑ k=1 xi,k= ti, i∈N; (2) n ∑ i=1 xi,k≤ bk+1−bk,k∈M; (3) xi,k≤ tiyi,k, i∈N,k∈M; (4) l−1 ∑ k=j+1 yi,k≥ (l− j−1)(yi,l+yi,j−1), i∈N,3≤ l≤m,1≤ j≤ l−2; (5) xi,k≥ (yi,k−1+yi,k+1−1)(bk+1−bk), i∈N,2≤ k≤m−1; (6) yi,k+yi,k+1+yj,k+yj,k+1≤3, i∈N, j∈N,1≤ k≤m−1, i = j. (7) Equation(1), theobjective is tominimize the totalelectricitycost (TEC).Constraints (2)–(4)are associatedwith theprocessingtimeassignedtoperiods.Constraints (5)and(6)areusedtoguarantee thenon-preemptiveassumption. Specifically, constraint (5)guarantees that if a job isprocessedacross 4