Seite - 13 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 18 Table2.Themeasurementdataof thereal-life instance. ProductModel AveragePowerConsumptionRate (kW) ProcessingTime(h) TheNumberofParts 40 4.4 2.4 15 70 4.7 2.6 35 100 5.3 3.1 10 Letus temporarilyputaside theabovereal-life instance,andtalkaboutsolvingahypothetical instancegiven inTables 3 and4basedon theabovedata. Specifically, it is assumed that there are twelvepartswhichneedtobeprocessedwithin twodays. That is, thenumberofperiods is ten(i.e., m=10).According to thisexample,wewilldemonstrate theMILPmodelandthemaincomputational processofGIH-F. Table3.Ahypothetical instancebasedonreal-lifedata. Part (Job) 1 2 3 4 5 6 7 8 9 10 11 12 Processingtime(h) 2.4 2.4 2.4 2.4 2.6 2.6 3.1 3.1 3.1 3.1 3.1 3.1 Powerconsumptionrate (kW) 4.4 4.4 4.4 4.4 4.7 4.7 5.3 5.3 5.3 5.3 5.3 5.3 Table4.TOUtariffs for thehypothetical instance. Period 1 2 3 4 5 6 7 8 9 10 Duration(h) 3.5 7 4.5 8 1 3.5 7 4.5 8 1 Price (CNY/kwh) 1.2473 0.8451 1.2473 0.443 0.8451 1.2473 0.8451 1.2473 0.443 0.8451 First, the twelve jobsaresorted innon-increasingorderaccordingto theirpowerconsumption rates, that is, job7, job8, job9, job10, job11, job12, job5, job6, job1, job2, job3,and job4. Second, the remaining idle timeof all theperiods are initialized. Obviously, t7 ≤maxk∈A{Ik}+ Ik+1 and t7≤ I4(i.e., k=4), hence job7canbe inserted into the low-price layer1andisplaced in theposition corresponding to theCondition1. The sameapplies to jobs 8, 9, and10. In thisway, theoff-peak periods are fullyutilizedby the jobswithhighpower consumption rates, resulting in lower total electricity costs. At this stage, the remaining idle timeof eachperiod is as follows: I1 =3.5, I2 =7, I3 =4.5, I4 =1.8, I5 =1, I6 =3.5, I7 =7, I8 =4.5, I9 =1.8, I10 =1.Anillustration isgiven inFigure10a. Now, t11 >maxk∈A{Ik}+ Ik+1 and ∃k′ ∈ B,t11 ≤ Ik′ (i.e., k=4andk′=2), hence job 11 is assigned tomedium-price layer 2, and is placed in theposition corresponding to theCondition 3 becausemaxk∈A{Ik}> 0anddk+2= 3.5> 0.Moreover, xi,k×(cB−cA)> xi,k+2×(cΓ−cB)where k= 4 and i= 11, thus, job 11 is to be inserted into the position across periods 4–6. At this stage, theremaining idle timeofeachperiod isas follows: I1 =3.5, I2 =7, I3 =4.5, I4 =0, I5 =0, I6 =3.2, I7 =7, I8 =4.5, I9 =1.8, I10 =1.Anillustration isgiven inFigure10b. Let us continue, and it is not hard to check that the job 12 is to be inserted into the position correspondingtoCondition4.Asmentionedearlier, therewillbefivepositionswaitingforselectionat thismoment. The insertioncosts for thesefivepositionsare12.8,10.7,10.7, Inf, and13.9, respectively. Therefore, job12 is tobe inserted into thePosition2whichcrossesperiods8and9.Note that Iksm=0 (i.e., I4 = 0), hence job 12 cannot be processed across periods ksm, ksm + 1, and ksm + 2, and the corresponding insertion cost is infinity. At this stage, the remaining idle timeof eachperiod is as follows: I1 =3.5, I2 =7, I3 =4.5, I4 =0, I5 =0, I6 =3.2, I7 =7, I8 =4.2, I9 =0, I10 =0.Anillustration is given inFigure10b. Next, letusexplain the insertionprocessofother jobsconcisely. Jobs5and6areassignedto layer 2, andtheysatisfyCondition5. Therefore, these two jobsare tobe inserted intomid-peakperiod2. Similarly, jobs1and2are tobe inserted intoperiod7.At thisstage, theremaining idle timeofeach period is as follows: I1 =3.5, I2 =1.8, I3 =4.5, I4 =0, I5 =0, I6 =3.2, I7 =2.2, I8 =4.2, I9 =0, I10 =0. Anillustration isgiven inFigure10c. 13