Page - 24 - in Algorithms for Scheduling Problems

Algorithms 2018,11, 66 Table1. Inputdata for theproblem1|pLi ≤ pi≤ pUi |∑Ci. i 1 2 3 4 5 6 7 8 9 10 pLi 6 7 6 1 8 17 15 24 25 26 pUi 11 11 12 19 16 21 35 28 27 27 Thereare fourblocks in thisexampleas follows: {B1,B2,B3,B4}=:B. The jobs J1, J2, J3, J4 and J5 belongto theblockB1. The jobs J4, J5 and J7 arenon-fixed. Theremaining jobs J1, J2, J3, J6, J8, J9 and J10 arefixed in theirblocks. TheblockB2 isvirtual. The jobs J4, J5 and J7 belongto thevirtualblockB2. The jobs J4, J6, and J7 belongto theblockB3. The jobs J7, J8, J9 and J10 belongto theblockB4. J1 J2 J3 J4 J5 J6 J7 J8 J9 J10 Jobs Ji 1 67 8 10 12 15 17 19 21 24 26 28 35 times pi Processing Figure1.Thesegments [pLi ,p U i ]givenforthefeasibleprocessingtimesofthejobs Ji∈J={J1, J2,. . . , J10} (thecoresof theblocksB1,B2,B3 andB4 aredashed). 3.2. Properties of a JobPermutationBasedonBlocks TheproofofLemma1isbasedonProcedure1. Lemma 1. For the problem 1|pLi ≤ pi ≤ pUi |∑Ci, the set B = {B1,B2, . . . ,Bm} of all blocks can be determined inO(n logn) time. Proof. The right bound bU1 of the core of the first block B1 ∈ B is determined as follows: bU1 =minJi∈J p U i . Then, all jobs included in the block B1 may be determined as follows: B1={Ji∈J : pLi ≤ bU1 ≤ pUi }. The leftboundbL1 of thecoreof theblockB1 isdeterminedas follows: bL1 =maxJi∈B1 p L i . Then,onecandetermine thesecondblockB2∈Bviaapplying theaboveprocedure to thesubsetof setJwithout jobs Ji, forwhich theequalitybU1 = pUi holds. Thisprocess is continued untildeterminingthe lastblockBm∈B. Thus,onecanusetheaboveprocedure(wecall itProcedure1) for constructing the set B = {B1,B2, . . . ,Bm} of all blocks for the problem1|pLi ≤ pi ≤ pUi |∑Ci. Obviously,Procedure1has thecomplexityO(n logn). AnyblockfromthesetBhas the followingusefulproperty. 24