Reponse time variability

Response time variability Albert Corominas, Wieslaw Kubiak, Natalia Moreno Palli IOC-DT-P-2004-08 Maig 2004 Response Time Variability 1 Albert Corominas a, Wieslaw Kubiakb, Natalia Moreno Pallib aInstitut d’Organitzaci´o i Control de Sistemes Industrials Universitat Polit`ecnica de Catalunya Barcelona, Spain bFaculty of Business Administration Memorial University of Newfoundland St. John’s, Canada April 29, 2004 Abstract: This paper presents a work-in-progress on the response time variability problem. This problem occurs whenever events, jobs, clients or products need to be sequenced so as to minimize the variability of time they wait for their next turn in obtaining the necessary resources. The problem has numerous real-life applications, which will be briefly reviewed. The problem has distinctive number theoretic flavor. We study its computational complexity, present efficient, polynomial time algorithms for some cases and the NP-completeness proof for a general problem. We then propose a position exchange heuristic and apply it to improve the response time variability of an initial sequence. The latter is obtained in various ways: the optimum bottleneck sequence, Webster and Jefferson sequences of the apportionment, or randomly. We report on computational experiments with the heuristic. 1. Introduction Most modern systems shares its resources between different jobs. The jobs define a certain amount of work to be done, for instance the file size to be transmitted to or from a server or the number of cars of a particular model to be produced on a mixed-model assembly line. To ensure fair sharing of common resources between different jobs, this work is divisible in atomic tasks, for instance data blocks or 1This research has been supported by the Natural Sciences and Engineering Research Council of Canada grant OPG0105675 and by the Ministerio de Ciencia y Technologia of Spain project DPI2001-2176. 1 2 cars. These tasks, in turn, are required to be evenly distributed so that the distance between any two consecutive tasks of the same job is as regular as possible, in other words, ideally constant. The following are some real-live examples. The Asynchronous Transfer Mode (ATM) networks divide each application (voice, large data file, video) into cells of fixed size so that the application can be preempted after each cell. Furthermore, isochronous applications, for instance voice and video, require that a inter-cell distance in a cell stream be as close to being constant as possible and in the worst case not exceeding some pre-specified value. The latter is to account for limited resources shared with other applications, Han, Lin, and Hou [9], and Altman, Gaujal and Hordijk [1]. In fact multimedia systems should avoid presenting video frames too early or too late which would result in jagged motion perceptions. On a mixed-model, just-in-time assembly line a sequences of different models to produce is sought where each model is distributed as ”evenly” as possible but appears a given number of times to satisfy demand for different models. Consequently, shortages, on one hand, and excessive inventories, on the other, are reduced, Monden [14]. The stride scheduling is a deterministic scheduling technique where each client is first issued a number of tickets. The resources are then allocated in discrete time slices called quanta. The client to be allocated resources in next quantum is calculated as a certain function of the number of allocations obtained in the past and the number of tickets issued, Waldspurger, and Weihl [17]. This paper considers the throughput error and the response time variability as two main metrics of the schedule obtained. These problems are often considered as the distance-constrained scheduling problems, where the temporal distance between any two consecutive executions of a task is not longer that a pre-specified distance, Han, Lin, and Hou [9]. Sometimes even stronger condition is imposed that the temporal distance is equal to the pre-specified distance, constant gaps discussed by Altman, Gaujal and Hordijk [1], see also Anily, Glass and Hassin [2], where periodic machine maintenance problem is considered with equal distances between consecutive services of the same machine. The distance-constrained model, however, suffers from a serious problem which is that there may not be a feasible solution that respects the distance constraints and at the same time makes sure that tasks are done at given rates. In this paper, we propose the response time variability metric instead to avoid the feasibility problem but at the same time preserve the main idea of having any two consecutive 3 tasks at a distance which remains as constant as the existing resources and other competing tasks allow. We formulate the problem as follows. Given are npositive integers d1≤... ≤dn, define D=Pn i=1 di and ri=di D. Consider a sequence s=s1s2. . . sDof length Dwhere i (client, product or task) occurs exactly ditimes. Such sequence will be called feasible. For di≥2, for any two consecutive occurrences of i define a distance tbeing the number of positions that separate the two plus 1. This distance will also be referred to as the end-to-end distance between the two occurrences. Since ioccurs exactly ditimes in s, then there are exactly didistances ti 1,...,ti difor i, where tdiis the distance between the last and the first occurrence of i. Since ti 1+...+ti di=D, then the average distance tibetween the i’s in sequals D di =1 ri , and it is the same for each feasible sequence s. We define the response time variability for ias follows RT Vi=X 1≤j≤di (ti j−ti)2, and the response time variability as RT V = n X i=1 RT Vi= n X i=1 X 1≤j≤di (ti j−ti)2. We observe that the response time variability is a weighted variance with weights being equal to demands, that is RT V = n X i=1 diV ari, where V ari=1 diP1≤j≤di(ti j−ti)2. We also consider the maximum deviation just-in-time sequencing problem, or the bottleneck minimization problem. We shall use the term throughput error (TE) as well in the paper. Let xi,k be the number of occurrences of iin the k-prefix of s, that is in s1. . . sk. B∗= min max i,k |xi,k −kri| 4 Subject to xi,k ≤xi,k+1 for i= 1,...,n and k= 1,...,D−1 Pn i=1 xi,k =kfor k= 1,...,D xi,k non-negative integers for i= 1,...,n and k= 1,...,D. The plan for the paper is as follows. Section 2 studies the optimization and the computational complexity of the response time variability problem. It first introduces the number decomposition graphs as a useful tool for the analysis of the response time variability. Second, it shows an optimization algorithm for two product case. The algorithm minimizes both the response time variability and the bottleneck at the same time. Third, the section shows a dynamic programming algorithm to prove polynomial solvability for a fixed number of products. Finally, it proves that the problem is NP-complete. Section 3 presents optimization algorithms for the response time variability. Section 4 presents a simple position exchange heuristic that takes a sequence exchanges positions of some products as long as the exchanges lead to improvements in the value of RTV . The sequences subjected to this exchange heuristic are generated by various procedures: the bottleneck that solves the bottleneck problem to optimality, insertion based on a solution to the two product case, Webster and Jefferson based on the well known methods of the apportionment. These are described in Section 4.2. Section 5 presents results of computational experiments with the exchange heuristic as well as very limited experiment with an optimization algorithm based on mathematical programming. Finally, Section 6 presents conclusions and remarks on further research. 2. Optimization and Complexity 2.1. Number Decomposition Graphs vs RTV. For product i, consider a vector α= (α1, . . . , αdi) of di≥2positive integers that sum up to D. Without loss of generality we assume the coordinates of αordered in descending order, that is α1≥... ≥αdi. Any vector αthat meets the above conditions will be referred to as the decomposition vector of Dinto dicomponents. Now let us define a unit exchange operation on the decomposition vector αas follows. Consider two components αj and αk>1, j < k, of α. Replace αjby αj+ 1 and αkby αk−1 and keep all other components of αunchanged. The new components after ordering them define another decomposition vector β. For instance, consider α= (6,6,5), then adding 1 to the second component and subtracting 1 from the third component leads to the vector β= (7,6,4). Let us consider a weighted directed graph Di, we refer to this graph as the number decomposition graph for product i, with the set of nodes 5 Niincluding all decomposition vectors of Dinto dicomponents, and the set of arcs Aiincluding all pairs of decomposition vectors (α, β) such βis obtained from αby a unit exchange operation. The weight of the arc (α, β) is defined as 2(αj−αk+ 1). We have the following straightforward properties of Di. Lemma 2.1. The following properties hold for Di: •The graph Diis acyclic with a single maximal node, Ni, and a single minimal node, Mi. • Ni= (⌈D di ⌉,...,⌈D di ⌉ |{z } Dmod di ,⌊D di ⌋,...,⌊D di ⌋ |{z } di−Dmod di ). • Mi= (D−di+ 1,1,...,1 |{z } di−1 ). Proof. If (α, β)∈ Ai, then n X i=1 α2 i< n X i=1 β2 i. Therefore, Dimust be acyclic. The node Nihas in-degree 0. Otherwise, there would be a node αin Disuch that (α, Ni)∈ Ai. Then, there would be two components αjand αk>1, j < k, of αthat would become some components αj+ 1 and αk−1 of Ni. Then, αj+ 1 must be either ⌊D di⌋or ⌈D di⌉. Consequently, αjmust be either ⌊D di⌋ − 1 or ⌈D di⌉ − 1. Then, however, αk−1≤ ⌈D di⌉ − 2≤ ⌊D di⌋ − 1, and thus αk−1 cannot be a component of Ni. No other node has in-degree 0 since it can be shown that there is a path from Nito the node in Di. Finally, by definition the only node with out-degree 0 is the one that has the last dicomponents all equal 1. Otherwise a unit exchange would be possible. However, since all components of any node must sum up to di, there is only one such a node, namely Mi. Figure 1 presents the number decomposition graph for D= 16 and di= 3. Consider Niand another node αin Di. The length of a directed path from Nito αis the sum of all the weights along the path. We have the following lemma. Lemma 2.2. For any node αin Di, all directed paths from Nido α have the same length. 6 6, 5, 5 6, 6, 4 7, 5, 4 7, 6, 3 8, 5, 3 8, 4, 4 7, 7, 2 8, 6, 2 9, 4, 39, 5, 2 8, 7, 1 9, 6, 1 10, 5, 1 10, 4, 2 11, 4, 1 12, 3, 1 13, 2, 1 14, 1, 1 2+4+ 2+ 6+ 4+ 8+6+ 2+ 8+10+6+ 12+10+ 12+ 10+ 2+ 14+ 6+ 8+ 4+ 14+8+16+ 4+8+ 10+ 6+ 12+18+ 16+ 20+ 24+ 4+ Figure 1. The number decomposition graph for D=16 and di= 3. Proof. For a node α∈ Didefine RT V (α) = n X j=1 (αj−D di )2. Let pbe any path from Nito α, and w(p) its total weight. It can be shown that RT V (α) = RT V (Ni) + w(p). This, however, implies the lemma since both RTV (α) and RTV (Ni) are constants, that is path independent. The following lemma links the decomposition graphs and the response time variability problem. Lemma 2.3. Let Sbe a solution to the response time variability problem with value RT V . Then there are nodes α1,...,αnin the decomposition graphs D1,...,Dnrespectively, such that RT V = n X i=1 w(Ni, αi) + n X i=1 RT V (Ni), 7 where w(Ni, αi)is the length of a directed path from Nito αiin Diand RT V (Ni) = (Dmod di)(⌈D di ⌉ − D di )2+ (di−Dmod di)(⌊D di ⌋ − D di )2 for i= 1,...,n. Proof. Follows from Lemma 2.2. 2.2. Two Product Case. This section considers a two product case. It shows a solution that minimizes both the response time variability and the maximum deviation at the same time, which generally is impossible for more than two products. Prior to giving the details of the solution we need to point out that the sequence minimizing the response time variability for two products is quite straightforward to obtain as follows. Let d1< d2. We omit the case d1=d2since it is trivial. It follows from our discussion in Subsection 2.1 that if one can find a solution with distances ⌈D d1⌉and ⌊D d1⌋for product 1, and ⌈D d2⌉and ⌊D d2⌋for product 2, then this solution will be optimal. We notice, however, that such solution is always possible since ⌊D d1⌋ ≥ 2 and 2 >D d2>1. Therefore, starting a sequence with product 1 and then sequencing any consecutive copy of 1 at a distance either ⌈D d1⌉or ⌊D d1⌋(the number of times each distance is used is given in Lemma 2.3) from the last one will produce the sequence where empty positions are separated by at most a single copy of product 1. This allows us to fit in product 2 in the empty positions ensuring the desired distances for product 2. We now discuss details of the solutions that minimizes both the response time variability and the maximum deviation. We assume that the greatest common divisor of d1,d2, and D=d1+d2is 1, that is gcd{d1, d2}= 1. Otherwise, the optimal solution for d1 gand d2 gcan be repeated g= gcd{d1, d2}times resulting into an optimal solution with respect to both metrics for the original instance with demands d1and d2. Our solution relies on the ideal positions for copy jof product i,i= 1,2 and j= 1,...,didefined as ⌈2j−1 2ri⌉, see Kubiak and Sethi [10]. We consider two cases. One with one demand being odd and the other even is easier to deal with since then all the ideal positions are pairwise different. The other with both demands being odd is a bit more involved since then there may be two ideal positions with the same value creating a conflict for two copies. 8 Lemma 2.4. Consider numbers aj=2j−1 2r1for j= 1,...,d1and bk= 2k−1 2r2for k= 1,...,d2. If l−1< aj≤land l−1< bk≤lfor some l= 1,...,D, then aj=bk=l. Proof. Since aj=2j−1 2r1= (l−1) + f1and bk=2k−1 2r2= (l−1) + f2, with 0 < fi≤1 (i= 1,2), we have 2j−1 = 2r1(l−1) + 2r1f1 2k−1 = 2r2(l−1) + 2r2f2 and, since r1+r2= 1 j+k−1 = (l−1) + r1f1+r2f2 which, as the left-hand side of the equation and (l−1)are integers, can only be possible if r1f1+r2f2is also integer; however, 0 < r1f1+r2f2≤ 1, since r1f1+r2f2≤(r1+r2) max (f1, f2) = max (f1, f2)≤1, and is equal to 1 if and only if f1=f2= 1. Lemma 2.5. If one of demands, d1and d2, is odd and the other even than none of the numbers aj=2j−1 2r1for j= 1,...,d1and bk=2k−1 2r2for k= 1,...,d2is an integer. Proof. If one of demands, d1and d2, is odd and the other even, then Dis odd and, consequently, (2j−1)Dis odd, j= 1,...,diand i= 1,2. Since 2diis even, then (2j−1)D 2di=2j−1 2riis not an integer for j= 1,...,di and i= 1,2. Lemma 2.6. If one of demands, d1and d2, is odd and the other even, then αj=⌈aj⌉for j= 1,...,d1and βk=⌈bk⌉for k= 1,...,d2are pairwise different. Proof. Follows immediately from Lemma 2.4 and Lemma 2.5. Lemma 2.7. If both d1and d2are odd, than none of the numbers aj=2j−1 2r1for j= 1,...,d1+1 2−1,d1+1 2+ 1,...,d1and bk=2k−1 2r2for k= 1,...,d2+1 2−1,d2+1 2+1,...,d2is integer. However, both ad1+1 2 and bd2+1 2 =D 2are integers equal D 2. 15 Instead, the use of CPLEX with MILP models derived from the QIP turned out to be more efficient, as a computational experiment showed. In order to linearize the QIP model three techniques were applied: (i) Substitute the binary variables δikhjfor the products yikh ·yi,k+1,j and include the constraints: 1 + δikhj ≥yikh +yi,k+1,j. (ii) Substitute the binary variables δikhjfor the products yikh ·yi,k+1,j and include the constraints: 2·δikhj ≤yikh +yi,k+1,j 1 + δikhj ≥yikh +yi,k+1,j. (iii) Introduce the binary variables δj ik (i∈G1; k= 1, ..., di;j= 1, ..., UBi), substitute the objective function for P i,k,j j2·δj ik and include the constraints: X h hyi,k+1,h −X h hyikh =δ1 ik +... +j·δj ik +... +UBi·δUBi ik D−X h∈Hidi hyi,di,h +X h∈Hi1 hyi1h=δ1 ik +... +j·δj ik +... +UBi·δUBi ik UBi X j=1 δj ik = 1 ∀i, k (which allows suppressing the precedence constraints, since they are embedded in the new ones). The lower computing times were those corresponding to the model obtained by technique (iii). Therefore, this was the model that we used to compare the solutions obtained by heuristics with optimal solutions in the computational experiment described in Section 5. Notwithstanding, the experiments indicate that the practical limit to get optimal solutions applying CPLEX to this model is D= 25. 4. Heuristics This section describes heuristics for the response time variability problem. Each of these heuristics uses the exchange procedure described in Subsection 4.1 to exchange products next to each other in a given sequence in order to reduce the sequence’s response time variability. The exchange procedure can be applied to any feasible sequence, 16 and as expected its result is rather sensitive to the selection of the initial sequence it is applied to. Therefore, in Subsection 4.2 we describe a number of different ways the initial sequence was obtained in our study. 4.1. The Exchange. Consider a sequence s=s1. . . sDand a product iwith di≥2 in position pof s, that is sp=i. We define the closest to position pclockwise ias the first iin sencountered when moving clockwise away from p, similarly, we define the closest to pcounterclockwise ias the first iencountered when moving counter-clockwise away from p. Notice that if di= 2, then that the clockwise iis the same as the counter-clockwise i. The Exchange Heuristic does the exchange of two products that are next to each other whenever the exchange leads to the reduction of response time variability. More precisely, consider products iand j,i6=j, that are next to each other in a given sequence s, assume the iis in position pand the jin position p+ 1. Let Liand Ribe distances to the closest to pclockwise, respectively counter-clockwise, iin s. Similarly, let Ljand Rjbe distances to the closest to p+ 1 clockwise, respectively counter-clockwise, jin s. Then, for di, dj≥2, B=L2 i+R2 i+L2 j+R2 j before the exchange and A= (Li+ 1)2+ (Ri−1)2+ (Lj−1)2+ (Rj+ 1)2 after the exchange. Since all the other distances remain unchanged, we have the following net change in the value of the response time variability, ∆ = B−A= 2(Li−Ri+ 1) + 2(Rj−Lj+ 1). If dj= 1 and di≥2, then ∆ = 2(Li−Ri+ 1).By symmetry, if di= 1 and dj≥2, then ∆ = 2(Lj−Rj+ 1). Finally, if di=dj= 1, the ∆ = 0. The exchange takes place only if ∆ is positive. The exchange algorithm passes counter-clockwise through the sequence and checks for each neighboring couple spsp+1 if the exchange within the couple reduces the response time variability, if so, the exchange is made and the algorithm moves to position p+ 1. It is worth keeping in mind that position Dis immediately followed by position 1. If position 1 is reached without any reduction in the response time variability, then the heuristic stops. Otherwise, the next pass through the sequence begins. We observe that the heuristic eventually stops since each pass either reduces the response time variability, an optimal value of which 17 is obviously finite, or no improvement takes place. In fact the exchange heuristic goes a bit further, namely, whenever no improvement is possible in a given pass it tries to do the exchanges even if their net improvement is 0. However, these exchanges are only done if the maximum distance for either of the two products being exchanged does not increase and moreover at least one of the maxima actually decreases. This last condition ensures that the heuristic actually terminates. The exchange heuristic is applied to an initial sequence which is generated in a number of different ways. These will be detailed in the subsequent sections. 4.2. The Initial Sequences. 4.2.1. Bottleneck (minimum throughput error) sequences. Bottleneck sequences have been obtained by solving to optimality the bottleneck problem defined in the Introduction. We used the algorithm of Moreno, 2002 to solve the bottleneck problem. However, other approaches have been proposed in the literature and could be used to obtain, perhaps different, bottleneck sequences( see Kubiak [11], Steiner and Yeomans [16], and Bautista, companys and Corominas [6]). 4.2.2. Random sequences. The bottleneck sequence shas been randomized as follows. For each position xin 1..D, get a random number ran in the range 1..D. Then, swap S[x] with S[ran]. 4.2.3. Webster’s sequences. These sequences have been obtained by applying the parametric method of apportionment with parameter δ=1 2 , known as Webster’s method (Balinski and Young [3], Bautista, Companys and Corominas [5]). The sequence is generated as follows. Consider xit the number of product icopies in the sequence of length t,t= 0,1,.... Assume xi0= 0, i= 1,...,n. The product to be sequenced in position t+ 1 can be computed as follows i∗= arg maxi{di (xit+δ)}. 4.2.4. Jefferson’s (stride scheduling) sequences. These sequences have been generated by applying the parametric method of apportionment, described before, with δ= 1 , known as Jefferson’s parametric method (Balinski and Young [3]). The stride scheduling technique produces the same sequences as shown by Kubiak [13]. 4.2.5. Insertion sequences. Recall that d1≤...≤dn. Consider n−1, two-product problems Pn−1= (dn−1, dn), Pn−2= (dn−2,Pn j=n−1dj), ...,P1= (d1,Pn j=2 dj). In each of the problems Pn−1, Pn−2,...,P1, the first product is the original one, that is n−1, n−2,...,1 and the second product will be the same (fictitious product) for all problems, and 18 denoted by ∗. Let sequences Sn−1, Sn−2,...,S1be the optimal solution for problems Pn−1, Pn−2,...,P1respectively. They can be obtained by the algorithm described in Section 2.2. Notice that the sequence Sj, j=n−1,...,1, is made up of the product jand ∗. Then the sequence for the original problem is built recursively by first replacing ∗in S1 by S2to obtain S′ 1. Notice that the latter is made up of products 1, 2, and ∗. Next, ∗are replaced by S3in S′ 1to obtain a sequence S′′ 1made up of products 1, 2, 3 and ∗. Finally, sequence Sn−1replaces all the remaining ∗and thus we obtain a sequence, referred to as the insertion sequence, where product ioccurs exactly ditimes. 5. Computational Experiments The computational experiment has been carried out in order to study how the Exchange heuristic affects two metrics, throughput error and response time variability. The experiment consists of applying the Exchange heuristic to earlier described initial sequences and analyzing the main metrics. In this report we include only the main results. All codes have been implemented in C++ and executed on a X86based PC with 500 Mhz processor and 128 MB of RAM. Instances for this experiment are generated by fixing the total number of units Dand number of products n, and randomly selecting the number of copies of each product, di, which are uniformly distributed. A total of 6650 instances have been run for different (D, n) values, which are as follows: D= 100, n : (3,10k, k = 1,...,9) D= 500, n : (3,5,10,50k, k = 1,...,9) D= 1000, n : (10,50,100k, k = 1,...,9) D= 1500, n : (100k, k = 1,...,14) 5.1. Computational Results. The Exchange heuristic has been designed for the problem of minimization of the response time variability (RTV). Therefore, RTV was considered as a main metric to examine, while the throughput error (TE) for the sequence was included as a secondary metric. The computational results have shown that, on average, much lower values of final response time variability have been reached after the application of the Exchange heuristic to the initial bottleneck, random and insertion sequences. Moreover, the bottleneck and insertion sequences have produced final sequences with small final throughput 19 errors, although, as expected, the TEs of bottleneck sequences’ have increased with respect to the initial TE, while for the insertion sequences they have, on average, decreased. The Webster’s and Jefferson’s sequences have resulted in the final sequences with values of RTV comparable to the bottleneck and insertion sequence only for very small values of n. For larger n, on average, their RTV was higher than for the bottleneck, random and insertion sequences. The same has been observed about the change in the values of TE. For small n, the TE has been in the same range as the values of TE for bottleneck and insertion sequences, while TE significantly grew when nincreased. For these reasons we do not include the computational results with neither Webster’s nor Jefferson’s sequences in Tables 1-4. On average, final TE for bottleneck sequences is lower than the final throughput error for random sequences. For small and large nvalues the bottleneck sequences result in lower RTV, while on average, random sequences perform slightly better with regard to RTV. To sum up, with respect to the reduced RTV value, the most promising initial sequences were bottleneck, random and insertion sequences. The change in Response Time Variability (RTV) and Throughput Error (TE) for bottleneck, random and insertion initial sequences, for each value of Dis presented in Tables 1-4. The first column contains values of n, the second column includes the averages of RTV for bottleneck sequences for each n(we call them initial RTV). The averages are rounded to integers for ease of understanding. The third column is composed of averages of reduced RTV values (we call them final RTV). The fourth column contains averages of optimum throughput error (initial TE) and the fifth column their final values (final TE). The same order is for the other two initial sequences, that is random and insertion. Initially, we have compared only two sequences (bottleneck and random) and concluded that bottleneck sequences result in lower response time variability in 54% of cases; random sequences result in lower response time variability in 41% of cases; for 5% of cases the two coincide. The insertion method sequences seem to perform well with regard to both metrics, throughput error and response time variability, but on average, the random sequences still perform better with regard to response time variability. Finally, for very small values of n, the best sequences, resulting in lower RTV, are bottleneck sequences. The instances with ratio: n D≈0.1−0.5 can be considered as the worst cases with regard to the reduced RTV value. It has been observed (see tables) that for these instances the values of reduced RTV are 20 Table 1. The exchange improvements on the Bottleneck, Insertion and Random initial sequences for D=100. n: Bottleneck Random Insertion Init RTV Final RTV Init TE Final TE Init RTV Final RTV Init TE Final TE Init RTV Final RTV Init TE Final TE 3 43 26 0.639 0.738 1377 71 4.052 2.726 31 26 0.757 0.766 1 0 539 86 0.794 1.220 8868 143 4.114 2.454 306 101 1.232 1.188 2 0 2763 105 0.856 1.522 10424 142 4.178 2.608 498 104 1.120 1.059 3 0 3447 139 0.880 1.347 15598 120 3.562 1.828 1539 85 1.199 1.063 4 0 4908 172 0.923 1.337 32549 70 3.183 1.521 3307 71 1.263 1.033 5 0 8621 94 0.938 1.431 32280 51 2.908 1.546 2609 57 1.223 1.081 6 0 12100 35 0.946 1.128 31413 31 2.715 1.410 1840 31 0.995 0.990 7 0 15111 17 0.954 1.182 23834 25 2.616 1.510 687 11 0.990 0.990 8 0 20029 10 0.958 1.087 17576 15 2.338 1.194 187 4 0.990 0.990 9 0 20296 3 0.967 0.990 10381 3 1.876 0.995 17 2 0.990 0.990 Table 2. The exchange improvements on the Bottleneck, Insertion and Random initial sequences for D=500. n: Bottleneck Random Insertion Init RTV Final RTV Init TE Final TE Init RTV Final RTV Init TE Final TE Init RTV Final RTV Init TE Final TE 3 82 73 0.651 0.677 2959 608 10.605 9.670 108 92 0.724 0.713 51081 177 0.748 1.170 27032 1224 9.379 7.010 285 183 1.218 1.170 1 0 3403 409 0.825 1.200 82248 2441 9.441 7.336 993 443 1.260 1.199 5 0 63498 1948 0.939 1.593 1000332 2384 6.607 3.534 29925 2256 1.549 1.323 10 0 153664 1404 0.960 2.036 1492918 1207 7.111 4.797 106108 1313 1.509 1.190 15 0 234034 4086 0.977 2.637 3372643 871 5.181 2.811 300787 1353 2.153 2.140 20 0 461694 1497 0.980 1.285 3730674 593 4.487 2.115 344989 1036 1.252 1.032 25 0 719887 496 0.985 1.433 4069915 345 5.008 3.431 380971 496 1.116 1.016 30 0 1245583 255 0.987 1.290 3800175 289 4.631 3.041 244113 236 1.031 1.003 35 0 1578706 86 0.987 1.365 2573962 306 5.136 3.731 88601 56 0.998 0.998 40 0 3079086 38 0.991 1.075 2788306 137 3.197 1.951 32116 20 0.998 0.998 45 0 1996168 41 0.991 1.089 1063597 149 3.300 1.646 1580 9 0.998 0.998 much higher than for instances corresponding to other nvalue. This is also shown by the averages of maximum differences between maximum and minimum distances. For these instances averages of maximum difference in improved sequences are higher than in other cases. The time it takes to do the exchanges with the Exchange heuristic is almost negligible. It depends on both Dand n D. The longest times are reached for instances with ratio n D≈0.4−0.5 and for instances with a very small difference between dnand d1. Average reduction times (clock time) have been: in range of 0 −1 sec for D= 500, range of 0−7 sec for D= 1000, and of 0 −20 sec for D= 1500. As a part of our computational experiment we also compared heuristic solutions with optimum obtained by solving the MILP described in 21 Table 3. The exchange improvements on the Bottleneck, Insertion and Random initial sequences for D=1000. n: Bottleneck Random Insertion Init RTV Final RTV Init TE Final TE Init RTV Final RTV Init TE Final TE Init RTV Final RTV Init TE Final TE 1 0 17904 601 0.837 1.503 253685 5435 13.327 10.985 1546 625 1.461 1.406 5 0 180503 3208 0.936 2.004 2706679 7407 9.704 6.219 49101 4242 1.761 1.570 10 0 636545 4946 0.964 2.289 7130615 6375 8.812 5.564 253319 5866 2.207 1.825 20 0 1020847 8412 0.978 2.931 13476818 3517 7.662 4.596 873579 5032 2.039 1.977 30 0 1418033 6120 0.985 3.555 16271934 2266 8.605 6.400 1376361 2717 2.166 2.153 40 0 3574364 3913 0.991 4.754 35047637 1195 6.339 4.203 3584645 3395 3.512 3.409 50 0 6232671 1162 0.992 2.327 35083775 862 5.883 4.006 3290617 1313 1.856 1.574 60 0 7681994 496 0.992 1.648 21386442 962 7.549 5.924 1321738 375 1.049 1.014 70 0 12206931 179 0.993 1.407 20496095 952 6.716 5.093 706786 130 1.007 1.001 80 0 18083157 334 0.994 1.466 15952258 697 5.431 3.676 184422 84 1.163 1.071 90 0 15549203 82 0.996 1.181 8299817 472 4.421 2.685 14832 18 1.004 1.001 Table 4. The exchange improvements on the Bottleneck, Insertion and Random initial sequences for D=1500. n: Bottleneck Random Insertion Init RTV Final RTV Init TE Final TE Init RTV Final RTV Init TE Final TE Init RTV Final RTV Init TE Final TE 10 0 885866 8780 0.967 2.005 13310978 13475 10.325 6.394 318918 11125 1.752 1.462 20 0 3206865 10985 0.977 2.209 28313115 10532 10.292 6.582 1554419 12273 1.732 1.320 30 0 3243331 13577 0.986 1.833 51059006 5475 8.309 5.019 3611346 9623 1.696 1.166 40 0 4996223 23905 0.989 1.874 73166821 4048 8.200 5.157 6624499 8586 1.608 1.190 50 0 6458663 10564 0.991 1.808 82218609 3517 6.980 4.284 8396917 7558 1.446 1.140 60 0 11085096 4866 0.992 1.534 98681397 2208 7.225 4.847 9990472 4804 1.425 1.070 70 0 14593169 2051 0.994 1.646 116870944 1628 7.574 5.671 10742017 3627 1.236 1.049 80 0 24081386 1309 0.994 1.472 110641048 1369 6.394 4.217 8495253 1501 1.147 1.038 90 0 36781821 1007 0.995 1.316 112399627 1086 5.888 3.884 7107165 1068 1.076 1.016 100 0 49367053 298 0.995 1.215 100131267 990 5.423 3.641 4335813 442 1.022 1.003 110 0 67535885 150 0.996 1.179 90861641 893 4.934 3.286 2475907 259 1.003 0.999 120 0 78982366 116 0.996 1.123 71570932 620 4.542 2.964 966875 70 0.999 0.999 130 0 83546651 82 0.997 1.067 52228958 632 4.213 2.737 201881 29 0.999 0.999 140 0 60688751 65 0.997 1.038 27742011 360 3.179 1.697 14809 8 0.999 0.999 Section 3. The MILP has been applied to 389 instances, for D=10, 15, 20 and 25 and different values of n. The results are presented in Table 5. For most instances the optimal solutions have been reached within 300 sec. Nevertheless, for some instances, 39 out of 389, the number of nodes of the branch-and-bound tree was increasing dramatically after the first 180 sec. and the execution was aborted, for these instances the best objective function value has been kept, however, these instances 22 Table 5. The comparison of the exchange heuristic for different initial sequences with optimal solutions. D n [1] [2] Insertion Webster Jefferson Bottleneck Random [6] [3] [4] [5] [3] [4] [5] [3] [4] [5] [3] [4] [5] [3] [4] [5] 10 3 8 0 7 0.500 4 8 0.000 0 8 0.000 0 8 0.000 0 8 0.000 0 8 4 7 0 5 0.857 4 6 0.286 2 5 0.857 4 5 0.857 4 5 0.857 4 7 5 7 0 3 1.429 4 2 2.286 6 6 0.571 4 2 2.286 6 4 0.857 2 7 6 5 0 4 0.400 2 3 0.800 2 4 0.400 2 5 0.000 0 5 0.000 0 5 7 3 0 3 0.000 0 3 0.000 0 3 0.000 0 2 0.667 2 3 0.000 0 3 8 2 0 2 0.000 0 2 0.000 0 2 0.000 0 2 0.000 0 2 0.000 0 2 9 1 0 1 0.000 0 1 0.000 0 1 0.000 0 1 0.000 0 1 0.000 0 1 for D=10 33 025 25 29 25 28 33 15 312 010 1.33310 10 0.667 6 11 0.500 611 0.167 2 9 0.833 412 416 012 1.375 8 13 1.000 8 11 1.375 614 0.875 814 0.375 416 514 0 6 3.57116 81.286 8 8 1.429 4 8 1.000 410 0.571 212 713 0 5 3.23116 17.38516 24.308 10 15.846 16 52.769 10 7 9 9 0 7 0.667 4 3 3.77812 32.444 6 3 4.000 14 70.444 2 9 11 4 0 4 0.000 0 3 0.500 2 3 0.500 2 3 0.500 2 2 2.000 6 4 13 2 0 2 0.000 0 2 0.000 0 2 0.000 0 2 0.000 0 2 0.000 0 2 for D=15 70 046 40 40 42 49 62 20 319 015 0.947 8 15 0.632 4 14 0.842 416 0.421 412 2.105 16 18 417 011 1.76514 11 1.176 8 9 1.529 813 0.471 211 0.824 414 517 3 6 3.42914 72.28614 33.714 12 72.000 14 63.286 12 10 620 3 3 6.47120 16.00018 24.471 10 44.941 14 10 2.000 812 718 3 5 4.40012 17.06714 06.400 10 26.267 14 44.267 10 7 818 0 5 3.333 8 2 8.33318 25.556 16 47.000 18 53.444 10 8 917 0 5 3.76516 011.760 34 15.882 16 110.940 34 44.940 24 8 11 13 0 7 1.846 8 2 6.76918 25.231 24 24.615 8 2 3.692 8 7 13 9 0 7 0.444 2 3 2.667 8 1 3.556 6 4 1.556 4 3 1.778 4 8 15 6 0 5 0.333 2 4 0.667 2 4 0.667 2 3 1.000 2 4 1.000 4 5 18 2 0 2 0.000 0 2 0.000 0 2 0.000 0 2 0.000 0 2 0.000 0 2 for D=20 156 971 48 40 58 63 99 25 318 213 1.62512 15 0.62510 15 0.625 10 16 0.000 0 9 2.250 14 16 517 8 3 4.44414 34.66714 44.000 10 44.000 14 34.444 16 7 720 14 24.00014 15.000 8 0 10.000 16 15.333 10 05.000 8 2 918 6 2 9.16730 014.670 22 011.500 20 013.500 22 16.667 18 3 11 18 0 0 10.110 38 023.890 52 110.890 20 019.560 52 27.000 16 3 13 15 0 3 5.06718 116.000 36 111.200 28 014.530 36 24.933 16 5 16 13 0 6 1.538 6 1 7.38520 34.769 12 34.615 12 52.923 8 9 19 8 0 6 0.500 2 5 0.750 2 4 1.250 4 4 1.250 4 5 0.750 2 7 22 3 0 3 0.000 0 3 0.000 0 3 0.000 0 3 0.000 0 3 0.000 0 3 for D=25 130 30 38 29 31 31 30 55 Total 389 39 180 142 140 156 170 249 (1) Number of instances (2) Number of instances excluded from examination (3) Number of instances for which the heuristic found an optimal solution (4) Average difference between the heuristic and optimal values (5) Maximum difference between the heuristic and optimal values (6) Number of instances for which some heuristic found an optimal solution have been excluded from the comparison statistics. The highest average and maximum differences between heuristic and optimal solutions have been achieved whenever 0.3≤D n≤0.6. The sequences obtained 23 by the Insertion method have been reduced to optimal ones most often, closely followed by Random sequences and bottleneck sequences. The heuristics found optimum for 249 instances out of the 350 for which the optimum could be found. 6. Conclusions and Further Research There a number of possible directions to proceed in order to search for improvement in response time variability. We think the following are most natural for the problem and promising. •Exploit the properties of the number decomposition graphs introduced in Section 2 and the sufficient conditions for local optima defined by the exchange procedure from Section 4 in the Constraint Logic programming approach. •Use the randomized greedy algorithm, in the form of GRASP, see Feo and Resende [7]. This would build a sequence, one product at a time, by taking into account the increase in the response time variability, first, and the throughput error, second, associated with the candidate product. The choice could be randomized by randomly choosing one of the best candidates, but not necessarily the best one. The complete sequence would then by subjected to the exchange procedure described in Section 4. •Use multi-start. •Find lower bounds on the response time variability for partial solutions and use them along with the upper bounds obtained by the heuristics of Section 4 to prune the states of the Dynamic Programming algorithm defined in Section 2. References [1] Altman, E., B. Gaujal and A. Hordijk(2000), “Multimodularity, Convexity and Optimization Properties”, Math. of Oper. Research, Vol. 25, pp. 324-347. [2] Anily, S., C.A. Glass and R. Hassin (1998), The scheduling of maintenance service, Discrete Applied Mathematics 82, 27 42. [3] Balinski, M. L., Young, H.P. (1982): Fair Representation. Yale University Press, New Haven, CT. [4] Bar-Noy, A., R. Bhatia, J. Naor, and B. Schieber (1998) Minimizing service and operation costs of periodic scheduling. In Ninth Annual ACMSIAM Symposium on Discrete Algorithms SODA, 1998, 11-20. [5] Bautista, J., R. Companys and A. Corominas (1996) A note on the relation between the product rate variation (PRV) and the apportionment problem. Journal of Operational Research Society 47 1410-1414. 24 [6] Bautista, J., Companys, R., Corominas, A. (1997): Modelling and solving the production rate variation problem, TOP , vol. 5, 2, 221-239. [7] Feo, T. and M. Resende (1989). A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters 8, 6771. [8] Dong, L., R. Melhem and D. Mosse(1998), ”Time Slot Allocation for Real-time Messages with Negotiable Distance Constrains Requirements”, The Real-time Technology and Application Symposium, RTAS, Denver, CO. [9] Han, C.C., K.J. Lin, and C.J. Hou(1996), ”Distance-Constrained Scheduling and Its Applications in Real-Time Systems,” IEEE Trans. on Computers, Vol. 45, No. 7, pp. 814-826. [10] Kubiak, W., and S.P. Sethi (1991) A Note on ”Level schedules for mixedmodel assembly lines in just-in-time production systems,” Management Science 37 121-122. [11] Kubiak, W. (1993): Minimizing variations of productions rates in just-in-time systems: A survey, Eur. J. Opl. Res., 66, 259-271. [12] Kubiak, W. (2003) On small deviations conjecture, Bulletin of the Polish Academy of Sciences 51 189-203. [13] Kubiak, W. (2004) Fair Sequences, In Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Joseph Y-T. Leung (Edt.) Chapman and Hall/CRC, to appear. [14] Monden, Y. (1983) Toyota Production Systems Industrial Engineering and Management Press, Norcross, GA. [15] Moreno, N. (2002): Solving the Product Rate Variation Problem (PRVP) of large dimensions as an assignment problem, Doctoral Thesis, DOE, ETSEIBUPC. [16] Steiner, G., Yeomans S. (1993): Level Schedules for Mixed-Model, Justin-Time Processes, Management Science, vol. 39, no. 6, 728-735. [17] Waldspurger, C.A., Weihl, W.E. (1995) Stride Scheduling: Deterministic Proportional-Share Resource Management. Technical Memorandum MIT/LCS/TM-528 MIT Laboratory for Computer Science Cambridge, MA 02139