820 EEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS.VOL.25,NO.3,MARCH 2014 0=0.4 P3=0.2 P0.4 5.3 First-Fit by Collision Probability 12 [12 [123 12 In the bin packing problem [23],we are given n items with sizes s1,s2,...,sn E(0,1],and the objective is to find a Pm=0.1 packing method in unit-sized bins that minimizes the number of bins used.We observe that,when each variable ts1 ts2 ts3 ts4 ts5 ts6 ts7 tse.tsN subrequirement requires only one time slot,ie.,v;=1 for frame all 1<i<n,TSA is similar to bin packing,except that the Fig.3.The time slot assignment problem.The probability threshold size of multiple items is the sum of them in bin packing;the serves as the "volume"of a substrate time slot. collision probability of multiple subrequirements is neither linear nor multiplicative,as shown in (1). slots assigned to it is at least vi;and 2)the collision probability The first-fit algorithm [23]is a greedy approximation at each substrate time slot is no more than a given collision algorithm of factor 2 for bin packing.In first-fit,items are threshold pth. considered in an arbitrary order,and for each item,first-fit attempts to place the item in the first bin that can For example,Fig.3 shows a feasible assignment.tsi can accommodate the item.If this is not possible,the item is be assigned to two variable subrequirements because they placed into a new bin.First-fit can be executed online and collide with a probability 0.08,which is less than ph=0.1; however,tsa cannot be assigned to the second and fourth has a low time complexity. subrequirements simultaneously,because the collision Algorithm 2.First-Fit by Collision Probability(CFF). probability 0.12 is larger than pth. 1:Input:vi and pi For the hardness of the TSA problem,we have the 2:cnt←-0，indexr←-0 following theorem:Please refer to the supplemental 3:while cnt <vi do material,which can be found on the Computer Society 名 while getCollistion Pro(Dinder:Pi)>Pth do Digital Library at http://doi.ieeecomputersociety.org/ 5: index←-inder+1 10.1109/TPDS.2013.64,for the detailed proofs of all the 6: if index N return false theorems in this paper. 7: end while Theorem 1.TSA is NP-hard in the strong sense. & Dinder←-Dinder U{i} 9: cnt←-cn.t+l,inder←-index+i 5.2 An ILP-Based Optimal Solution 10: if index N return false Inspired by the cutting stock problem,we can formulate the 11:end while TSA problem by means of ILP.Denote a set of variable 12:return true subrequirements whose collision probability is no more than The resemblance between the two problems inspires us Puh as a pattern.Denote the number of all possible patterns as to adopt the core idea of first-fit and design the "first-fit m.For each possible pattern j,let jrepresent the times that by collision probability"algorithm,shown in Algorithm 2. pattern j appears in a feasible assignment.Thus,the TSA In the algorithm,N is the total number of substrate time problem can be formulated as slots,and D;is the set of subrequirements that the jth substrate time slot is assigned to;the function min i getCollision Pro(Dinder,pi)returns the collision probability of subrequirements Dinder Ufi}and can be implemented (2) st.(a)≥，i∈{L,2,n}, in an incremental manner.Let A(D)=Π1-pm), rj,nonnegative integer,vie{1,2,...,m}, hEDi where aji indicates whether pattern j contains the ith subrequirement.Ideally,(2)can be optimally solved using intelligent exhaustive search approaches,such as back- tracking and branch-and-bound [24].However,it is not Then,the collision probability in (1)can be rewritten as practical.First,the number of possible patterns can be Pr(Di)=1-A(Dj)-B(Dj).We have exponentially large,the construction of which costs ex- A(DU{i})=A(D)1-), ponential time;second,the intelligent exhaustive search (3) approach usually consists of a systematic enumeration of all B(DU{i)=B(D)(1-)+A(D)P. candidate solutions,which is also difficult to apply in Let us look at the performance guarantee of CFF.Denote practice.This motivates us to design practical solutions, by Seff the assignment results from CFF,and by Sopt the which are introduced in the next two sections. results from the optimal solution.Abusing the notation a bit,we also use Seff and Sopt to denote the number of 1.Cutting stock problem [26].Given a number of rolls of paper of fixed width waiting to be cut,yet different customers want different numbers of substrate slots used in these results,respectively,if no rolls of various-sized widths,find a cutting method to minimize the waste. confusion can be caused.Letslots assigned to it is at least vi; and 2) the collision probability at each substrate time slot is no more than a given collision threshold pth. For example, Fig. 3 shows a feasible assignment. ts1 can be assigned to two variable subrequirements because they collide with a probability 0.08, which is less than pth ¼ 0:1; however, ts4 cannot be assigned to the second and fourth subrequirements simultaneously, because the collision probability 0.12 is larger than pth. For the hardness of the TSA problem, we have the following theorem: Please refer to the supplemental material, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/ 10.1109/TPDS.2013.64, for the detailed proofs of all the theorems in this paper. Theorem 1. TSA is NP-hard in the strong sense. 5.2 An ILP-Based Optimal Solution Inspired by the cutting stock problem,1 we can formulate the TSA problem by means of ILP. Denote a set of variable subrequirements whose collision probability is no more than pth as a pattern. Denote the number of all possible patterns as m. For each possible pattern j, let xj represent the times that pattern j appears in a feasible assignment. Thus, the TSA problem can be formulated as minXm j¼1 xj; s:t: Xm j¼1 ðajixjÞ  vi; 8i 2 f1; 2; ... ; ng; xj; nonnegative integer; 8j 2 f1; 2; ... ; mg; ð2Þ where aji indicates whether pattern j contains the ith subrequirement. Ideally, (2) can be optimally solved using intelligent exhaustive search approaches, such as back￾tracking and branch-and-bound [24]. However, it is not practical. First, the number of possible patterns can be exponentially large, the construction of which costs ex￾ponential time; second, the intelligent exhaustive search approach usually consists of a systematic enumeration of all candidate solutions, which is also difficult to apply in practice. This motivates us to design practical solutions, which are introduced in the next two sections. 5.3 First-Fit by Collision Probability In the bin packing problem [23], we are given n items with sizes s1; s2; ... ; sn 2 ð0; 1, and the objective is to find a packing method in unit-sized bins that minimizes the number of bins used. We observe that, when each variable subrequirement requires only one time slot, i.e., vi ¼ 1 for all 1  i  n, TSA is similar to bin packing, except that the size of multiple items is the sum of them in bin packing; the collision probability of multiple subrequirements is neither linear nor multiplicative, as shown in (1). The first-fit algorithm [23] is a greedy approximation algorithm of factor 2 for bin packing. In first-fit, items are considered in an arbitrary order, and for each item, first-fit attempts to place the item in the first bin that can accommodate the item. If this is not possible, the item is placed into a new bin. First-fit can be executed online and has a low time complexity. Algorithm 2. First-Fit by Collision Probability (CFF). 1: Input: vi and pi 2: cnt 0, index 0 3: while cnt < vi do 4: while getCollistionP roðDindex; piÞ > pth do 5: index index þ 1 6: if index > N return false 7: end while 8: Dindex Dindex [ fig 9: cnt cnt þ 1, index index þ 1 10: if index > N return false 11: end while 12: return true The resemblance between the two problems inspires us to adopt the core idea of first-fit and design the “first-fit by collision probability” algorithm, shown in Algorithm 2. In the algorithm, N is the total number of substrate time slots, and Dj is the set of subrequirements that the jth substrate time slot is assigned to; the function getCollisionP roðDindex; piÞ returns the collision probability of subrequirements Dindex [ fig and can be implemented in an incremental manner. Let AðDjÞ ¼ Y h2Dj ð1  phÞ; BðDjÞ ¼ X h2Dj ph Y k2Dj ; k6¼h ð1  pkÞ : Then, the collision probability in (1) can be rewritten as P rðDjÞ ¼ 1  AðDjÞ  BðDjÞ. We have AðDj [ figÞ ¼ AðDjÞð1  piÞ; BðDj [ figÞ ¼ BðDjÞð1  piÞ þ AðDjÞpi: ð3Þ Let us look at the performance guarantee of CFF. Denote by Scff the assignment results from CFF, and by Sopt the results from the optimal solution. Abusing the notation a bit, we also use Scff and Sopt to denote the number of substrate slots used in these results, respectively, if no confusion can be caused. Let 820 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 25, NO. 3, MARCH 2014 1. Cutting stock problem [26]. Given a number of rolls of paper of fixed width waiting to be cut, yet different customers want different numbers of rolls of various-sized widths, find a cutting method to minimize the waste. Fig. 3. The time slot assignment problem. The probability threshold serves as the “volume” of a substrate time slot.